Register

GO Classes DPP | GATE CS | Theory of Computation | CFL Regular Union

52 views
1 1 vote

Let $R$ be a regular language and $C$ be a context-free language over the same alphabet.

Which statement about $R\cup C$ is always true?

  1. $R\cup C$ must be regular.
     
  2. $R\cup C$ must be context-free.
     
  3. $R\cup C$ must be nonregular.
     
  4. $R\cup C$ may fail to be context-free.

1 Answer

1 1 vote

Every regular language is also a context-free language.

Therefore,

$R\in REG \implies R\in CFL$

We are given

$C\in CFL.$

CFLs are closed under union, hence

$R\cup C\in CFL.$

But it need not be regular.

For example, take

$R=\varnothing$ and $C=\{a^nb^n\mid n\ge0\}$.

Then

$R\cup C=C,$ which is context-free but nonregular.

Therefore the strongest guaranteed conclusion is

$\boxed{R\cup C\text{ is context-free}}.$

Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | GAT...Next → · GO Classes DPP | GAT...
← Previous in category · GO Classes DPP | GAT...Next in category → · GO Classes DPP | GAT...
Position:
Show:

Related questions

1 1 vote
1 1 answer
57
57 views
GO Classes asked Sep 22
57 views
GO Classes DPP | GATE CS | Theory of Computation | CFL Difference
Let $L$ be a context-free language and $R$ be a regular language.Consider the problem$$L-R=\varnothing?$$Which statement is correct?It is decidable because $L-R$ is conte...
1 1 vote
1 1 answer
50
50 views
GO Classes asked Sep 22
50 views
GO Classes DPP | GATE CS | Theory of Computation | CFL Reversal Closure
For a language $L$, define$$L^R=\{w^R\mid w\in L\}.$$ If $L$ is context-free, which statement is correct?$L^R$ is always regular. $L^R$ is always context-free. $L^R$ may ...
1 1 vote
1 1 answer
53
53 views
GO Classes asked Sep 22
53 views
GO Classes DPP | GATE CS | Theory of Computation | CFL Closure
The class of context-free languages satisfies which one of the following?It is closed under intersection. It is closed under complementation. It is closed under concatena...
1 1 vote
1 1 answer
51
51 views
GO Classes asked Sep 22
51 views
GO Classes DPP | GATE CS | Theory of Computation | Kleene Star Closure
Suppose a language $L$ is accepted by some pushdown automaton.What can always be concluded about $L^*$?$L^*$ must be regular. $L^*$ must be context-free. $L^*$ need not b...