GATE CSE 2008 | Question: 10

Question

Which of the following are decidable?

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

• A. I and II
• B. I and IV
• C. II and III
• D. II and IV

Comments

@Pratik2404 Bhaiya,

Whether a given grammar is type 0 / type 1 / type 2 / type 3 -It is decidable because we can write grammar for them and identify

Whether a given grammar is RE L / REC L / CSL / CFL / RL -It is not decidable because we can't write grammar.

Is it correct intuition ?

---

@Tejaswee_Bommaluleni

A grammar can be written in type-0 form, but still generate Regular language. Identifying what type of language a grammar generates is undecidable (except for RE - trivial) 

---

https://youtu.be/8oa4qxMryLQ?t=4020

Answer 1

Lets see options one by one :

1. 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 the start state and that state is either a final state or leading to final state, then the language will be infinite.
    
2. 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
    
3. Now equivalence of two CFLs is also an undecidable property. Hence, given $2$ PDAs which is nothing but characterizing CFLs, whether the $2$ CFLs will be same or not cannot be decided.
    
4. Given a grammar, it is context free iff its productions are of the type $V \to ( V  \cup  \Sigma )^*$ which can be verified with a Turing machine. Hence, it is a decidable property..

Hence, (B) should be correct answer.

Comments

"This can be seen by observing the DFA..If DFA contains a state which contains a loop" there should be a mechanical solution to this problem. we have eyes so we can know that there is a loop in DFA but how a m/c will recognize it?

---

@chauhansunil20th https://www.geeksforgeeks.org/detect-cycle-in-a-graph/

Answer 2

(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

Comments

whether a grammar is context-free or not we can determine it by checking for CFG property on the grammar, not by CYK algorithm. The CYK algorithm is used to check whether a given string could be generated by a CFG grammar or not. and YES if it were language instead of grammar that is undecidable.

---

@Nitesh Singh 2 @gatecse, 

I can understand, we can check a Grammar is CFG or not.

But, I can’t understand, why is it mentioned,

Obviously undecidable had it been language instead of grammar

 

---

same doubt as Mohank

Answer 3

Answer – B ( 1^st and 4^th )

as we know, every thing is decidable for regular languages.

and for CFL only 3 thing are decidable.

1^st) Membership Problems ( Whether the given rammer is CFL )

2^nd ) Emptiness problem ( The given language is empty or not)

3^rd ) Finitness Problem( Means the given language is finte or not).