Consider the following decision problems (P₁) Does a given finite state…
2000
Consider the following decision problems
(P₁) Does a given finite state machine accept a given string
(P₂) Does a given context free grammar generate an infinite number of strings
Which of the following statements is true?
- A.
Both (P₁) and (P₂) are decidable
- B.
Neither (P₁) nor (P₂) are decidable
- C.
Only (P₁) is decidable
- D.
Only (P₂) is decidable
Attempted by 13 students.
Show answer & explanation
Correct answer: A
Membership problem in Finite State mechine is Decidable.
infiniteness probelm in CFG is also a decidable Problem.
P1: Does a given finite state machine accept a given string?
This is the membership problem for FSM/DFA/NFA.
How to solve:
Start from initial state.
Simulate the machine on the input string.
After reading all symbols, check whether final state is accepting.
This always finishes in finite time (linear in string length).
So P1 is decidable ✅
P2: Does a given context-free grammar generate an infinite number of strings?
This is also a known decidable problem.
Idea:
A CFG generates infinitely many strings iff there exists a productive cycle (a variable can derive itself while producing some terminals), allowing arbitrarily long strings.
Algorithm exists:
Remove useless variables.
Convert to normal form (e.g., CNF).
Check for cycles among productive nonterminals.
This can always be done in finite time.
So P2 is decidable ✅
A video solution is available for this question — log in and enroll to watch it.