The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+24 votes
2k 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 (59.5k points)
edited by | 2k views

1 Answer

+20 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 - answer is (A).

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

answered by Veteran (353k points)
edited by
0
Means?

For any CFG we can check whether it generates an infinite number of strings. No problem if its language is deterministic or not.
+2
Checking if L(G) = ∑* and L(G) is finite are two different problems. The first one is undecidable but second one is decidable.
0
That's given in the above link. You can check that.
0
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
0
TM IS ALSO FSM

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

Can you please explain a bit further...
+1
$n$ is the pumping lemma constant. See the stackoverflow link for exact procedure.
0
P2 is not understood plz explain it other ways
0
@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.
+4
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.
+1
The graph might consist of useless symbols which are not reachable from  start
0
Can anyone explain why problem 2 is not undecidable?
Answer:

Related questions



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

37,111 questions
44,694 answers
127,236 comments
43,753 users