Problem Solving in Automata, Languages, and Complexity

140 CONTEXT-FREE LANGUAGES

It is clear that the above PDA M accepts z$ if and only if there ex-
ists a computation path of Ml that accepts q for some y c L2. Thus,

L(M) = (h/J52){$}* BY J3-l eorem 3.37, there exists a context-free grammar

G generating (&/&){$}. Note that in G, $ is a terminal symbol. Now, we
change $ from a terminal symbol to a nonterminal symbol and add a new rule
$ -+ E to G. Then, we obtain a new context-free grammar generating Li/L2.
Cl

• Example 3.42 Show that if L is regular, then

z = I= I PY) [I4 = IYI = I47 x:yz E Ll}

is context-free.

Proof. Let M = (Q&S, 41, F) be a DFA accepting L, with Q =

{Ql, q2, l l. , qn}. We will construct a PDA to accept the language z. The

idea is to apply the multi-track simulation of Example 2.40 to PDA’s:

(1) We nondeterministically divide the input zu into two parts w = zz.

(2) We simulate M on x and also push x: into the stack. Assume that it

ends at state q;, 1 < - i < - n.

(3) We guess a string y and simulate M on y starting at state qi; we simul-

taneously simulate M on x starting from state qj for all j = 1,... , n.

During these simulations, we use string x in the stack to check that

IYI = I4 = I4

(4) We accept the input if the simulation of y ends at a state qj and the

simulation of x starting at qj ends at a final state.

To implement the above idea, we need the following NFA: We define an

NFA M’= (Q,C,S’,ql,F), w h ere d’(qi,a) = {S(qi, b) I b E C}, for qi E Q and

a E C.

Now, we can define our new PDA as E = (6, C, C, 8, 41, F), where Q, F

and s” are defined as follows:

(i) Q = Q U Q”+l (so that each state in G is either a state qi E Q or a

state of the form [qi,,, qil,... , qi,] with qij E Q for j = 0, 1,... , n).

(ii) F = {[qm, qil,... ) qi,J E Q”+l 1 qi, E F).

(iii) At each state qj E Q, b(qj, a+) = {(S(qj, a), a)}, for all a E C.

(iv) At each state qj E Q, J(qjyE,E) = {([qj,ql,q2y l --yqn]lE)}-

(v) At state [qjy qilI qi2)... y qi,] E Q”+l y b([qj > qil y qi2 7 l l b 7 Qi,l, a, b)) =

Assume that w = xz E E, where 1x1 = lz]. Then, there is an accepting

path of M on xyx for some Iy] = 1x1 as follows: