edited by
2,689 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
edited by

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 votes
1 votes
$\underline{\textbf{Answer:}\Rightarrow}\;\mathbf{b.}$

Context-free languages are closed under Union and Kleene Closure but not closed under intersection.
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

3 votes
3 votes
3 answers
1
Satbir asked Jan 13, 2020
2,124 views
Which of the following is true?Every subset of a regular set is regularEvery finite subset of non-regular set is regularThe union of two non regular set is not regularInf...
6 votes
6 votes
5 answers
2
Satbir asked Jan 13, 2020
2,884 views
If $x+2y=30$, then $\left(\dfrac{2y}{5}+\dfrac{x}{3} \right) + \left (\dfrac{x}{5}+\dfrac{2y}{3} \right)$ will be equal to$8$$16$$18$$20$
3 votes
3 votes
4 answers
3
Satbir asked Jan 13, 2020
8,873 views
A given grammar is called ambiguous iftwo or more productions have the same non-terminal on the left hand sidea derivation tree has more than one associated sentencethere...
5 votes
5 votes
12 answers
4
Satbir asked Jan 13, 2020
8,917 views
If every non-key attribute functionally dependent on the primary key, then the relation will be inFirst normal formSecond normal formThird normal formFourth Normal form