in Theory of Computation edited by
2,679 views
2 votes
2 votes

Context free languages are closed under

  1. union, intersection
  2. union, kleene closure
  3. intersection, complement
  4. complement, kleene closure
in Theory of Computation edited by
by
2.7k views

1 comment

CFLs are closed under kleene closure and union therefore option B is correct
0
0

4 Answers

3 votes
3 votes

Context Free Languages are:

1) Closed under Union, Kleen Closure

2) not closed under intersection and complementation.

However,

Deterministic CFL are closed under intersection, but not closed under Union.

b) union, kleen closure is the answer.

1 vote
1 vote
$\underline{\textbf{Answer:}\Rightarrow}\;\mathbf{b.}$

Context-free languages are closed under Union and Kleene Closure but not closed under intersection.
by
0 votes
0 votes

Lemma: The context-free languages are closed under union, concatenation and Kleene closure.
That is, if $L_{1}$ and $L_{2}$ are context-free languages, so are$L_{1}$U$L_{2}$​​, $L_{1}$.$L_{2}$and ​​​​​​$L_{1}*$​​​​​​​
Proof:
We will prove that the languages are closed by creating the appropriate grammars.
Suppose we have two context-free languages, represented by grammars with start symbols ​​​​​​​$S_{1}$and ​​​​​​​$S_{2}$ respectively. First of all, rename all the terminal symbols in the second grammar so that they don't conflict with those in the first. Then:

  • To get the union, add the rule $S\; \rightarrow\; S_1\; \mid\; S_2$
  • To get the concatenation, add the rule $S\; \rightarrow\; S_1\; S_2$
  • To get the Kleene Closure of $L_1$, add the rule $S\; \rightarrow\; S_1\; S \mid\; \varepsilon$ to the grammar for $L_1$.


So B is correct.

Ref: http://www.cs.nuim.ie/~jpower/Courses/Previous/parsing/node43.html

0 votes
0 votes
Option B) CFL’s are closed under union and kleene closure.
Answer:

Related questions