GATE 1996
December 6, 2023Theory-of-Computation
December 6, 2023Theory-of-Computation
| Question 33 |
Which of the following statements is false?
| The Halting problem of Turing machines is undecidable. | |
| Determining whether a context-free grammar is ambiguous is undecidbale. | |
| Given two arbitrary context-free grammars G1 and G2 it is undecidable whether L(G1) = L(G2). | |
| Given two regular grammars G1 and G2 it is undecidable whether L(G1) = L(G2). |
Question 33 Explanation:
Equivalence of regular languages is decidable under
1) Membership
2) Emtiness
3) Finiteness
4) Equivalence
5) Ambiguity
6) Regularity
7) Everything
8) Disjointness
All are decidable for Regular languages.
→ First 3 for CFL.
→ Only 1st for CSL and REC.
→ None for RE.
1) Membership
2) Emtiness
3) Finiteness
4) Equivalence
5) Ambiguity
6) Regularity
7) Everything
8) Disjointness
All are decidable for Regular languages.
→ First 3 for CFL.
→ Only 1st for CSL and REC.
→ None for RE.
Correct Answer: D
Question 33 Explanation:
Equivalence of regular languages is decidable under
1) Membership
2) Emtiness
3) Finiteness
4) Equivalence
5) Ambiguity
6) Regularity
7) Everything
8) Disjointness
All are decidable for Regular languages.
→ First 3 for CFL.
→ Only 1st for CSL and REC.
→ None for RE.
1) Membership
2) Emtiness
3) Finiteness
4) Equivalence
5) Ambiguity
6) Regularity
7) Everything
8) Disjointness
All are decidable for Regular languages.
→ First 3 for CFL.
→ Only 1st for CSL and REC.
→ None for RE.