2,170 views
5 votes
5 votes
Which of the following is not decidable problem?
(a) A sting is generated by C.N.F or Not?
(b) A given non-terminal A in a given grammar CFG is ever used in the generation of word
(c) Given context-free Grammar generates an infinite language or a finite language
(d) None of the above

3 Answers

11 votes
11 votes

If we can automate an algorithm to run on a machine so that it can give us answer to the underlying problem or complement of it then the problem is called decidable. More importantly the algorithm must have to stop in finite time.

A) CNF is a form of CFL grammar. Using CNF we need only 2n-1 steps for any derivation of string where n = | string |. This is decidable.

B) This is indirectly asking whether finding useless symbol in CFG is decidable or not ? It is possible to automate this elimination procedure which means decidable.

LINK

C) Finiteness problem of CFL (or CFG) decidable, because we can check the existence of loops in the dependency graph over the non terminals.

ans : D)

Regarding option A) 

  • A string is generated by CNF or Not ?
  • Whether a string belongs to the language generated by a CNF ?

These are two different questions. They have different solutions.

For checking whether a string is generated by a CNF ? => Procedure takes $2n-1$ steps where n is the string length.

On the other hand, 

For checking whether a string belongs to a language generated by a given CNF or CFG ? => CYK algorithm $O(n^{3})$

edited by
5 votes
5 votes

This list of common decidable problems will help you to easily solve such questions!

  • Regular language: {Membership, Emptiness, Finiteness, Equivalence, Everything (Σ*), Ambiguity, Regularity, Disjointedness}
  • Context free language: {Membership, Emptiness, Finiteness}
  • Context sensitive : {Membership }
  • Recursive: {Membership }
  • Recursive Enumerable : None.

In given question,

(a) A sting is generated by C.N.F or Not?  => membership in Context free language; Decidable√
(b) A given non-terminal A in a given grammar CFG is ever used in the generation of word=> Finding useless symbols in CFG is Decidable√
(c) Given context-free Grammar generates an infinite language or a finite language=>Finiteness of a Context free language; Decidable√

0 votes
0 votes
(a) is decidable. Membership problem is decidable in CFG because they have a membership algorithm - CYK algorithm

(b) is decidable. Reason:- Here we need to check if a variable is ever used. i.e. From a given CFG, if we eliminate all useless symbol, all remaining variables can be reached and therefore will be used.

(c) is decidable because finiteness problem is decidable for  CFG's.

(d) is correct.
edited by

Related questions

0 votes
0 votes
0 answers
1
aambazinga asked Sep 8, 2018
422 views
How can we say that any two disjoint co-turing recognisable languages are seperable by some Decidability language?
3 votes
3 votes
3 answers
4
Parshu gate asked Nov 29, 2017
615 views
Suppose in question we are given the language is Turing Decidable , can I consider it a CFL or Regular?