PDA question > need help

i have a task to construct the PDA which recognizes the language A= {a^m b^n | m > n} with ∑ = {a, b}.. i'm a bit confused how to do it.. can you guys help me to solve thi开发者_开发知识库s question? thanks

Look at this example on the Wikipedia page for pushdown automata: it's for the language { 0ⁿ1ⁿ | n ≥ 0 }, that is, some number of zeroes followed by the same number of ones. This is not exactly the same as your task, but similar. Can you understand the description based on your course material? How would you modify it to recognize the language you need?

Let's not jump directly on to designing a PDA for the problem, and try to understand the question first.

What are few possible string that can be generated from the given language.
Well there can be infinite such string, for instance -

1. aab
2. aaab
3. aaa...b
4. aaaa..bb

The idea is to make sure that number of a's is always greater than number of b's, or we can say that number of b's in a string should never exceed number of a's in the string to be accepted by the PDA.

So now we have a question.

How to make sure that number of a's greater than number of b's

For a string if we start to cancel a's for every 'b' in the string
We will be left with the following conclusion

1. Number of a's was equal to number of b's - There was nothing left after cancellation
2. Number of b's was greater than number of a's - We were left with few b's after cancellation
3. Number of a's was greater than number of b's - We were left with few a's after cancellation

If we try to establish a relationship between 'Question' and those points above we observe that string which belong to Point No. 3 above are the strings acceptable by the PDA.

Now lets define our PDA as follows

P = ({q0,q1,qf}, {a,b}, δ, {a,b,Z0}, q0, Z0, {qf})

Transition function (δ):

δ(q0, a, Z0) = (q0,aZ0)  
δ(q0, a, a) = (q0, aa)  
δ(q0, b, a) = (q1, Λ)  
δ(q1, b, a) = (q1, Λ) 
δ(q1, Λ, a) = (qf, Z0) 
δ(q1, b, Z0) = (q2, Z0)  
δ(q1, Λ, Z0) = (q2, Z0)

Explanation:

1. We initially store a's in the stack (q0 state)
2. When first b is encountered, we pop a from stack and change state to q1
3. We continue popping a's from stack
4. If there is no b's left to pop a from stack we change the state to qf to indicate the string acceptace. (POINT No. 3)
5. If there are few b's left but there is no a to pop out from stack, we change state from q1 to q2(Trap). (POINT No. 2)
6. If neither a's is left in stack to be popped out nor b's are left in input string, we again change the state from q1 to q2(Trap). (POINT No. 1)