Question

Question 2
a) Construct a Pushdown Automaton (PDA) for the language L (M) = {a, b}* where, if there
are any a’s must precede all b's and the number of b's must be equal to or twice the number
of a’s.


a) Trace the computations for the strings aabb, bbb, and abb in the PDA obtained in Question 2
 

Answer 1

The given language can be written as union of three simpler languages

PDA for each of the language is:

Their union can be found by adding another start state s and adding the required transitions.

2 aabb belongs to L2, so from s we non-deterministically transition to PDA for L2 by writing x to stack and then we go to state q1 for L2 and write another x to stack then we move to state q2 by reading b and popping x from stack and writing empty string to stack and then finally we read another b pop x push epsilon and finally move to final state.

bbb is in L1 and abb in L3