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) 1 and 2 (B) 1 and 4
(C) 2 and 3 (D) 2 and 4

Answer 1

Answer on Question#38163 – Math – Other

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) 1 and 2 (B) 1 and 4

(C) 2 and 3 (D) 2 and 4

Solution:

2. Whether a given context-free language is regular.

As context-free languages may or may not be regular, hence it's not decidable, so (C) and (D) option can be eliminated

1. Whether the intersection of two regular languages is infinite.

Every regular language supports F.A and can contain only finite number of states, so intersection of two regular language will always be finite, so it's decidable. Hence it's B not D.

II) and III) are not decidable, so (A), (C) and (D) are not true. Correct answer is (B).

Answer: (B) 1 and 4.