Theory-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.
Subscribe
Login
0 Comments