###### Question 8816 – Theory-of-Computation

May 4, 2024###### Question 8829 – Theory-of-Computation

May 4, 2024# Question 8828 – Theory-of-Computation

Which of the following problems are decidable?

1) Does a given program ever produce an output?

2) If L is a context-free language, then, is also context-free?

3) If L is a regular language, then, is also regular?

4) If L is a recursive language, then, is also recursive?

Correct Answer: D

Question 25 Explanation:

The statement “Does a given program ever produce an output?” is same as the statement “Does a Turing Machine will halt for any arbitrary string?”, which is nothing but the “halting problem of Turing Machine”, hence statement 1 is undecidable.

Context free languages are not closed under complement operation, so compliment of CFL may or may not be CFL. Hence statement 2 is also undecidable.

Complement of Regular languages is also regular. Since a DFA that accepts the complement of L, i.e. ∑* – L, can be obtained by swapping its final states with its non-final states and vice-versa. Hence it is decidable and if L is a regular language, then, L must also be regular.

Recursive languages are closed under complement, so if L is a recursive language then L must also be recursive, hence it is decidable.

Context free languages are not closed under complement operation, so compliment of CFL may or may not be CFL. Hence statement 2 is also undecidable.

Complement of Regular languages is also regular. Since a DFA that accepts the complement of L, i.e. ∑* – L, can be obtained by swapping its final states with its non-final states and vice-versa. Hence it is decidable and if L is a regular language, then, L must also be regular.

Recursive languages are closed under complement, so if L is a recursive language then L must also be recursive, hence it is decidable.

1, 2, 3, 4

1, 2

2, 3, 4

3, 4

Subscribe

Login

0 Comments