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

Which of the following statements is true?

  1. If a language is context free it can always be accepted by a deterministic push-down automaton
  2. The union of two context free languages is context free
  3. The intersection of two contest free languages is a context free
  4. The complement of a context free language is a context free
asked in Theory of Computation by Veteran (68.8k points)
edited by | 769 views

2 Answers

+20 votes
Best answer

Answer is (B)

(A) is wrong as a language can be context free even if it is being accepted by non deterministic PDA for ex- { WWr: W ∈ ∑*(a,b) and W is reverse}

(C) and (D) not always true as Context free languages are not closed under Complement and Intersection.

answered by Active (2.2k points)
selected by

I think example of A is wrong ... it will be { WWr  :  W ∈(a,b)and W is reverse} ... correct me if i am wrong ...

Edit : { WWr  :  W ∈(a,b)and W is reverse}  ... both r npda .... My mistake ...

+2 votes
Ans: B not closed under intersection and complement
answered by Boss (7.4k points)

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

32,442 questions
39,188 answers
36,561 users