For any CFG we can check whether it generates an infinite number of strings. No problem if its language is deterministic or not.

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+24 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?

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

+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

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.

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

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

@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.

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.

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.4k
- Digital Logic 2.1k
- Programming & DS 3.8k
- Algorithms 3.3k
- Theory of Computation 4.1k
- Compiler Design 1.6k
- Databases 3k
- CO & Architecture 2.6k
- Computer Networks 3k
- Non GATE 1.1k
- Others 1.4k
- Admissions 496
- Exam Queries 443
- Tier 1 Placement Questions 19
- Job Queries 59
- Projects 9

37,111 questions

44,694 answers

127,236 comments

43,753 users