edited by
8,894 views
46 votes
46 votes

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?

  1. Both$(P1)$ and $(P2)$ are decidable
  2. Neither $(P1)$ nor $(P2)$ is decidable
  3. Only $(P1)$ is decidable
  4. Only $(P2)$ is decidable
edited by

2 Answers

Best answer
40 votes
40 votes

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

edited by
Answer:

Related questions