Question

Read the definitions of NOPREFIX ( $\mathbf{A}$) and NOEXTEND ($\mathbf{A}$) in Problem .

a. Show that the class of CFLs is not closed under NOPREFIX.

b. Show that the class of CFLs is not closed under NOEXTEND.

Short answer

a).The class of CFLs is not closed under NOPREFIX is proved.

b). The class of CFLs is not closed under NOEXTEND is proved.

Step-by-step solution

Context free language.

Context free language is a grammar where its language is supports pushdown deterministic automata.The class of CFLs is not closed under NOPREFIX

And also, theclass of CFLs is not closed under NOEXTEND.

It means these two properties does not support by context free language.

Step 2: The class of CFLs is not closed under NOPREFIX.

a).

Consider the language$\mathrm{L}=\mathrm{L}1\cup \mathrm{L}2$where,

$\mathrm{L}1=\left\{{\mathrm{a}}^{\mathrm{n}}{\mathrm{b}}^{\mathrm{m}}\mathrm{c}\right|\mathrm{n}\ne \mathrm{m},\mathrm{n},\mathrm{m}\ge 1\}$and

${\mathrm{L}}_2=\left\{{\mathrm{a}}^{\mathrm{n}}{\mathrm{b}}^{\mathrm{m}}{\mathrm{c}}^{\mathrm{m}}\right|\mathrm{n},\mathrm{m}\ge 1\}.$

Are the two languages.

If we consider a string of$\mathrm{L}1=\left\{{\mathrm{a}}^{\mathrm{n}}{\mathrm{b}}^{\mathrm{m}}\mathrm{c}\right|\mathrm{n}\ne \mathrm{m},\mathrm{n},\mathrm{m}\ge 1\}$.

Its proper prefixes are strings containing only a's and b's and all strings in$\mathrm{L}1$

and ${\mathrm{L}}_2$contain at least $1\mathrm{c}$.

Hence every string in$\mathrm{L}1$is in NOPREFIX(L).

If we consider a string in,${\mathrm{L}}_2=\left\{{\mathrm{a}}^{\mathrm{n}}{\mathrm{b}}^{\mathrm{m}}{\mathrm{c}}^{\mathrm{m}}\right|\mathrm{n},\mathrm{m}\ge 1\}.$it is not in NOPREFIX(L) if, there is a proper prefix of it which is in$\mathrm{L}$, since no proper prefix of it is in$\mathrm{L}$

(the number of bs will not be equal to the number of cs in any proper

prefix), the proper prefix will have to come from${\mathrm{L}}_1$and hence the$\mathrm{n}\ne \mathrm{m}$.

So, the strings in $\mathrm{L}1$which are in NOPREFIX (${\mathrm{L}}_1$) are$\left\{{\mathrm{a}}^{\mathrm{n}}{\mathrm{b}}^{\mathrm{m}}\mathrm{c}\right|\mathrm{n}\ne \mathrm{m},\mathrm{n},\mathrm{m}\ge 1\}$.

Therefore,

NOPREFIX( ${\mathrm{L}}_1$) =$\mathrm{L}1$role="math" localid="1659711270607" $\cup$$\mathrm{L}1=\left\{{\mathrm{a}}^{\mathrm{n}}{\mathrm{b}}^{\mathrm{m}}\mathrm{c}\right|\mathrm{n}\ne \mathrm{m},\mathrm{n},\mathrm{m}\ge 1\}$.

However, NOPREFIX ($\mathrm{L}$) is not context-free.

