Question

Give context-free grammars generating the following languages.

1. The set of strings over the alphabet $\left\{a,b\right\}$ with more a’s than b’s.
2. The complement of the languagerole="math" localid="1660717618566" $\{a^n{b}^n\overline{)n\ge 0}\}$
3. role="math" localid="1660717878385" $\{w\#x\overline{)w^R}isasubstringofxforw.x\in \left\{0,1\right\}*\}$
4. role="math" localid="1660718125664" $\{x_1{\#}_2\#...\#x_k\overline{)k\ge 1,each{x}_i\in \left\{a,b\right\}*,andforsomeiandj,x_i=x_j^R}\}$
   

Short answer

1. $$\begin{gathered} S\to RaR \\ R\to RR\overline{)aRb\overline{)bRa\overline{)a\overline{)\epsilon }}}} \end{gathered}$$
   
2. $$\begin{gathered} S\to RbRaR\overline{)T\overline{)Q}} \\ T\to aTb\overline{)Tb}\overline{)b} \\ Q\to aQb\overline{)aQ\overline{)a}} \\ R\to aR\overline{)bR\overline{)\epsilon }} \end{gathered}$$
   
3. $$\begin{gathered} S\to RX \\ R\to 0R0\overline{)1R1\overline{)\#X}} \\ X\to XX\overline{)1\overline{)0\overline{)\epsilon }}} \end{gathered}$$
   
4. $$\begin{gathered} S\to X\#Y\#X\overline{)Y\#X\overline{)X\#Y\overline{)Y}}} \\ Y\to aYa\overline{)bYb\overline{)a\overline{)b\overline{)\#\overline{)\#X\#\overline{)\epsilon }}}}}} \\ X\to aX\overline{)bX\overline{)\#X\overline{)\epsilon }}} \end{gathered}$$
   

Step-by-step solution

Explain Context-free languages

A context-free grammar consists of productions, variables, and terminals. Productions have the arrow representation with terminals on the left hand side and the variables on the right hand side. Terminals are represented by uppercase letters and the variables are represented by the lower case letters.

Give context-free grammars that generate the given language.

a.

Consider context-free language, with the set of strings over the alphabet {a,b} with more a’s than b’s. The context-free grammar that produces the above language is as follows,

$$\begin{gathered} S\to RaR \\ R\to RR\overline{)aRb\overline{)bRa\overline{)a\overline{)\epsilon }}}} \end{gathered}$$

In the above grammar, the production R ensures that the string contains more a’s than b’s.

Therefore, the context-free grammar for the given language has been obtained.

Give context-free grammars that generate the given language.

b.

Consider context-free language,The complement of the language $\{{\mathrm{a}}^{\mathrm{n}}{\mathrm{b}}^{\mathrm{n}}\overline{)\mathrm{n}\ge 0}\}$. The context-free grammar that produces the above language is as follows,

$$\begin{gathered} S\to RbRaR\overline{)T\overline{)Q}} \\ T\to aTb\overline{)Tb}\overline{)b} \\ Q\to aQb\overline{)aQ\overline{)a}} \\ R\to aR\overline{)bR\overline{)\epsilon }} \end{gathered}$$

In the above grammar, the productions T,Q,R ensures that the complement of the language is produced.

Therefore, the context-free grammar for the given language has been obtained.

Give context-free grammars that generate the given language.

c.

Consider context-free language,$\{\mathrm{w}\#\mathrm{x}\overline{){\mathrm{w}}^{\mathrm{R}}}\mathrm{is}\mathrm{a}\mathrm{substring}\mathrm{of}\mathrm{x}\mathrm{for}\mathrm{w}.\mathrm{x}\in \{0,1\}*\}$. The context-free grammar that produces the above language is as follows,

$$\begin{gathered} S\to RX \\ R\to 0R0\overline{)1R1\overline{)\#X}} \\ X\to XX\overline{)1\overline{)0\overline{)\epsilon }}} \end{gathered}$$

In the above grammar, the productions S,R,X ensures that w^R is a substring of x for w.

Therefore, the context-free grammar for the given language has been obtained.

Give context-free grammars that generate the given language.

d.

Consider context-free language,$\{{\mathrm{x}}_1{\#}_2\#...\#{\mathrm{x}}_{\mathrm{k}}\overline{)\mathrm{k}\ge 1,{\mathrm{eachx}}_{\mathrm{i}}\in \{\mathrm{a},\mathrm{b}\}*,\mathrm{and}\mathrm{for}\mathrm{some}\mathrm{i}\mathrm{and}\mathrm{j},{\mathrm{x}}_{\mathrm{i}}={\mathrm{x}}_{\mathrm{j}}^{\mathrm{R}}}\}$. The context-free grammar that produces the above language is as follows,

$$\begin{gathered} S\to X\#Y\#X\overline{)Y\#X\overline{)X\#Y\overline{)Y}}} \\ Y\to aYa\overline{)bYb\overline{)a\overline{)b\overline{)\#\overline{)\#X\#\overline{)\epsilon }}}}}} \\ X\to aX\overline{)bX\overline{)\#X\overline{)\epsilon }}} \end{gathered}$$

In the above grammar, all the productions ensures that the string is in the format of the given context free language..

Therefore, the context-free grammar for the given language has been obtained.