i saw in a book how to construct a PDA for a case with m is equal to n . It's pretty simple, just push a symbol for every a and pop this symbol for every b that the PDA reads. But, i don't found a way to construct a PDA for this particular case. Every help is welcome.
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
You can think about the scheme you proposed (push a symbol for every a, pop for every b) as using the stack as a counter. When you see an a, you increment the counter (push a symbol onto the stack) and when you see a b, you decrement the counter (pop from the stack). In the case where $m=n$, the stack should be empty after processing the whole string, or in other words the value of the counter should be 0. Following the same scheme, how would we know from the count that $m > n$? What would the stack have to look like in that case?
$\begingroup$
$\endgroup$
According to me if no. of a's is greater than no. Of b's and once the pushing of string a is completed in the stack then we start popping out every a for every b we get,then at last more than 1 no. Of a will be left in the stack as no. Of a's is greater in no..Hence keeping this concept in mind you can draw the transition diagram and table as well.
