The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+14 votes

02. Choose the correct alternatives (more than one may be correct) and write the corresponding letters only:

(xix) Context-free languages are

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


asked in Theory of Computation by Veteran (59.4k points)
edited by | 450 views

2 Answers

+14 votes
Best answer

Answer: a, d

Context Free languages are not closed under intersection and complementation.

answered by Boss (34.2k points)
edited by
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 vote


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



answered by Active (3.2k points)
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.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

34,780 questions
41,758 answers
41,400 users