now you can say it is decidable

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?

- Both$(P1)$ and $(P2)$ are decidable
- Neither $(P1)$ nor $(P2)$ is decidable
- Only $(P1)$ is decidable
- Only $(P2)$ is decidable

### 1 comment

## 2 Answers

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

### 13 Comments

For a CFG, we can have dependency graph based on the given productions and if in case the dependency graph contains CYCLE, we can say it is infinite else Finite.

Ex:

S-> AB

A -> aC / a

C -> aA / b

B -> a.

For the above CFG, dependency graph contains CYCLE between A and C, hence it is infinite.

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/