

![0_image_0.png](0_image_0.png)

![0_image_1.png](0_image_1.png)

## 4.2 Transformation Into A Pushdown Automaton

Given an acyclic grammar Ga = (**T, H, P, S**1,n) from the previous section, we now construct a pushdown automaton Pa(hS1,ni, T, T ∪ H, δ, QP , FP ), where hS1,ni is the initial stack of Pa, T is the alphabet, T ∪H is the set of stack symbols, δ is the transition function, QP = FP = {qP } is the single initial and accepting state. We use an algorithm that encodes a context free grammar into a pushdown automaton (PDA) that computes the leftmost derivation of a string[5]. The stack maintains the sequence of symbols that are expanded in this derivation. At every step, the PDA non-deterministically uses a production to expand the top symbol of the stack if it is a non-terminal, or consumes a symbol of the input string if it matches the terminal at the top of the stack.

We now describe this reformulation in detail. There exists a single state qP which is both the starting and an accepting state. For each non-terminal Ai,j in Ga we introduce the set of transitions δ(qP , ε, Ai,j ) = {(qP , β)|∀Ai,j → β ∈ Ga}. For each terminal ai ∈ Ga, we introduce a transition δ(qP , ai, ai) = {(qP , ε)}. The automaton Pa accepts on the empty stack. This constructs a pushdown automaton accepting L(Ga). Example 4. The pushdown automaton Pa constructed for the running example.

δ(qP , ε, S1,3) = δ(qP , A1,2B3,1) δ(qP , ε, S1,3) = δ(qP , A1,1B2,2)
δ(qP , ε, A1,2) = δ(qP , A1,1A2,1) δ(qP , ε, B2,2) = δ(qP , B2,1B3,1)
δ(qP , ε, Ai,1) = δ(qP , ai) δ(qP , ε, Bi,1) = δ(qP , bi)∀i ∈ {1, 2, 3}
δ(qP , ai, ai) = δ(qP , ε) δ(qP , bi, bi) = δ(qP , ε)∀i ∈ {1, 2, 3}

## 4.3 Transformation Into A Nfa

Finally, we construct an NFA(Σ, Q, Q0, F0, σ), denoted Na, using the PDA from the last section. States of this NFA encode all possible configurations of the stack of the PDA that can appear in parsing a string from Ga. To reflect that a state of the NFA
represents a stack, we write states as sequences of symbols hαi, where α is a possibly empty sequence of symbols and α[0] is the top of the stack. For example, the initial