3,503 views

Context-free languages are:

1. closed under union
2. closed under complementation
3. closed under intersection
4. closed under Kleene closure

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

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
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.

@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?

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

wat is GSM mapping ??

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.

What is Substitution Operation?

A is right

D is right because

$(CFL)^* = Regular$

all regular are CFL’s
by

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.