Undecidability

Introduction

In the theory of computation, we frequently encounter such troubles that are answered either 'yes' or 'no'. The class of problems which can be answered as 'yes' are known as solvable or decidable otherwise, the class of problems is said to be unsolvable or undecidable.

Questions

1. Consider the subsequent statements about regular languages:

• S1: Every infinite regular language consists of an undecidable language as a subset.
• S2: Every finite language is regular.

Which one of the following choices is accurate?

(A) Only S1 is true

(B) Only S2 is true

(C) Both S1 and S2 are true

(D) Neither S1 nor S2 is true

Solution: (C) Both S1 and S2 are true.

S1: True. We can construct a subset N of A that we will prove nonregular through the pumping lemma.

S2: True. Every finite language is regular because we will draw DFA for it.

2. Consider the subsequent sets in which n≥2:

S1: Set of n×n matrices with entries from the set {a,b,c}.

S2: Set of all capabilities from the set {0,1,2 … ,n2−1} to the set {0,1,2}

Which of the following preference(s) is/are accurate?

(A) There does not exist an injection from S1 to S2

(B) There exists a bijection from S1 to S2

(C) There exists a surjection from S1 to S2

(D) There does not exist any bijection from S1 to S2

Solution: (B) (C)

S1: We understand that there are n×n positions in the matrix in which each can be filled with either of the values a or b or c, so in total, we've got 3^n×n ways

S2: total number of functions possible from A to B is (Cardinality of B)^Cardinality of A

For ex- |B|= 3 and |A|= n^2-1 +1 = n^2. So in this situation, total functions possible is 3^n×n

So the function is Surjective as well as Bijective correct option- B, C

3. For a Turing machine M, ⟨M⟩ denotes an encoding of M. Consider the following two languages.

L1 = { ⟨M⟩ ∣ M takes more than 2021 steps on all inputs }

L2 = { ⟨M⟩ ∣ M takes more than 2021 steps on some input }

Which of the following options is correct?

(A) Both L1 and L2 are decidable

(B) L1 is decidable and L2 is undecidable

(C) L1 is undecidable and L2 is decidable

(D) Both L1 and L2 are undecidable

Solution: (A) Both L1 and L2 are decidable.

For L1: check if Turing machine M halts within 2021 steps for all inputs of length less than or equal to 2021. If it is not halting within 2021 steps, definitely it is taking more than 2021 steps, so it is decidable.

For L2: Similarly, we can check if Turing machine M halts within 2021 steps for some length inputs less than or equal to 2021. If it is not halting within 2021 steps for some inputs, it takes more than 2021 steps, which is also decidable.

4. Let ⟨M⟩ denote an encoding of an automaton. Suppose that Σ={0,1}. Which of the following given languages is/are NOT recursive?

(A) L = {⟨M⟩ ∣ M is a DFA such that L(M)=∅}

(B) L = {⟨M⟩ ∣ M is a DFA such that L(M)=Σ*}

(C) L = {⟨M⟩ ∣ M is a PDA such that L(M)=∅}

(D) L = {⟨M⟩ ∣ M is a PDA such that L(M)=Σ*}

Solution: (D) L = {⟨M⟩ ∣ M is a PDA such that L(M)=Σ*}

A language 'L' is recursive only if a Turing machine exists that will accept the strings in 'L' and also reject all the strings that are not in 'L'. The Turing machine will halt each time and answer (accepted or rejected) for each string input. A language 'L' is said to be decidable if it is a recursive language.

From the given options, L = {⟨M⟩ ∣ M is a PDA such that L(M)=Σ*} is the completeness problem of CFL, which is undecidable. Hence not recursive.

Given a language L, take its complement L' and check if L' is empty => L is complete.

Since CFLs are not closed under complementation. So, completeness is undecidable for CFL.

5. Which of the following languages are undecidable? Note that ⟨M⟩ indicates the encoding of the Turing machine M.

L1 = { ⟨M⟩ ∣ L(M)=∅ }

L2 = { ⟨M,w,q⟩ ∣ M as input w reaches state q in exactly 100 steps }

L3 = { ⟨M⟩ ∣ L(M) is not recursive }

L4 = { ⟨M⟩ ∣ L(M) contains at least 21 members }

(A) L1, L3, and L4 only

(B) L1 and L3 only

(C) L2 and L3 only

(D) L2, L3, and L4 only

Solution: (A) L1, L3, and L4 only.

L1 = { ⟨M⟩ ∣ L(M)=∅ } is the emptiness problem of TM, which is undecidable by Rice's theorem since it is a non-trivial problem.

L2 = { ⟨M,w,q⟩ ∣ M as input w reaches state q in exactly 100 steps } is decidable as we can run it for 100 steps and see if it reaches its state q.

L3 = { ⟨M⟩ ∣ L(M) is not recursive } is undecidable according to Rice theorem.

L4 = { ⟨M⟩ ∣ L(M) contains at least 21 members } is undecidable. It may or may not halt.

