91Ó°ÊÓ

Consider C be the context-free language. Consider be the regular language. The objective of the question is to prove that the intersection of two languages and is context-free.The intersection of two languages is the set of the strings that both languages has in common.

Let $N=(Q_N,∑,{\mathrm{δ}}_N,q_0,F_M)$be a DFA recognizing R . Let $M=(Q_N,\mathrm{Γ},∑,{\mathrm{δ}}_M,q_0,F_M)$be a PDA that recognizes C .

Combine the machines to construct a PDA machine. The PDA machine recognizesC ∩ R . Each state of this PDA consists of two states $(p,q).$

Here, P is a state of PDA and q is a state of N .

The formal definition is:

$M^{\text{'}}=(Q_M,Q_N,∑,\mathrm{Γ},{\mathrm{δ}}_M,(p_o{q}_0),F_M×F_N)$

The transition function ${\mathrm{δ}}_{M^{\text{'}}}$ is defined by

${\mathrm{δ}}_{M^{\text{'}}}\left(\right(p,q),a,x)=\left\{\right((p^{\text{'}},q^{\text{'}}),y\left)\right|(p^{\text{'}},y)∈{\mathrm{δ}}_M(p,a,x)$and${\mathrm{δ}}_N(q,a,)=q^{\text{'}}\}$

Thus, this shows that C ∩ R is context-free.

Assume A is a context free grammar. Let B be the regular language a*b*c*. Then, by Part (a), $Aâˆ\copyright B$is context-free. But $Aâˆ\copyright B$= $\left\{a^n{b}^n{c}^n\right|nâ‰\yen 0\}$this language is not context-free.

Thus, A is not a context free language.