3.5 Pushdown Automata and Context-Free Grammars 139
A = (O”‘l”‘O”21”” l **0”k17nk 1 m1,nz2,.. .,mk > 1,k > - 1),
~~{O~~~~~O~~l~~O~~...l~~o~~l~~+~ ~mo,m;...,?n~+~ > - l,k>O}. -It is clear that both A and B are context-free. In addition, we can check that
AnB=E.
It is not hard to see that both A and B are also context-free. More precisely,
we note that
A= (o+l+)*{o”l” 1 m, 72 > 1, m # n}(O+l+)*
u l+(o + l)* u (0 + l):o+B = 0+(1+0+){1~0” (^1) m, n > 1, m # n}(l+O+)l+
u l+(o + 1> u (0 + 1)oY
So, both A and B are context-free. It follows that L = AU B is also context-
free. Cl
Example 3.41 Show that if L1 is a context-free language and L2 is a regular
language, then the quotient Ll/L2 is a context-free language.
Proof. Recall that x is in LJL2 if and only if there exists a string y E L2 such
that zy E L1. To check the existence of such a string y, we can use the idea
of parallel simulation again. That is, let i& be a PDA that accepts L1 and
A42 a DFA accepting L2. Then, we first simulate A41 on X, and then, when x
is done, we perform a parallel simulation of A41 and A& on an unkown string
Y*
This approach has two problems:
(a) How do we know that we have reached the end of the input string?
(b) How do we find this unknown string y?
Problem (a) can be solved by adding an end-of-string symbol $ to the input.
That is, we first construct a PDA to accept {x$ 1 x: E Ll/L2} instead of
Ll/L2, where $ is a new symbol. This shows that the language (Ll/L2){$}
is context-free. We then argue that it implies that Ll/L2 is also context-free.
For problem (b), we note that PDA’s are nondeterministic and so we can
simply use the E-moves to guess and check the existence of y.
We now describe, based on the above idea, the detail of the product PDA M
for (Ll/L2){$}. Assume that A41 = (Qr, C, I’,&, sr, Fl) and M2 = (Q2, C, 82,
~2, F2). Then, M = (QI u (Ql x &2), C u {$}, W, ~1, FI x F2), WI-M~ 6 is
defined as follows:
(1) For q E &I and a E cu{E), &v,P) =Wwd)-
(a> For 4 E &I, Q, $7 4 = {([a, s2194b
(3) For [ql, 921 E Q 1 x Q2 and P E r u {+
s([ql,q2],E,p) = {([iol,p2lJ) I (3a E lxu -w)
[(PlJ) E ~l(q1,aJ),P2 = s2(q24h