in Theory of Computation edited by
3,503 views
21 votes
21 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
3.5k views

4 Answers

25 votes
25 votes
Best answer

Answer: A;D.

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

edited by

4 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
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
0

@air1ankit I have some doubt in the above table
 

       1. DCFL closed under reversal?

  1. CSL closed under set difference?
  2. REC under epsilon free substitution?

for 1. formal languages - Are DCFLs closed under reversal? - Computer Science Stack Exchange 

0
0
3 votes
3 votes

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

3 Comments

wat is GSM mapping ??
0
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
2

What is Substitution Operation?

0
0
0 votes
0 votes
A is right

D is right because

$(CFL)^* = Regular$

all regular are CFL’s
0 votes
0 votes

A & D

CFL’s are NOT CLOSED under INTERSECTION, COMPLEMENTATION, DIFFERENCE.

DCFS’s are NOT CLOSED under INTERSECTION, UNION, CONCATENATION, KLEENE CLOSURE, DIFFERENCE, REVERSAL, HOMOMORPHISM.

Answer:

Related questions