Otherwise NOPREFIX ($\mathrm{L}$) = { $\left\{{\mathrm{a}}^{\mathrm{n}}{\mathrm{b}}^{\mathrm{m}}{\mathrm{c}}^{\mathrm{m}}\right|\mathrm{n},\mathrm{m}\ge 1\}.$is context-free which is a contradiction.

The unambiguous CFGs context free grammar is a context free grammar by which only one parse tree or only one derivation tree is possible.
Therefore, there exists a context-free language$\mathrm{L}$such that NOPREFIX ( $\mathrm{L}$) is not context-free, hence context- free languages are not closed under NOPREFIX operation.

Therefore NOPREFIX(${\mathrm{L}}_1$) = $\mathrm{L}1\cup$$\mathrm{L}1=\left\{{\mathrm{a}}^{\mathrm{n}}{\mathrm{b}}^{\mathrm{m}}\mathrm{c}\right|\mathrm{n}\ne \mathrm{m},\mathrm{n},\mathrm{m}\ge 1\}$.

Hence, it is proved that the class of CFLs is not closed under NOPREFIX.

Step 3: The class of CFLs is not closed under NO EXTEND

b).

Consider the language where ${\mathrm{L}}_1=\left\{{\mathrm{a}}^{\mathrm{n}}{\mathrm{b}}^{\mathrm{m}}{\mathrm{c}}^{\mathrm{p}}\right|\mathrm{n}\ne \mathrm{m},\mathrm{n},\mathrm{m},\mathrm{p}\ge 1\}$ and ${\mathrm{L}}_2=\left\{{\mathrm{a}}^{\mathrm{n}}{\mathrm{b}}^{\mathrm{m}}{\mathrm{c}}^{\mathrm{m}}\right|\mathrm{n},\mathrm{m}\ge 1\}.$Consider ${\mathrm{a}}^{\mathrm{n}}{\mathrm{b}}^{\mathrm{m}}{\mathrm{c}}^{\mathrm{p}}$belongs to language one, this string is not in NOEXTEND(L) since ${\mathrm{a}}^{\mathrm{n}}{\mathrm{b}}^{\mathrm{m}}{\mathrm{c}}^{\mathrm{p}}$, an extension of the string is in L.

Now consider a string${\mathrm{a}}^{\mathrm{n}}{\mathrm{b}}^{\mathrm{m}}{\mathrm{c}}^{\mathrm{p}}$.

${\mathrm{L}}_2=\left\{{\mathrm{a}}^{\mathrm{n}}{\mathrm{b}}^{\mathrm{m}}{\mathrm{c}}^{\mathrm{m}}\right|\mathrm{n},\mathrm{m}\ge 1\}.$, it is not in NOEXTEND(L) if, there is a proper prefix of it which is in $\mathrm{L}$, since no proper prefix of it is in $\mathrm{L}$

(the number of bs will not be equal to the number of cs in any proper

prefix), the proper prefix will have to come from ${\mathrm{L}}_1$and hence the $\mathrm{n}\ne \mathrm{m}$.

So, the strings in ${\mathrm{L}}_1$which are in NOEXTEND (${\mathrm{L}}_1$) are $\left\{{\mathrm{a}}^{\mathrm{n}}{\mathrm{b}}^{\mathrm{m}}\mathrm{c}\right|\mathrm{n}\ne \mathrm{m},\mathrm{n},\mathrm{m}\ge 1\}$

Therefore, NOEXTEND( ${\mathrm{L}}_1$) =$\mathrm{L}1$$\cup$$\mathrm{L}1=\left\{{\mathrm{a}}^{\mathrm{n}}{\mathrm{b}}^{\mathrm{m}}\mathrm{c}\right|\mathrm{n}\ne \mathrm{m},\mathrm{n},\mathrm{m}\ge 1\}$ .

However, NOEXTEND ( $\mathrm{L}$) is not context- free.

Otherwise NOEXTEND ( $\mathrm{L}$)= { $\left\{{\mathrm{a}}^{\mathrm{n}}{\mathrm{b}}^{\mathrm{m}}{\mathrm{c}}^{\mathrm{m}}\right|\mathrm{n},\mathrm{m}\ge 1\}.$iscontext-free which is a contradiction.
Hence it is that the class of context free language is not closed under NOEXTEND.