6,130 views

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

### 1 comment

p2, convert cfg to cnf

now you can say it is decidable

### Subscribe to GO Classes for GATE CSE 2022

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

by

Means?

For any CFG we can check whether it generates an infinite number of strings. No problem if its language is deterministic or not.
Checking if L(G) = ∑* and L(G) is finite are two different problems. The first one is undecidable but second one is decidable.
That's given in the above link. You can check that.
1) it is completeness pb ie whether L(G) is complete language or not it is undecidable for CFL but not for regular because we have an algo to check whether 2 Finite automata are equal (Equivalence pb) but unfortnately we do not have same for CFL or DCFL 2)it is emptyness problem i.e whether L(G) is empty or not it is decidable by simplifying grammar and check if we can derive a string or not? 3) is finiteness pb it is also decidable ,first we reduce our grammar into CNF form and then we check for existing of any loop or self loop.if exist then infinite otherwise finite 4 and 5 can be solved with 3 only
TM IS ALSO FSM

AND SIR I M ALSO NOT GETTING THE 2ND ANS ..PLZ CONSIDER MY DOUBTS
Sir what is n here?

Can you please explain a bit further...
$n$ is the pumping lemma constant. See the stackoverflow link for exact procedure.
P2 is not understood plz explain it other ways
@Hari A language is NP that means there exists a algo for this problem no matter it is polynomial complexity it will decidable. because if you go on decidablility definition says a problem is decidable if there exists a Algo for that.
For the second statement,

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 graph might consist of useless symbols which are not reachable from  start
Can anyone explain why problem 2 is not undecidable?

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