Question

3. Construct a push down au gprnerated by a grammar with producti (npda) that accepts the lana B--b b. Show that the npda in part a accepts the language a 0 RE

Answer 1

a. Here if from non-terminal S, the production S -> aSA happens total n times, then the output will be aⁿSAⁿ and then if S -> a production happen then the output becomes aⁿ⁺¹Aⁿ . And then each non-terminal A produce bB and hence output becomes (aⁿ⁺¹(bB)ⁿ ). Since each B becomes b due to B -> b, hence the output will be aⁿ⁺¹b²ⁿ .

Hence this grammar produce string of the form aⁿ⁺¹b²ⁿ where n>= 0.

Below is the transition function of push-down automata to accept it.

$\delta(q_0,a,Z_0) \rightarrow (q_1,Z_0)$ //On first input a, simply switch to state q₁ .

$\delta(q_1,a,Z_0) \rightarrow (q_2,aZ_0)$ //Push a into stack and move to state q₂

  //Push a into stack and move to state q₂ even when top of stack contains a

(u,a, a2, aa)

$\delta(q_2,\epsilon,a) \rightarrow (q_1,aa)$ //Push a into stack without consuming any input and go back to q₁

Thus for even 'a' in the input, we are putting 'aa' into stack by going from q₁ to q₂ and coming back to q₁ .

$\delta(q_1,b,a) \rightarrow (q_3,\epsilon)$ //once b is encountered, then pop 'a' from stack and move to state q₃

$\delta(q_3,b,a) \rightarrow (q_3,\epsilon)$ //we will pop 'a' from stack for even 'b' in input

$\delta(q_3,\epsilon,Z_0) \rightarrow (q_{accept},\epsilon)$ //Once entire input is over and stack contains only Z₀ then this means input was in the form aⁿ⁺¹b²ⁿ and hence accept the input.

b. We have already shown that above grammar generates aⁿ⁺¹b²ⁿ and hence the push down automata accepts the above grammar.

Please comment for any clarification.