edited by
10,022 views
26 votes
26 votes

Which of the following problems are undecidable?

  1. Membership problem in context-free languages.
  2. Whether a given context-free language is regular.
  3. Whether a finite state automation halts on all inputs.
  4. Membership problem for type $0$ languages.
edited by

2 Answers

Best answer
32 votes
32 votes
  1. Membership problem in context-free languages. is Decidable.
  2. Whether a given context-free language is regular. Undecidable [ Regularity is decidable till DCFL class]
  3. Whether a finite state automation halts on all inputs. Decidable
  4. Membership problem for type $0$ languages. Undecidable [undecidable for RE or semi-decidable]

Ref : http://gatecse.in/grammar-decidable-and-undecidable-problems/

edited by
16 votes
16 votes

Let us see each of the options one by one..

A) is decidable as we have various  membership algos for CFL class of languages like CYK algo , LL(k) and LR(k) parsing algos etc..In fact the upper bound to determine if a string belongs to a CFL is given by O(n3) in worst case scenario by CYK algorithm and in some cases we have best case as O(n) as is the case of S - grammar..

B)  Let us assume that a CFL is regular..For that we have to establish the fact that there exists some regular language L2 for CFL L1 ..The equivalence can be written mathematically as :

        L1 ⊕ L2  =  Φ = L3 (say)

==> (L1 - L2)  U  (L2 - L1) = Φ

Thus if we are able to establish L3 to be empty is decidable, then our claim will be true..

Now we concentrate on the 2nd term we are performing L2 - L1 which can be written as : L2 ⋂ L1'

Now L1 being a CFL we know is not closed under complementation..So we go up the Chomsky hierarchy for the sake of generality and now hence we push L1 to CSL level..

Now L2 is regular and L1' is a CSL for sure..So the 2nd term will also be a CSL and the first term (L1 - L2) will be a CFL..

But to do union , we push the 1st term up to CSL level , hence L1 - L2 be CSL..Now union of 2 CSL is a CSL..

Hence the resultant language L3 is a CSL..

But we know emptyness problem for CSL is undecidable..

Hence our assumption was false..

Hence it is proved that the regularity of CFL is undecidable..

C) Now coming to C).This is a trivial problem as finite state automation is an specific case of halting turing machine with limited power..Hence it is decidable problem..

D) Type 0 language means recursively enumerable language..But all recursively enumerable languages are not recursive and hence cannot be necessarily modelled by Halting Turing Machine..So possibility is that for some cases of rejection of input , the Turing Machine will not halt..Thus making the membership property undecidable for RE languages..

Therefore the correct answers are B) and D)

Answer:

Related questions

18 votes
18 votes
7 answers
2
makhdoom ghaya asked Nov 27, 2016
3,599 views
Which of the following well-formed formulas are equivalent?$P \rightarrow Q$$\neg Q \rightarrow \neg P$$\neg P \vee Q$$\neg Q \rightarrow P$
32 votes
32 votes
8 answers
3
makhdoom ghaya asked Nov 27, 2016
11,833 views
Context-free languages and regular languages are both closed under the operation (s) of :UnionIntersectionConcatenationComplementation
10 votes
10 votes
3 answers
4
makhdoom ghaya asked Nov 29, 2016
1,586 views
Show that {NOR} is a functionally complete set of Boolean operations.