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

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

The Gateway to Computer Science Excellence

+20 votes

Which of the following statements is true?

- If a language is context free it can always be accepted by a deterministic push-down automaton
- The union of two context free languages is context free
- The intersection of two context free languages is a context free
- The complement of a context free language is a context free

+23 votes

Best answer

0

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

Edit : { WW^{r }: W ∈(a,b)^{* }and W^{r } 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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,300 answers

198,290 comments

104,996 users