The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+22 votes
1.6k 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
asked in Theory of Computation by Veteran (68.9k points)
edited by | 1.6k views

1 Answer

+19 votes
Best answer

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 - (A).

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

answered by Veteran (332k points)
edited 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?


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

32,693 questions
39,293 answers
110,109 comments
36,701 users