What if given grammar is ambiguous?

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+23 votes

Which of the following are decidable?

- Whether the intersection of two regular languages is infinite
- Whether a given context-free language is regular
- Whether two push-down automata accept the same language
- Whether a given grammar is context-free

- I and II
- I and IV
- II and III
- II and IV

+15 votes

Best answer

Lets see options one by one :

- The language here will be regular as intersection of regular languages will lead to regular language only..And we know that given a regular language , whether it is finite or not is a decidable problem..This can be seen by observing the DFA..If DFA contains a state which contains a loop and that state is reachable from start state and that state is either a final state or leading to final state , then the language will be infinite..

- The regularity property is undecidable for context free languages..Hence it is undecidable..Details regarding this : https://cs.stackexchange.com/questions/19482/why-is-deciding-regularity-of-a-context-free-language-undecidable

- Now equivalence of two CFLs is also undecidable property..Hence given $2$ PDAs which is nothing but characterising CFLs , whether the $2$ CFLs will be same or not cannot be decided..

- Given a grammar , it is context free iff its productions are of the type V --> ( V U Σ )* .....Hence it is a decidable property..

**Hence, B) should be correct answer..**

+18 votes

(1) Intersection of two regular languages is regular. And checking if a regular language is infinite is decidable.

(2) Undecidable

(3) Undecidable

(4) Decidable as we just have to check if the grammar obeys the rules of CFG. (Obviously undecidable had it been language instead of grammar)

Reference: http://gatecse.in/wiki/Grammar:_Decidable_and_Undecidable_Problems

(2) Undecidable

(3) Undecidable

(4) Decidable as we just have to check if the grammar obeys the rules of CFG. (Obviously undecidable had it been language instead of grammar)

Reference: http://gatecse.in/wiki/Grammar:_Decidable_and_Undecidable_Problems

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.2k
- Digital Logic 2k
- Programming & DS 3.7k
- Algorithms 3.2k
- Theory of Computation 4k
- Compiler Design 1.6k
- Databases 3k
- CO & Architecture 2.6k
- Computer Networks 3k
- Non GATE 1k
- Others 1.3k
- Admissions 488
- Exam Queries 436
- Tier 1 Placement Questions 18
- Job Queries 56
- Projects 9

36,204 questions

43,662 answers

124,118 comments

42,949 users