The Gateway to Computer Science Excellence
+18 votes
1.7k views

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 context free languages is a context free
  4. The complement of a context free language is a context free
in Theory of Computation by Veteran (52.2k points)
edited by | 1.7k views

2 Answers

+22 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- $\{ ww^r: w \in \Sigma^*$ and $w^r$  is reverse of $w\}$

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

by Active (2.2k points)
edited by
0

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

0

Answer is only (B) because Deterministic push down automata can recognize only deterministic context free languages and cannot recognize non- deterministic context free languages.

Non Deterministic push down automata can recognize all the context free languages(both deterministic and non- deterministic).

You can also refer similar GATE question https://gateoverflow.in/3650/gate2004-it-9?show=4336#a4336.

 

0

The statement in your answer should have been this - "(A) is wrong as a language can be context-free even if it is being not accepted by deterministic PDA for e.g., ...". We don't care whether a CFL is accepted by a non-deterministic PDA or not. Here we concentrate on Deterministic PDA. The key concept here is NDPA ≠ DPDA, i.e., to say NDPA is more powerful than DPDA. 

+2 votes
Ans: B not closed under intersection and complement
by Loyal (7.2k points)

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
50,647 questions
56,504 answers
195,502 comments
100,865 users