Question

Give a counter example to show that the following construction fails to prove that the class of context-free languages is closed under star. Let A be a CFL that is generated by the CFG $G=(V,\in ,R,S)$. Add the new rule$S\to SS$ and call the resulting grammar. This grammar is supposed to generate A*.

Short answer

Answer.

The construction fails for $\mathit{L}\mathbf{=}\mathbf{\left\{}\mathit{a}\mathbf{\right\}}\mathbf{.}$

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 superset 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 ${\mathit{G}}_{\mathbf{2}}\mathbf{=}\mathbf{(}{\mathit{V}}_{\mathbf{2}}\mathbf{,}\mathit{S}\mathbf{,}{\mathit{R}}_{\mathbf{2}}\mathbf{,}{\mathit{S}}_{\mathbf{2}}\mathbf{)}\mathbf{.}$

Determine the counter example

Consider the language$\mathit{L}\mathbf{=}\mathbf{\left\{}\mathit{a}\mathbf{\right\}}\mathbf{.}\mathbf{}$

The given grammar and the language is in context free grammar in the form of .$\mathit{G}\mathbf{=}\mathbf{(}\mathit{V}\mathbf{,}\mathbf{\in }\mathbf{,}\mathit{R}\mathbf{,}\mathit{S}\mathbf{)}\mathbf{.}$

Note that $\mathit{L}\mathbf{*}\mathbf{=}\mathbf{\{}\mathit{\epsilon }\mathbf{,}\mathit{a}\mathbf{,}\mathit{a}\mathit{a}\mathbf{,}\mathit{a}\mathit{a}\mathit{a}\mathbf{,}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{\}}$

A grammar of L is localid="1662050454885" $G=\left(\right\{S\},\{a\},\{(S\to a)\},S).$

The construction gives :$G\text{'}=\left(\right\{S\},\{a\},\{(S\to a),(S\to SS)\},S).$

However, L (G) does not contain ε so the construction doesn’t produce a grammar for L*.

Hence, the construction fails for $L=\left\{a\right\}.$