Global Web Forum

husnain

Administrator

From: Chichawatni,Pakistan

Registered: 2014-10-03

Posts: 8,129

Website

Infinite Number:

Mathematics Quizzes Computation Theory

Question:
We have decision problems P1 and P2 as described below:
P1: Does a given finite state machine accept a given string?
P2: Does a given context-free grammar generate an infinite number of strings?

The statement that holds true for P1 and P2 is:

Option A):
Neither P1 nor P2 are decidable
Option B):
Only P2 is decidable
Option C):
Both P1 and P2 are decidable
Option D):
Only P1 is decidable

Correct Answer is Option C):
Both P1 and P2 are decidable

---

You cannot discover the new oceans unless you have the courage to lose the sight of the shore.