GATE CSE 2000 | Question: 2.9

Question

Consider the following decision problems:

$(P1):$ Does a given finite state machine accept a given string?

$(P2):$ Does a given context free grammar generate an infinite number of strings?

Which of the following statements is true?

• A. Both$(P1)$ and $(P2)$ are decidable
• B. Neither $(P1)$ nor $(P2)$ is decidable
• C. Only $(P1)$ is decidable
• D. Only $(P2)$ is decidable

Comments

p2, convert cfg to cnf

now you can say it is decidable

---

Know the “Reason” behind every answer. Watch the following Video Solution.

Detailed Video Solution, with Proof of Both Statements

---

For P1 just run it on NFA or DFA if reachable then accept otherwise reject.

Answer 1

For $P1$, we just need to give a run on the machine. Finite state machines always halts unlike TM.

For$ P2$, check if the $CFG$ generates any string of length between $n$ and $2n-1$, where $n$ is the pumping lemma constant. If So, $L(CFG)$ is infinite, else finite. Finding the pumping lemma constant is not trivial - but there are other procedures which can do this - http://cs.stackexchange.com/questions/52507/is-it-decidable-whether-a-given-context-free-grammar-generates-an-infinite-numbe/52520

Hence, both $P1$ and $P2$ are decidable - answer is (A).

http://gatecse.in/wiki/Grammar:_Decidable_and_Undecidable_Problems

Comments

the first one is membership property of regular grammer and second one is the finiteness problem of CFG

 https://gatecse.in/grammar-decidable-and-undecidable-problems/

---

Problem: Given a CFG $G$, decide if $L(G)$ is infinite.

Algorithm:

Convert $G$ into Chomsky Normal Form(CNF) (this can be done Algorithmically).

Now that $G$ is in Chomsky normal form with no unit productions, no useless symbols and no nullable symbols. Recall that in Chomsky normal form, all productions are of the form $A → a, A → BC$.

Create the “Reachability” graph from CNF $G$. Let $H$ be a graph with vertices $V$. Draw an arrow $A → B$ and $A → C$ for each production $A → BC$.

Then $L(G)$ is infinite if and only if $H$ has some cycle.

Since, there exists an Algorithm to determine if a CFG generates an Infinite language, it is a Decidable problem.

https://www.classes.cs.uchicago.edu/archive/2015/winter/28000-1/Lec11.pdf 

---

we can convert that CFG into CNF
which ofcourse have finite number of transitions n by its defination
if it stops it should stop with in 2n-1 steps or else it will never stop because it loops itself
based on pigeon hole principle
so , it is decidable

Answer 2

• P1; membership problem of DFA is decidable.

• p2: finiteness problem of CFG ia also decidable