Michael Sipser Edition 3 Exercise 2 Question 10 (Page No. 155)

Question

Give an informal description of a pushdown automaton that recognizes the language $A=\{a^{i}b^{j}c^{k}\mid i=j$ $\text{or}$ $ j=k$ $\text{where}$ $ i,j,k\geq 0\}.$

Comments

The PDA for this language will be a NPDA , that is non-deterministic Push Down automata.
Informally the PDA description would be like ,
1. On seeing a , we've to make a non-deterministic decision regarding whether we need to push a's or to do nothing.
Thus we will get 2 branches here , one will check the equality of a's and b's and the other will check the equality of b's and c's.
3. Let's take the first branch , in this , on seeing an a the machine will keep on pushing a's . On seeing a b , the machine changes state and starts popping a's on each b , and on seeing c's the machine would just loop on the state and will do no operation on the stack . After reading the entire string , if the top of the stack is $Z_{0}$ , then the string is accepted , else rejected.

4. Now let's take the other branch , here we'll not be updating the contents of the stack on seeing a's .
On seeing b's , the machine will push b's onto the stack , on seeing c's b's will be popped from the stack .
After reading the entire string , if the top of the stack is $Z_{0}$ , then the string is accepted , else rejected.


Hence , this informal description of the NPDA will accept the language ,


$A=\{a^{i}b^{j}c^{k}|i=j \ or \ j=k\}$