in Theory of Computation edited by
2,554 views
19 votes

Context-free languages are:

  1. closed under union
  2. closed under complementation
  3. closed under intersection
  4. closed under Kleene closure
     
in Theory of Computation edited by
2.6k views

Subscribe to GO Classes for GATE CSE 2022

3 Answers

24 votes
 
Best answer

Answer: A;D.

Context-Free languages are not closed under intersection and complementation.

edited by

3 Comments

CFG are closed under Union , Kleen closure & Concatenation .

Also CFG are closed under Regular intersection

BUT , are CFG closed under Regular Union ?

I think yes...coz..every regular is CFG & CFG are closed under union ....

correct me if I am wrong
1
So take two regular language sigma* over {a,b} and other as {a}then their union is sigma* ,which is not cf.

Correct me if I am wrong.
0
2 votes

According to the above table we can say , A and D is correct answer

3 Comments

wat is GSM mapping ??
0

Gsm mapping Short for generalized sequential machine mapping. A function that is the response function of a generalized sequential machine, and therefore generalizes the notion of sequential function. Without constraining the machine to have a finite state-set, generalized sequentiality is equivalent to the following property of initial subwords preservation

for all u,v in I*, f(uv) has the form f(u)w for some w in O*, where I* and O* are the sets of all input and output strings.

2

What is Substitution Operation?

0
0 votes
A is right

D is right because

$(CFL)^* = Regular$

all regular are CFL’s
Answer:

Related questions