Question

Show that the class of DCFLs is not closed under the following operations:

a. Union

b. Intersection

c. Concatenation

d. Star

e. Reversal

Short answer

a).The deterministic context free language is not closed under Union.

b).The deterministic context free language is not closed underIntersection.

c).The deterministic context free language is not closed underConcatenation.

d).The deterministic context free language is not closed underStar.

e). The deterministic context free language is not closed under Reversal.

Step-by-step solution

Step 1: Deterministic context free language.

Context free language is a grammar where its language or string that formed by context free grammar is supports pushdown deterministic automata.

Context free language is used to represent syntax of language but not used to represent meanings of languages. To represent meaning of a sentence so there Context free grammar is used. Context free language is of two types which is DCFL is deterministic context free language and NDCFL non- deterministic context free language.

Step 2: DCFLs is not closed under Union.

a).

Deterministic context free language is not closed under Union is determined by the Union of two deterministic context free language is may or may not be deterministic context free language hence deterministic context free language is not closed under union.

$\mathrm{DCFL}\mathrm{U}\mathrm{DCFL}=\mathrm{NON}\mathrm{DCFL}$

$\left\{{\mathrm{a}}^{\mathrm{n}}{\mathrm{b}}^{\mathrm{n}}\right\}\cup \left\{{\mathrm{a}}^{\mathrm{n}}{\mathrm{b}}^{2\mathrm{n}}\right\}=\left\{{\mathrm{a}}^{\mathrm{n}}{\mathrm{b}}^{2\mathrm{n}}\right\}$

Hence, the deterministic context free language is not closed under Union.

Step 3: DCFLs is not closed under Intersection.

b).

Deterministic context free language is not closed under Intersection is determined by the intersection of two deterministic context free language is may or may not be deterministic context free language hence deterministic context free language is not closed under Intersection.

$\left\{{\mathrm{a}}^{\mathrm{n}}{\mathrm{b}}^{\mathrm{n}}{\mathrm{c}}^{\mathrm{m}}\right\}\cap \left\{{\mathrm{a}}^{\mathrm{m}}{\mathrm{b}}^{\mathrm{n}}{\mathrm{c}}^{\mathrm{n}}\right\}=\left\{{\mathrm{a}}^{\mathrm{n}}{\mathrm{b}}^{\mathrm{n}}{\mathrm{c}}^{\mathrm{n}}\right\}$

$\mathrm{DCFL}\mathrm{U}\mathrm{DCFL}=\mathrm{NON}\mathrm{DCFL}$

hence, the deterministic context free language is not closed under Intersection.

Step 4: DCFLs is not closed under Concatenation.

c).

The concatenation of two deterministic context free language is may or may not be deterministic contextfree language hence deterministic context free language is not closed under concatenation.

$\begin{array}{l}\mathrm{Ex}.\left\{{\mathrm{XWCW}}^{\mathrm{R}}\right|\mathrm{w}\in {\{\mathrm{a},\mathrm{b}\}}^{+}\}\\ \left\{{\mathrm{XWCW}}^{\mathrm{R}}\right|\mathrm{x}\in {\{\mathrm{a},\mathrm{b}\}}^{+}\}\end{array}$

Hence, the deterministic context free language is not closed under concatenation.

Step 5: DCFLs is not closed under Star.

d).

Thedeterministic context free language is not closed under kleen closure or also called star is defined as it may or may not be deterministic context free language.

It is denoted by ${\mathrm{L}}^{*}$.

$\mathrm{DCFL}\mathrm{U}\mathrm{DCFL}=\mathrm{NON}\mathrm{DCFL}$.

Hence, the deterministic context free language is not closed under star.

Step 6: DCFLs is not closed under Reversal.

e).

Reversal of a deterministic context free language is may or may not be deterministic context free language is defined as,

$\begin{array}{l}\mathrm{L}=\left\{{\mathrm{WCW}}^{\mathrm{R}}\mathrm{X}|\mathrm{X}\in {\{\mathrm{a},\mathrm{b}\}}^{*}\right\}\\ \mathrm{L}=\left\{{\mathrm{XW}}^{\mathrm{R}}\mathrm{CXW}|\mathrm{X}\in {\{\mathrm{a},\mathrm{b}\}}^{+}\right\}\end{array}$

$\mathrm{DCFL}\mathrm{U}\mathrm{DCFL}=\mathrm{NON}\mathrm{DCFL}$

Hence, the deterministic context free language is not closed under reversal.