Question

1. Use the languages $\mathit{A}\mathbf{=}\mathbf{\{}{\mathbf{a}}^{\mathbf{m}}{\mathbf{b}}^{\mathbf{n}}{\mathbf{c}}^{\mathbf{n}}\mathbf{}\overline{)\mathbf{}\mathbf{m}\mathbf{,}\mathbf{n}\mathbf{\ge }\mathbf{0}}\mathbf{\}}$and $\mathit{B}\mathbf{=}\mathbf{\{}{\mathbf{a}}^{\mathbf{n}}{\mathbf{b}}^{\mathbf{n}}{\mathbf{c}}^{\mathbf{m}}\mathbf{}\overline{)\mathbf{}\mathbf{m}\mathbf{,}\mathbf{n}\mathbf{\ge }\mathbf{0}}\mathbf{\}}$together with Example 2.36 to show that the class of context-free languages is not closed under intersection.
2. Use part (a) and DeMorgan’s law (Theorem 0.20) to show that the class of context-free languages is not closed under complementation.

Short answer

1. The class of context-free languages is not closed under intersection and can be shown by using the given languages.
2. By contradiction and DeMorgan’s law, it can be shown that the class of context-free languages is not closed under complementation.

Step-by-step solution

Explain Context-free languages

A context-free grammar consists of productions, variables, and terminals. The language generated by context-free grammar is called a context-free language.

The context-free grammars generate the languages by the productions and the rules.

Show that the class of context-free languages is not closed under intersection.

a.

Consider the given languages,

$$\begin{gathered} A=\{{\mathrm{a}}^{\mathrm{m}}{\mathrm{b}}^{\mathrm{n}}{\mathrm{c}}^{\mathrm{n}}\overline{)\mathrm{m},\mathrm{n}\ge 0}\} \\ B=\{{\mathrm{a}}^n{\mathrm{b}}^{\mathrm{n}}{\mathrm{c}}^m\overline{)\mathrm{m},\mathrm{n}\ge 0}\} \end{gathered}$$

Consider that the languages A and B are context-free languages.

To prove that, consider that the following grammar recognizes the language A.

$$\begin{gathered} S\to QT \\ Q\to aQ\overline{)\epsilon } \\ T\to bTc\overline{)\epsilon } \end{gathered}$$

The above grammar shows that the language A is a context-free language.

Construct the grammar, that recognizes the language B and shows that the language B is a context-free language.

$$\begin{gathered} S\to QT \\ T\to aTb\overline{)\epsilon } \\ Q\to cQ\overline{)\epsilon } \end{gathered}$$

Perform intersection between the languages A and B.

$A\cap B=\left\{a^n{b}^n{c}^n\overline{)n\ge 0}\right\}$

To check whether, $A\cap B$is a context-free language use pumping lemma.

Assume that $A\cap B$ is a context-free language. Let p be the pumping length for $A\cap B$.

Consider the string $s=a^p{b}^p{c}^p$, s is a member of $A\cap B$ with length p.

To prove that the s cannot be pumped, divide the s into ijkl .

Consider that the substrings t and k contains more that one type of alphabet symbol.

In case 1, if both the substrings t and k contain one type of symbol, t substring contains both a ' s and b ' s or both b ' s and c ' s and the same is for k substring. The string ht²jk²l does not contain equal number of a ' s, b ' s, and c ' s. Thus, it cannot be the member of $A\cap B$and violates the condition for pumping lemma and it the contradiction of the hypothesis.

In case 2, if either of the substrings contain more than one type of symbol ht²jk²l contains equal number of the three alphabet symbols but in the incorrect order. Thus, it cannot be the member of $A\cap B$and violates the condition for pumping lemma and it the contradiction of the hypothesis.

The above cases are in contradiction to the assumption that $A\cap B$is a context-free language.

Therefore, the assumption is false and it is shown that the $A\cap B$is not closed under intersection.

Show that the class of context-free languages is not closed under complementation.

b)

As given , use the DeMorgan’s law to show the languages A and B is not closed under complementation.

DeMorgan’s law : $\overline{A\cup B}=\overline{A}\cap \overline{B}$

Consider the two context-free grammars $C_1=\left(V_1,\sum ,R_1,S_1\right)$and $C_2=\left(V_2,\sum ,R_2,S_2\right)$. The two grammars C₁ and C₂ are closed under the union. Construct the grammar that recognizes the union of the grammars, C₁ and C₂ as $C=\left(V,\sum ,R,S\right)$. The grammar C defined as follows,

• $V=V_1\cup V_2$
• $R=R_1\cup R_2\cup \left\{S\to S_{1,}S\to S_2\right\}$

Assume that the CFGs are closed under complementation. The languages of the grammars C₁ and C₂ are $\overline{L\left(C_1\right)}$and $\overline{L\left(C_2\right)}$are the context-free grammars. The context-free languages under under union, role="math" localid="1660709215340" $\overline{L\left(C_1\right)}\cup \overline{L\left(C_2\right)}$that is context-free. As per the assumption implies, $\overline{L\left(C_1\right)}\cup \overline{L\left(C_2\right)}$is context-free.

By DeMorgan’s law, $\overline{L\left(C_1\right)}\cup \overline{L\left(C_2\right)}=\stackrel{}{L\left(C_1\right)}\cap \stackrel{}{L\left(C_2\right)}$.

By, part (a), $\overline{L\left(C_1\right)}\cup \overline{L\left(C_2\right)}$is not context free, that contradicts the assumption.

Therefore, the assumption is false and it is shown that the context-free grammars are not closed under complementation.