Question

Let $\mathit{E}\mathbf{=}\left\{a^i{b}^j|i\ne jand2i\ne j\right\}$. Show that$\mathit{E}$ is context-free language.

Short answer

It is shown that$E$ is a context-free language.

Step-by-step solution

Define context-free language

The context-free language is generated by context-free grammar. These languages are accepted by Pushdown Automata. These are the supersets of regular languages.

Consider context-free languages $L_1$described as $G_1=(V_1,S,R_1,S_1).$

Consider context-free language$L_2$ described as$G_2=(V_2,S,R_2,S_2).$

Explain the solution

Split it as unions of three languages.

$$\begin{gathered} \left\{a^i{b}^j|i>j\right\}̀E\left\{a^i{b}^j|i<jand2i>j\right\}\cup \left\{a^i{b}^j|2i<j\right\} \\ {G}^1=\left\{a^i{b}^j|i>j\right\} \\ {G}^2=\left\{a^i{b}^j|i<jand2i>j\right\} \\ {G}^3=\left\{a^i{b}^j|2i<j\right\} \end{gathered}$$

$$\begin{gathered} G^{1}and{G}^{3}arequiteeasytofigureout. \\ for{G}^1 \\ S\to aSb|a{S}^1 \\ {S}^1\to a{S}^1|\epsilon \end{gathered}$$

for G³

$$\begin{gathered} S\to aSbb|S^{1}b \\ {S}^1\to S^{1}b|\epsilon \\ NowtrickypartisG2. \end{gathered}$$

$$\begin{gathered} S\to aSb|a{S}^{1}b \\ {S}^1\to a \\ {S}^{1}bb|a{S}^{2}bb \\ {S}^2\to \epsilon \end{gathered}$$

It is proved very clearly, that $Swillgenerate{a}^n{a}^m{b}^{2m}{b}^{n}thatisequivalentto{a}^{n+m}{b}^{n+2m}$,

where$m,nmustbegreaterthan0.$

Hence,$E$ is a context-free language.