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.5k points)
edited by | 494 views

2 Answers

+14 votes
Best answer

Answer: a, d.

Context Free languages are not closed under intersection and complementation.

answered by Boss (34.1k 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.4k 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.

Related questions

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

37,072 questions
44,646 answers
43,699 users