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_{1}L_{2} 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_{1} 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 Σ_{1} ) 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

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 2 minutes ago

asked 6 minutes ago

asked 19 minutes ago

asked 27 minutes ago

asked 35 minutes ago

asked 39 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 2 hours ago

asked 2 hours ago

asked 2 hours ago

asked 2 hours ago