Context-Free Grammar to Pushdown (Stack) Automata

Question

Given the following problem:

Convert the following Context-Free Grammar specification to it's corresponding Pushdown (Stack) Automata.

$$ G = (N, \sum , P, S) \\ N = \{ S, A \} \\ \sum = \{ 0, 1 \} \\ P = \{ S \rightarrow 0S1, S \rightarrow A, A \rightarrow 1A0, A \rightarrow S, A \rightarrow \epsilon \} $$

When constructing the automata, I know that each operation is of the the form $\alpha ; \beta ; \delta$ where:

• $\alpha$: the input value
• $\beta$: the value to be checked or removed from the stack
• $\delta$: the value to be inserted into the stack

But in the Grammar for example, if I am correct:

• $S \rightarrow 0S1$: is a movement given an input of $0$, move to the state $S$ and insert the value $1$ into the stack. But what value do I check for in the stack or does this mean that it does not matter what value is at the top of the stack?

• $A \rightarrow \epsilon$: Is to ignore what is at the top of the stack (not remove anything). But does this mean that the input does not matter and I do not insert anything into the stack? Also, which state am I to move to?

Answer 1

$$M=(Q,\ \Sigma,\ \Gamma,\ \delta, \ q_{0},\ Z, \ F)$$ $$Q = \{q\}, \Sigma = \{0, 1\}, \Gamma = \{S, A, 0, 1\}, q_{0} = q, Z = S, F = \{q\}$$ $$\delta(q, \epsilon, S) = \{(q, A),(q, 0S1)\}$$ $$\delta(q, \epsilon, A) = \{(q, S),(q, 1A0),(q, \epsilon)\}$$ $$\delta(q,0,0) = (q, \epsilon)$$ $$\delta(q,1,1) = (q, \epsilon)$$

With:

• $Q$ the set of states.
• $\Sigma$ input alphabet
• $\Gamma$ stack alphabet
• $\delta$ transition relation.
• $q_{0}$ start state.
• $Z$ initial stack symbol.
• $F$ accepting states.