I'm studying for a test on PDA, and I want to know how to design a pushdown automaton that recognizes the following language:
L = {a^max(0,n-m)b^n a^m| n,m >=0}
How can I design a transition function to recognize if n-m is greater than 0?
And please, if you have some course materials with exercises of this level solved, put a link, my course materials suck and I'm facing a pretty tough test in two days.
you can decide where to go from a current state based on the value on top of the stack, you use symbols on the stack to keep notes about the state of the parsing.
here is how i think this would work: this are symbols read from the input, THIS are symbols on a stack. the symbol X on the botoom of the stack means that n <= m do not confuse X with Z, which is the initial symbol of the stack and helps determine when the stack is empty.
there are probably some problems with this solution, but it the overall approach should be correct.
... and good luck with your test :-)
first you read all the a symbols from the beginning of the string and add A to a stack for each of them, or push X if there was no a
then you read all the b symbols:
the last step is to read the final a symbols.
another edit:
sorry if the above isn't clear ... i'll try to formalize it.
accepting states are (4) and (5), starting state is (1). and it's nondeterministic
and the transition rules:
state (1) : read the first batch of a symbols
state (2) : read b symbols
state (3) : read the last as
state (4) : the trailing as if m > n
state (5) is for accepting the exact string when m < n
(and just to be absolutely clear -- when there is no way of a state and the reading cursor is not at the end of the word, then the word is not accepted)
This could maybe be made a bit simpler by using adidional states instead of the stack symbol X, but i guess you can do it yourself :-)
I think that language L is a context-sensitive or type 1 language on the Chompsky hierarchy. I could be wrong.
Language L1 = { a^n b^n c^n : n >= 1 } is an example of a type 1 language., and this looks pretty similar. It sounds like a trick question to me! I don't think there is a type 2 or context-free grammar or PDA that could recognize or generate L.
Easiest way is probably to write a grammar for the language and then build a PDA for that. Easiest way to write a grammar is to first split the language based on that 'max' so its easier to see what is going on
L = L1 \union L2
L1 = { b^n a^m | m >= n >= 0 }
L2 = { a^(n-m) b^n a^m | n >= m >= 0 }
now rewrite L1 and L2 to make them a bit simpler ( j = m-n, k = n-m )
L1 = { b^n a^n a^j | j,n >= 0 }
L2 = { a^k b^k b^m a^m | k,m >= 0 }
these turn into very simple grammars
L1 := BA A
L2 := AB BA
AB := a AB b | \epsilon
BA := b BA a | \epsilon
A := a A | \epsilon
L := L1 | L2
now build a PDA from them -- easiest to use an automated tool, but can be done manually if you need to show all the work