Push down automata for context free grammar

202 Views Asked by At

I'm having trouble finding the PDA for this language

$L = \{x^{3i} y^j z^k\ |\ i \ge 0 \land k \gt 2j \gt 0\}$

The free context grammar is

$$S \rightarrow TyUz^3$$ $$T \rightarrow xxxT\ |\ \lambda$$ $$U \rightarrow yVzz\ |\ \lambda$$ $$V \rightarrow zV \ |\ \lambda$$

Here's my try:

  • Any multiple of 3 number of xs $$(q_0, x, z_0) \vdash (q_1, z_0)$$ $$(q_1, x, z_0) \vdash (q_2, z_0)$$ $$(q_2, x, z_0) \vdash (q_0, z_0)$$

  • Then ys, we must store two symbols per each (not necessary a state change) $$(q_0, b, z_0) \vdash (q_0, bbz_0)$$ $$(q_0, b, b) \vdash (q_0, bbb)$$

  • Then zs. $$(q_0, z, b) \vdash (q_3, \lambda)$$ $$(q_3, z, b) \vdash (q_3, \lambda)$$ $$(q_3, z, z_0) \vdash (q_f, z_0)$$ $$(q_f, z, z_0) \vdash (q_f, z_0)$$ $$(q_f, \lambda, z_0) \vdash (q_f, \lambda)$$

1

There are 1 best solutions below

0
On BEST ANSWER

There is a very simple method of transforming a CFG into an PDA having a single state and acceptance by empty stack. It is the expand-match method, and is explained on wikipedia.

For each production $X\to\alpha$ we expand $(1,\varepsilon,1,X,\alpha)$ and for each terminal symbol $a$ we match $(1,a,1,a,\varepsilon)$. Thus expanding is simulationg the production, but on the stack, and matching means we check whether the symbol produced is actually on the input. One technicality: in this way of writing the stack for the PDA it is assumed its Top is written on the left, so it represents the sentential form derived by the grammar.

This method does not use states. Therefore directly programming your PDA might give both a simpler automaton and better understanding.