Only L2 is decidable.

6. Which of the following statements is false?

(A) The Halting Problem of Turing machines is undecidable

(B) Determining whether context-free grammar is ambiguous is undecidable

(C) Given two arbitrary context-free grammars, G1 and G2, it is undecidable whether L(G1)=L(G2)

(D) Given two regular grammars, G1 and G2, it is undecidable whether L(G1)=L(G2)

Solution: (D) Given two regular grammars, G1 and G2, it is undecidable whether L(G1)=L(G2)

The halting problem of the Turing Machine is undecidable because there is no algorithm exists for it.

Determining a context-free language is undecidable because no algorithm exists to decide CFG is ambiguous.

The equivalence problem of CFG is undecidable.

Everything about regular language is decidable.

7. Consider the following statements:

1. The complement of Turning decidable language is Turning decidable
2. There exists some language that is in NP but is not in Turing decidable
3. If L is a language that is in NP, then L is Turing decidable 

Which of the given statements is/are True?

(A) Only 2

(B) Only 3

(C) Only 1 and 2

(D) Only 1 and 3

Solution: (D) Only 1 and 3

1 is true: Complement of Turing decidable language is Turing Decidable.

2 is false: The definition of NP says solvable in polynomial time using the non-deterministic Turing machine. 

3 is true. All NP problems are Turing decidable.

8. Consider the following problems:

(P1) Does a finite state machine accept a given string

(P2) Does a given context-free grammar generate an infinite number of stings

Which of the following statements is true?

(A) Both (P1) and (P2) are decidable

(B) Neither (P1) nor (P2) is decidable

(C) Only (P1) is decidable

(D) Only (P2) is decidable

Solution: (A) Both (P1) and (P2) are decidable.

A finite state machine always halts in a final or non-final state. Therefore, problem P1 is decidable.

We check if the context-free language generates any length string between n and (2n – 1). If so, context-free language is infinite else, it is finite. Therefore, problem P2 is decidable.

9. Which of the following problem is undecidable?

(A) Deciding if the given context-free grammar is ambiguous.

(B) Deciding if the language generated by a given context-free grammar is finite.

(C) Deciding if a given string is generated by context-free grammar.

(D) Decide if the language generated by context-free grammar is empty.

Solution: (A) Deciding if a given context-free grammar is ambiguous.

A context-free grammar is not closed under ambiguity. A set is closed under an operation which means when we operate an element of that set with the operator, we get an element from that set.

Here, context-free grammar generates a context-free language, and a set of all context-free languages is also a set, but ambiguity does not consider to be an operation, and hence we can not say that CFG is closed under ambiguity.

10. Consider L to be the encoding of the Turing machine as a string over ∑= {0, 1}. Now, L = { |M is a Turing machine that takes a string of length 2014}. Then, L is

(A) decidable but not recursively enumerable

(B) undecidable but recursively enumerable

(C) decidable and recursively enumerable

(D) undecidable and not recursively enumerable

Solution: (B) undecidable but recursively enumerable

There are a finite number of strings of the length '2014'. So, a Turing machine will take this as an input string of length '2014' and test it.

If an input string is present in the language, the Turing machine will halt in the final state.

But, if the Turing machine cannot accept the input string, it will halt in a non-final state or go into an infinite loop and never halt.

Thus, 'L' is undecidable and recursively enumerable.

11. Which of the following problems is undecidable?

(A) Membership problem for CFGs

(B) Ambiguity problem for CFGs.

(C) Finiteness problem for FSAs.

(D) Equivalence problem for FSAs.

Solution: (B) Ambiguity problem for CFGs.

A set is closed beneath an operation means when we perform an element of that set with the corresponding operator, we get an element from that set.

Here, CFG generates a CFL, and the set of all CFLs is the set. But ambiguity isn't always an operation, and as a result, we can never say that CFG is closed below such operation.

Best ambiguity problems for CFGs are undecidable.

12. Given ∑ = {a, b}, which of the following sets is not countable?

(A) Set all strings over ∑

(B) Set of all languages over ∑

(C) Set of all languages over ∑ accepted by Turing machines

(D) Set of all regular languages over ∑

Solution: (B) Set all languages over ∑

(A) The set ∑ ={a, b} is countable because each element of this set can be mapped with the natural number and also generated in the following order:

Given ∑ ={a, b}. So, order will be a,b,aa,ab,ba,bb,aaa,aab … Therefore it will mapped with natural number. Hence it is countable.

(B) Here, we see that a set of languages over z is the power set of strings over ∑ an infinite set, and As we know, that power set of an infinite set is uncountable. Hence the set of languages becomes an uncountable set, so we can prove this is using Cantor's diagonalization method.

(C) The set of all languages ∑ accepted by the Turing machine is countable.

(D) The set of all regular languages is a subset of all recursively enumerable languages. And we know that a subset of a countable set is always countable.

 

You can also read about Greibach Normal Form here.