Question

Consider two languages L1 and L2 accepted by the pushdown automata M1 = (K1, Σ, Γ1, ∆1, s1, F1) and M2 = (K2, Σ, Γ2, ∆2, s2, F2), respectively. Show how to construct the pushdown automaton M = (K, Σ, Γ, ∆, s, F ) that accepts L1L2.

Answer 1

to construct a PDA that accepts L₁L₂ we do the following:

step 1:

Making unique final state in M1, to do this,

add a state q0 and transition from all the final states of M₁ by reading , popping from stack and pushing .

step 2:

if stack is not empty, empty it. i.e. add a transition from state q0 to itself by reading , popping x (in Σ₁ ) from stack and pushing .

step3:

add a transition from q0 to s2 by reading , popping # from stack and pushing #. where # is end of stack symbol.

The obtained PDA accepts L1L2