CFG and closure properties

302 Views Asked by At

I am solving one problem and I urgently need a hint to solve one problem:

Use closure under union to show that the following language is context-free $$\left\{a^mb^nc^pd^q : n=q,\ \text{or}\;\ m\leq p\ \;\text{or}\;\ m+n=p+q\right\}$$

EDIT: I study the closure properties of context-free languages. It was said there that CFG are closed under union.

1

There are 1 best solutions below

2
On BEST ANSWER

HINT: Your language is clearly the union of the following three languages:

$$\begin{align*} L_1&=\left\{a^mb^nc^pd^q:n=q\right\}\\ L_2&=\left\{a^mb^nc^pd^q:m\le p\right\}\\ L_3&=\left\{a^mb^nc^pd^q:m+n=p+q\right\} \end{align*}$$

Can you show that each of these languages is context-free, either directly by writing context-free grammars for them or indirectly by using known context-free languages and preservation properties?