## 10

## Computability and Undecidability

#### Introduction

According to the Church thesis, the algorithm of any computational procedure can be represented by the Turing machine (TM). Are there some problems for which there are no algorithms to solve the problem? This question divides the set of problems into two parts, namely, decidable and undecidable. If there exists an algorithm to solve a problem, the problem is called decidable; otherwise, it is undecidable. Before discussing undecidability, it is needed to know about the languages accepted by the TM.

#### 10.1 TM Languages

A string w is said to be accepted by a TM if it gets halt(H). What happens if it does not get halt? It may happen that for the current state q and the current input symbol ∈ Σ, no transitional function is defined or it can run forever without getting halt. For the first case, the string w does not belong to the defined TM. But, the second case creates an interesting situation.

Let us consider a TM with the transitional functions as follows.

Let us take three input strings, null, ‘aa’, and ‘a’.

- The null string is accepted because the machine gets ‘B’, enters state q
_{f}, and halts. - For the string ‘aa’, the first ‘a’ is traversed replacing ‘a’ by X. For the second ‘a’, it enters into q
_{4}and halts. So, ‘aa’ is rejected by the defined TM. - For the string ‘a’, the machine runs without halting. The fate of the string ‘a’ is not decided by the TM.

From the previous discussion, it can be concluded that for a TM, there are two types of languages.

- A TM acceptable or recursively enumerable
- Recursive language or Turing decidable.

#### 10.1.1 Turing Acceptable

A language L is Turing acceptable or Turing recognizable or recursively enumerable if there is a TM that halts and accepts L or halts and rejects or loop for an infinite time.

In notation, it can be represented as follows.

For a string w,

or

For a Turing acceptable language, there may exist a TM which halts on a large set of input string w, where w ∈ L, but there must exist at least one string w ∉ L for which the TM does not halt.

Pictorially, a recursively enumerable language can be represented as in Fig 10.1.

**Fig. 10.1** Turing Acceptable Language

Sometimes, a situation may appear when for some cases it can be said confirm that the string is accepted, but whether the string is not accepted cannot be decidable.

Consider a TM which finds a symbol X on the tape and halts.

The machine will search for the symbol X by traversing the symbols B. If it finds, it will halt. The transitional functions are

_{0}, B) → (q

_{0}, B, R)

_{0}, X) → (q

_{f}, H)

If a string BBXBBB is taken, the machine can easily detect the symbol and halts. But if the input tape does not contain any X, then the machine will run infinitely. This is called the semi-decidability of the TM.

#### 10.1.2 Turing Decidable

A language L is called Turing decidable (or just decidable), if there exists a TM M such that on input x, M accepts if x ∈ L, and M rejects otherwise. L is called undecidable if it is not decidable.

The decision problems always answer in yes or no. Another important property of decision problems is that, for the problem, the TM must halt.

Let there be a problem of checking whether a number X is prime or not. The algorithm for the problem is:

** Step 1:** Take the number X as input.

** Step 2:** Divide the number X by all integer numbers from 2 to .

** Step 3:** If any of the numbers divide X, then reject. Otherwise accept.

** Step 4:** stop

Already it is discussed that if there exists an algorithm for a problem, the corresponding TM can be constructed.

For this case, if an integer X is taken as input it can be said in yes or no whether the integer is prime or not. So, this problem is a Turing decidable problem.

Pictorially, a Turing decidable language or recursive language can be represented in Fig. 10.2.

**Fig. 10.2** Turing Decidable Language

If a language L is recursive, then it is a recursively enumerable language. The TM for the recursive language halts and accepts a string if it belongs to the language set L and halts and rejects if the string does not belong to L. These conditions are satisfied for a recursively enumerable language also. So, all recursive languages are recursively enumerable.

The difference between recursive and recursively enumerable language is that the TM will halt for recursive language but may not halt (loop infinitely) for recursively enumerable language.

This is described in Fig. 10.3.

**Fig. 10.3** Relation of Recursive and Recursively Enumerable

#### 10.2 Unrestricted Grammar

This term was first mentioned in the language and grammar chapter. In the chapter Turing machine, we have learned that unrestricted grammar is accepted by the TM. The term ‘unrestricted’ signifies that the grammar is not restricted. Here, restriction means the appearance of non-terminal and terminal symbols at both sides.

*Definition:**A grammar (V _{N}*, Σ,

*P, S) is called an unrestricted grammar if all its productions are in the form LS*→

*RS, where LS*∈

*(V*∪ Σ

_{N}*)*∈

^{+}and RS*(V*∪ Σ

_{N}*)**.

In an unrestricted grammar, any combination of terminal and non-terminal can appear at both ends of the production rule. The only restriction is that the null string (λ) cannot appear at the left hand side of the production rule. (Notice for LS, it is + not *.) In the Chomsky hierarchy, type 0 or unrestricted grammar is the superset of all grammars, and thus it accepts more languages than type 1 or other grammars.

Already it is mentioned that unrestricted grammar is accepted by the TM, and the language accepted by a TM is called recursively enumerable language. In the following section, we shall discuss the relation between unrestricted grammar and recursively enumerable language.

** Theorem 10.1:** Any language set generated by an unrestricted grammar is recursively enumerable.

** Proof:** Let G = (V

_{N}, Σ, P, S) be an unrestricted grammar. A grammar defines a set of procedures for enumerating all strings ∈ L(G).

- List all w ∈ L(G) such that w is derived from the production rules P in one step. As S is the start symbol, we can write that w is the set of strings derived from S in one step. Symbolically, it can be written as S → w.
- List all w ∈ L(G) such that w is derived from the production rules P in two steps. We can write it as S → x → w.

By the process, the derivation progresses.

If S be the set of all strings, then an enumeration procedure for S is a TM that generates all strings of S one by one in a finite amount of time. If, for a set, there exists an enumeration procedure, the set is countable. The set of strings generated by an unrestricted language is countable. Thus, the derivation procedures can be enumerated on a TM.

Hence it is proved that the language generated by an unrestricted grammar is recursively enumerable.

#### 10.2.1 Turing Machine to Unrestricted Grammar

A TM accepts type 0 languages. Type 0 language is generated by type 0 grammar. Type 0 grammar can be constructed directly from the TM’s transitional functions. The rules are discussed in the following.

Let the string to be traversed by a TM M be S which is enclosed between two end markers ψ S $. Note that the IDs are enclosed within brackets. The acceptance of the string S by M means the transformation of ID from [q_{0}ψ S $] to [q_{f}B]. Here, q_{0} is the initial state and q_{f} is the final or halt state. The length of the ID may change if the read–write head of the TM reaches the left hand side or right hand side brackets. Thus, the productions rules of the grammar equivalent to the transition of ID are divided into two steps: (i) no change in length and (ii) change in length. Assume that the transition table is given as follows.

**No change in length:****– Right move:**If there is a transitional functionδ(q_{i}, a_{j}) → (q_{k}, a_{l}, R)of the TM, then the equivalent production rule of the grammar is

q_{i}a_{j}→ a_{l}q_{k}**– Left move:**If there is a transitional functionδ(q_{i}, a_{j}) → (q_{k}, a_{l}, L)of the TM, then the equivalent production rule of the grammar is in the form

a_{p}q_{i}a_{j}→q_{k}a_{p}a_{l}for all a_{p}∈ Γ(If there are n allowable tape symbols, then for a left movement production n transitional functions are added to the production rule.)

**Change in length:****– Left bracket****‘[‘ at the left end:**If there is a productionδ(q_{i}, a_{j}) → (q_{k}, a_{l}, L)TM going to traverse the left boundary ’[‘): then the production

[q_{i}a_{j}→q_{k}Ba_{l}is added to the production rule. (Here B represents the blank.)

If B appears next to the left bracket, it can be deleted by the production

[B → [**– Right bracket ‘]‘ at the right end:**If B appears just before ‘]’, then it can be deleted by the productiona_{p}B] → a_{p}] for all a_{p}∈ ΓIf TM going to traverse to the right of ‘]’, then the length is increased due to the insertion of B. The productions are

q_{i}] → q_{i}B] for all q_{i}∈ Q- The string is confined by two end markers ψ and $. To introduce the end markers, the following productions are added.
To remove brackets ‘[‘ and ‘]’ from [q

_{f}B], the following production is added,[q_{f}B] → SHere, S is the start symbol of the grammar.

- Now, reverse the direction of the arrow in the transitional functions. The generated production rules are the production rules of the grammar. The grammar obtained in this process is called generative grammar.

#### Example 10.1

Consider a TM with the following transitional functions. (This is the TM for 1’s complement.) Convert this to an equivalent type 0 grammar.

*Solution:*

- For the transitional function δ(Q
_{0}, 0) → (Q_{0}, 1, R), the production rule isQ_{0}0 → 1Q_{0}For transitional function δ(Q

_{0}, 1) → (Q_{0}, 0, R), the production rule isQ_{0}1 → 0Q_{0}For transitional function δ(Q

_{0}, B) → (Q_{f}, B, R), the production rule isQ_{0}B → 0Q_{f} - The production rule corresponding to the left end is
[B → [
The production rules corresponding to the right end are

- The production rules for introducing end markers are
By reversing the direction of the arrow, the productions become

#### Example 10.2

Consider a TM with the following transitional functions. (This is the TM which accepts an even string of ‘a’.) Convert this to an equivalent type 0 grammar. Check it for the string ‘aa’.

Input | ||
---|---|---|

State | a | B |

Q _{0} | Q _{1}, B, R | |

Q _{1} | Q _{0}, B, R |

where Q_{0} is the initial and final state.

*Solution:*

- For transitional function δ(Q
_{0}, a) → (Q_{1}, B, R), the production rule isQ_{0}a →BQ_{1}For the second transitional function δ(Q

_{1}, a) → (Q_{0}, B, R), the production rule isQ_{1}a →BQ_{0} - The production rule corresponding to the left end is
[B → [
The production rules corresponding to the right end are

- The production rules for introducing end markers are
By reversing the direction of the arrow, the productions become

** Checking:** The string is ‘aa’. It means from S we have to produce [Q

_{0}ψaa$].

#### 10.2.2 Kuroda Normal Form

The Kuroda normal form is related to unrestricted and context-sensitive grammar. Sige-Yuki Kuroda, a Japanese linguist, proposed this normal form related to context-sensitive grammar. Since then, this is named after her.

** Definition:** A grammar is in Kuroda normal form if and only if all production rules of it are in the form

where A, B, and C are non-terminals and ‘a’ is terminal.

#### 10.2.3 Conversion of a Grammar into the Kuroda Normal Form

Consider G_{1} = {V_{N1}, Σ, P_{1}, S} as a context-sensitive grammar which does not produce ∈. An equivalent grammar G_{2} = {V_{N2}, Σ, P_{2}, S} in the Kuroda normal form can be constructed from G_{1} using the following rules.

- Replace all terminals T∈G
_{1}by a new production A_{r}→ T and add them to G_{2}. - For each production in the form A → A
_{1}A_{2}. . . . A_{k}in G_{1}, add a new production A → A_{1}B_{1}in G_{2}where B_{i}→ A_{i + 1}B_{i + 1}for i = 1, 2 . . . . k – 3 and the terminating condition isB_{k – 2}→ A_{k – 1}A_{k} - For each production in the form A
_{1}A_{2}. . . . A_{m}→ B_{1}B_{2}. . . . B_{k}, where 2 ≤ m ≤ k ≥ 3, the following new productionsare added to G

_{2}.

#### 10.3 Modified Chomsky Hierarchy

In the grammar and language chapter, we learned about the Chomsky hierarchy. There, the type 0 language was mentioned as an unrestricted language which is accepted by the TM. While discussing the Turing language, we have learned that this language is called the recursively enumerable language. A recursive language is a subset of the recursively enumerable language. Thus, type 0 language is divided into two parts, namely recursively enumerable language and recursive language. The modified Chomsky hierarchy is given in Fig. 10.4.

**Fig. 10.4** Modified Chomsky Hierarchy

#### 10.4 Properties of Recursive and Recursively Enumerable Language

**The union of two recursive languages is recursive.**Let L*Proof:*_{1}and L_{2}be two recursive languages, so there exist two TMs, say T_{1}and T_{2}accepting L_{1}and L_{2}, respectively. Let us construct a new TM M by combining T_{1}and T_{2}as given in Fig. 10.5. A string w is given as input to T_{1}; if it accepts, then M accepts. If it rejects, then the same input is given as input to T_{2}; if it accepts, then M accepts. From the discussion, it is clear that M accepts L_{1}∪ L_{2}.**Fig. 10.5**Union of Two Recursive LanguagesAs there exists a TM for L

_{1}∪ L_{2}which guarantees to halt, it is thereby proved that L_{1}∪ L_{2}is recursive.**The union of two recursively enumerable languages is recursively enumerable.**Let L*Proof:*_{1}and L_{2}be two recursively enumerable languages, so there exist two TMs, say T_{1}and T_{2}accepting L_{1}and L_{2}, respectively. Let us construct a new TM M by combining T_{1}and T_{2}as denoted in Fig. 10.6.**Fig. 10.6**Union of Two Recursive Enumerable LanguagesA string w is accepted by M if it is accepted by either T

_{1}or T_{2}. Acceptance by either T_{1}or T_{2}means accepting L_{1}∪ L_{2}. If w is not accepted by both T_{1}and T_{2}, then the machine M has no guarantee to halt. It proves that L_{1}∪ L_{2}is recursively enumerable.**The intersection of two recursive languages**is**recursive.**Let L*Proof:*_{1}and L_{2}be two recursive languages, so there exist two TMs, say T_{1}and T_{2}accepting L_{1}and L_{2}, respectively. Let us construct a new TM M by combining T_{1}and T_{2}as given in Fig. 10.7.**Fig. 10.7**Intersection of Two Recursive LanguagesA string w is accepted by M if it is accepted by both T

_{1}and T_{2}, and rejected if any of them reject. From the discussion it is clear that M accepts L_{1}∩ L_{2}. As there exists a TM for L_{1}∩ L_{2}which guarantee to halt; thereby proving that L_{1}∩ L_{2}is recursive.Algorithmically, it can be written as

**The intersection of two recursively enumerable languages is recursively enumerable.**It can be proved similar to the previous property, excluding the rejection part as given in Fig. 10.8.

**Fig. 10.8**Intersection of Two Recursively Enumerable Languages**The complement of a recursive language is recursive.**Let L be a recursive language, so there exists a TM T*Proof:*_{m}accepting L. T_{m}guarantees to accept and halt for any string w ∈ L and reject and halt for any string w ∉ L.Let us construct another TM T′

_{m}which simulates M on w; if T_{m}accepts w, then T′_{m}rejects it and if T′_{m}rejects w, then T′_{m}accepts it as shown in Fig. 10.9.**Fig. 10.9**Complement of Two Recursive LanguagesClearly, T'

_{m}is the complement of T_{m}. As it halts on all possible inputs and accepts the complement of L, it is proved that the complement of a recursive language is recursive.**If a language and its complement both are recursively enumerable, then both the language and its complement are recursive.**Let L and its complement L′ be recursively enumerable languages, so there exist two TMs, say T*Proof:*_{1}and T_{2}accepting L and L′, respectively. Let us construct a new TM M which simulates T_{1}and T_{2}simultaneously, accepting a string w if T_{1}accepts it and rejecting a string w if T_{2}accepts it, as denoted in Fig. 10.10.**Fig. 10.10**Thus, M will always halt and answer in ‘yes’ or ‘no’. As M guarantees to halt for all possible inputs, L is recursive.

Already it is proved that the complement of a recursive language is recursive, thus proving L′ is recursive.

*(Note that the recursively enumerable languages are not closed under complementation. If an RE language is closed under complementation, it is recursive.)***The concatenation of two recursively enumerable languages is recursively enumerable.**Let L*Proof:*_{1}and L_{2}be two recursively enumerable languages, so there exist two TMs, say, T_{1}and T_{2}accepting L_{1}and L_{2}, respectively. Design a machine M to accept L_{1}L_{2}whose operation is performed by the following algorithm.Let W ∈ L

_{1}L_{2}. Guess a number n between 0 and | W |. Break W into W_{1}and W_{2}such that W = W_{1}W_{2}and | W_{1}| = n and | W_{2}| = | W | – n.Set counter i = 0 with one increment up to | W |.

{

Run W

_{1}on T_{1}for n stepsRun W

_{2}on T_{2}for next | W | – n steps.}

If (T

_{1}accept W_{1}and T_{2}accept W_{2})Declare accept

M accepts if the substrings L

_{1}and L_{2}are accepted by T_{1}and T_{2}, respectively. Hence L_{1}L_{2}is recursively enumerable. This is described in Fig. 10.11.**Fig. 10.11**Concatenation of Two Recursively Enumerable Languages**The concatenation of two recursive languages is recursive.**Let L*Proof:*_{1}and L_{2}be two recursive languages, so there exist two TMs, say T_{1}and T_{2}accepting L_{1}and L_{2}, respectively. Design a machine M to accept L_{1}L_{2}whose operation is performed by the following algorithm.Let W ∈ L

_{1}L_{2}. Guess a number n between 0 and | W |. Break W into W_{1}and W_{2}such that W = W_{1}W_{2}and | W_{1}| = n and | W_{2}| = | W_{1}W_{2}| – n.Set counter i = 0 with one increment upto | W |

Run W

_{1}on T_{1}for n stepsif (T

_{1}halts and accept W_{1})Run W

_{2}on T_{2}for next | W | stepsif (T

_{2}halts and accept W_{2})Declare accept

Else reject

Else reject

M accepts if the substrings W

_{1}and W_{2}are accepted by T_{1}and T_{2}, respectively, and rejects if any of T_{1}and T_{2}rejects it. Hence, L_{1}L_{2}is recursive.**The Kleene-star operation on a recursively enumerable language is recursively enumerable.**Let L be a recursively enumerable language accepted by the TM T. We have to prove that L* is also recursively enumerable. Design another TM M to accept L* whose operation is performed by the following algorithm.*Proof:*Let W ∈ L*. On input W to M.

If W = λ (null) accept

If W ≠ λ

Consider a number n between 1 and | W |

Consider n different numbers NUM

_{k}(k = 0 to n) between 0 and | W | to break the string W into substrings w_{1}w_{2}. . . w_{n}.Set another counter i = 0 and start it.

Set a counter j = 0 with 1 increment up to NUM

_{k}{

Run T on w

_{i}for j stepsIf (T halts and accept w

_{i})Increment i by 1

}

If(j = = n)

[T accepts each substring w

_{i}(i = 1 to n)]declare accept

M halts and accepts L* if each of w

_{1}w_{2}…w_{n}are accepted by T. Hence, L* is recursively enumerable.**The Kleene-star operation on a recursive language is recursive.**It can be proved the same way as the previous case with a modification in algorithm that if any of w*Proof:*_{i}is not accepted by T, then reject.**The intersection of recursive and recursively enumerable language is recursively enumerable.**Let L*Proof:*_{1}be recursive and L_{2}be a recursively enumerable language. There exist two TMs, say T_{1}and T_{2}accepting L_{1}and L_{2}, respectively. Design a machine M to accept L_{1}∩ L_{2}whose operation is performed by the following logic.On input w ∈ L

_{1}∩ L_{2}Simulate w on T

_{1}If (T

_{1}halts and accepts w)Erase the tape content of M and copy w on the tape again.

Simulate w on T

_{2}If (T

_{2}halts and accepts w)w is accepted by M.

Thus, the intersection of recursive and recursively enumerable language is recursively enumerable.

**If L is a recursive language, then Σ* − L is also recursive.**As L is recursive, there exists a TM T*Proof:*_{m}accepting L. Σ * −**L**is the set of all languages except L which consists of the terminal symbols by which L is constructed.A new TM T′

_{m}is constructed as shown in the following diagram (Fig. 10.12) which halts and rejects a string w ∈ L but halts and accepts a string w ∉ L.**Fig. 10.12**TM for Σ* − LThe new machine consists of two TMs, T

_{m}and T_{2}. The design is such that if a string is accepted by T_{m}, it will be rejected by T_{2}and vice versa.The machine functions as follows: let a string w ∈ Σ* be given as input to the machine; it passes it to T

_{m}. If w ∈ L, then T_{m}accepts it and the input is passed to T_{2}which rejects it. On the reverse, if w ∉ L, T_{m}rejects but T_{2}accepts it.It is found that there exists a TM which halts and answers in ‘yes’ or ‘no’ for Σ* – L, thus proving it is recursive.

The following table is important for memorizing the closure property of different operations on different languages.

#### 10.5 Undecidability

In the previous section, it is already discussed that if there exists an algorithm to solve a problem, then the problem is called decidable. The Church–Turing thesis says that the ‘no computational procedure is considered as an algorithm unless it is represented by the Turing machine.’ It means that for a decidable problem there must exist a TM. Decidable problems are called solvable problems which can be solved by the computer. As solvable problems exist, there must also exist unsolvable problems which are not solved by the computer. Before going into the details of undecidability, the types of problems need to be discussed.

** Decidable or Solvable:** A language L is called decidable if there exists a TM M such that M accepts and halts on every string in L and rejects and halts on every string in L′.

A computational problem is known as decidable or solvable if the corresponding language is decidable.

** Recognizable:** A language L is called recognizable if there exists a TM M such that M accepts every string in L and either rejects or fails to halt on every string in L′.

A computational problem is known as recognizable or Turing acceptable if the corresponding language is recognizable.

** Undecidable:** Undecidable means not decidable. An undecidable language has no decider. There does not exist any TM which accepts the language and makes a decision by halting for every input string (may halt for some strings but not for all).

A computational problem is known as undecidable or unsolvable if the corresponding language is undecidable.

In the following section, we shall check the decidability of some languages related to DFA, NFA, and CFL.

#### Example 10.3

Prove that the problem that a string w is accepted by a DFA M is decidable.

** Solution:** According to the Church–Turing thesis, the algorithm for solving a problem must be represented by a TM. There exists an algorithm to check whether a string w is accepted by a DFA or not.

[Recall the algorithm in the finite automata chapter.

On getting input w to the beginning state of the DFA M, it traverses the string according to its transitional functions δ.

- The string is declared accepted if the string is totally traversed and the DFA reaches its final state.
- The string is not accepted if it is totally traversed but the DFA fails to reach to its final state.]

This can be represented by a TM which works as follows:

On getting a string w as an input to a DFA M

- The TM T simulates the DFA M on input w.
- T performs the simulation in a direct way keeping track of M’s current state and current position in the input string w.
- When T finishes the simulation by traversing the last symbol of w by the DFA M and reaches an accept state, it accepts. Reaching a non-accept state, T rejects.

As for every string w, the DFA halts declaring whether it accepts or rejects; so, the problem is decidable. In another way, it can be proved.

On input w to a DFA M

Run M on the string w.

If (w is accepted by M)

Halt and declare accept

Else

Halt and declare reject.

#### Example 10.4

Prove that the problem that a string w is accepted by an NFA M is decidable.

** Solution:** This example can be proved by using the proof of the previous example with a modification.

On getting a string w as an input to a NFA M

Convert the NFA M to an equivalent DFA M′.

(Algorithm exists, so an equivalent TM can be designed.)

Then, the TM T simulates the DFA M′ on input w.

#### Example 10.5

Prove that the problem that a set of null string is accepted by a DFA M is decidable.

*Solution***:**This can be represented by a TM which works as follows:

- On getting the input to the DFA M, mark the beginning state of the DFA.
- while(new states get marked = true)
do

{

Mark the state that has an incoming transition from a state already marked.

}

- If no accept state is marked,
*accept*; otherwise*reject*. Hence, decidable.

#### Example 10.6

Prove that the problem that a string L ∈ Σ* is accepted by a DFA M is decidable.

** Solution:** Construct a DFA M′ by changing the non-final states of M to the final state and final states of M to non-final states. Thus, the new DFA will accept Σ* – L = Φ , i.e., null set.

Construct a TM T which simulates the DFA M′.

Using example 3, if L(M′) = Φ then accept, otherwise reject. Hence, decidable.

#### Example 10.7

Prove that the problem that the two DFA, M_{1} and M_{2}, which satisfy the same language is decidable.

** Solution:** Let us assume that this is not true. Consider two languages L

_{1}and L

_{2}accepted by the two DFA M

_{1}and M

_{2}. A new DFA, M, is constructed which accepts only those strings that are accepted by either M

_{1}or M

_{2}but not both. From this, it is clear that if M

_{1}and M

_{2}recognize the same language, M will accept the null set.

Thus, the language accepted by M is

As L_{1} ⊆ L_{2} and L_{2} ⊆ L_{1}, it is proved that L_{1} = L_{2}.

Now let us come to the original proof.

- Construct a TM T which simulates on getting the input to M.
- Using Example 10.5, if L(M) = Φ then accept, otherwise reject. Hence, decidable.

#### Example 10.8

Prove that the problem that a string w is generated by a CFG G is decidable.

** Solution:** This can be proved by designing a TM which searches w from the set of the languages generated by G. But the set like (a,b)* may contain an infinite number of elements. So, this technique will not work for all cases. A different technique is used to prove this.

Construct a TM T which simulates the construction of w by G.

On getting input G, w, where G is the grammar and w is the string,

- Convert the grammar G to an equivalent grammar G′, where G′ is the Chomsky normal form of G. (Algorithm exists.)
- Derive up to 2n – 1 steps where | w | = n and list all the generated strings in a set S. If n = 0, then make derivations up to 1 step.
- If w ∈ S then accept, otherwise reject. Hence, decidable.

#### Example 10.9

Prove that the problem that a string w is accepted by a PDA P is decidable.

** Solution:** Construct a TM T which simulates this.

On getting input w, P, where w is the string and P is the PDA,

- Convert the PDA P to an equivalent CFG G. (Algorithm exists.)
- Convert the grammar G to an equivalent grammar G′, where G′ is the Chomsky normal form of G. (Algorithm exists.)
- Derive up to 2n – 1 steps where | w | = n and list all the generated strings in a set S. If n = 0, then make derivations up to 1 step.
- If w ∈ S then accept, otherwise reject. Hence, decidable.

#### Example 10.10

Prove if a language L is decidable, then its complement is also decidable.

** Solution:** As L is decidable, there exists a TM which accepts and halts for every string of L. Let us build another TM T′ using T where the ‘accept’ states of T are the ‘reject’ states of T′ and the rejected states of T are the accepted states of T′. T′ works as follows.

For each input string w,

- Run T on w.
- If T halts and accepts, then reject.
If T halts and rejects, then accept.

As T′ halts for every input string, is decidable.

#### Example 10.11

There is a language which is Turing acceptable and undecidable.

** Solution:** Let a language L be Turing acceptable. So, the language is not accepted by any TM. It is already proved that the complement of a decidable language is also decidable. As is not Turing acceptable, L is undecidable too. This proves that L is Turing acceptable but undecidable. This is described in Fig. 10.13.

**Fig. 10.13** Turing Acceptable and Undecidable

#### 10.6 Reducibility

A reduction is a process of converting one problem into another solved problem in such a way that the solution of the second problem can be used to solve the first problem.

This is coming from our daily life experience.

Let us assume that one is travelling in a new city and not aware of the transportation route. The person takes the help of a travel guide book (which contains the bus number, route number, destination, etc.). The book may be thought of as a solved problem. Finding the bus to reach to the destination is the problem. To solve the problem, we take the help of an already solved problem, i.e., the travel guide book.

To find the regular expression accepted by a finite automata is a problem. The Arden theorem is the solved problem. We reduce the first problem to the second problem (Arden theorem) to solve the first.

Reducibility involves two problems where one is a solved problem and another is the problem to be solved. If the problem to be solved is reduced to the solved problem, then the solution of the second problem is used to solve the first. Reducibility has some properties as follows.

Let the two problems be A and B, where B is a solved problem.

- When A is reduced to B, solving A cannot be harder than solving B.
- If A is reducible to B and B is a decidable problem, then A is also a decidable problem.
- If A is an undecidable problem and reducible to B, then B is also an undecidable problem (the important property used in proving that a problem is undecidable).

** Theorem 10.2:** A language is Turing recognizable if and only if some enumerator enumerates it.

*Proof*

** (IF Part):** If an enumerator enumerates a language, there exists a TM which recognizes the language.

Let the language L be enumerated by an enumerator E. Let a TM M recognize L, where M is designed as follows.

On input w,

- Run E. Every time when E outputs a string, say x, compare it with w.
- If x = w (i.e., the output of E ever matches with w), accept.

If an algorithm exists, it means that a TM exists. Thus, the TM M can be designed. This proves the ‘IF’ part.

** (Only IF):** Suppose the TM M recognizes L. Let s

_{1}, s

_{2}, s

_{3}, . . . . . s

_{i}be a list of all possible strings in Σ*. Construct an enumerator E

_{s}to generate this sequence. The enumerator works as follows.

- Repeat the following for input i = 1, 2, 3, . . . . .
- Run M for i steps on each input s
_{1}, s_{2}, s_{3}, . . . . . s_{i}. - If any computation is accepted, print out the corresponding S
_{i}.

#### Example 10.12

Prove that the problem ‘an arbitrary string w is accepted by an arbitrary TM M’ is undecidable.

** Solution:** This is known as the membership problem. The basic idea behind the problem is to find a contradiction. First, it is assumed that the problem is decidable. With this assumption, we will prove that every Turing-acceptable language is also decidable. This is a contradiction to our assumption.

Let us assume that the problem is decidable. So, there exists a TM A_{TM} accepting this. The machine A_{TM} takes the input <M, w> where M is the TM and w is the string. If M accepts w, then A_{TM} halts and accepts, if M rejects w then A_{TM} halts and rejects.

Let L be a recursively enumerable language and M′ be the TM accepting L. Let us build a decider for L reducing it to A_{TM}.

The pair <M′, s> is given as input to A_{TM}, where s is a string. As A_{TM} is the general TM for the arbitrary string w given input to the arbitrary TM M, it will halt for every input. Thus, L is decidable.

From here, it is proved that every Turing-acceptable language is decidable. But already it is proved that there is a Turing-acceptable language which is undecidable. Hence, we get a contradiction. So, our assumption is wrong.

It is proved that the membership problem is undecidable.

(Is it possible to know that a string w is accepted by a given TM M before traversing the string using the machine? This problem is known as the membership problem. From our general knowledge, we know that the answer is ‘no’. No algorithm exists to decide this. This is proved in the previous example.)

#### Example 10.13

Prove that the problem “a string w halts on a Turing machine M” is undecidable.

** Solution:** This is known as the halting problem.

Let us assume that the problem is decidable. So, there must exist a TM say A_{TM} to accept this. The machine A_{TM} takes the input <M, w> where M is the TM and w is the string. If M halts on w, then A_{TM} halts and accepts, if M does not halt on w then A_{TM} halts and rejects.

Let L be a recursively enumerable language and M_{L} be the TM that accepts L. Let us build a decider for L reducing it to A_{TM}.

The pair <M_{L}, s> is given the input to A _{TM}. s is an arbitrary string given as input to M_{L}. M_{L} will either halt or not. If M_{L} halts, then two conditions arise—whether s is accepted by M_{L} or it is rejected by M_{L}. In all the three cases, the decider halts on string s. Therefore, L is decidable.

A_{TM} is the general TM for the arbitrary string w given as input to the arbitrary TM M, and thus every Turing-acceptable language is also decidable.

But, it is already proved that there is a Turing-acceptable language which is undecidable. Hence, we get a contradiction. So, our assumption is wrong.

It is proved that the halting problem is undecidable.

(In general, the halting problem can be described that from the description of a computer program, decide whether the program finishes running or continues to run forever.)

#### Example 10.14

Given a TM *M*, prove that the problem whether or not *M* halts if started with a blank tape is undecidable.

** Solution:** This problem is called blank tape halting problem. This problem can be proved by reducing the halting problem to it.

Suppose that the blank tape halting problem is decidable. Therefore, it must have a decider to accept it. The decider takes the input of the TM M, halts and accepts if an M halt started with a blank tape; otherwise, it halts and rejects if M does not halt start with a blank tape.

The following is the decider for it.

Let there be a decider for deciding whether an arbitrary string w halts on a TM M. The decider takes two inputs—the machine M and the string w. This is the halting problem.

The halting problem can be reduced to the input of the blank tape halting problem decider using the following algorithm.

- Take the input from the machine M and the string w.
- Construct from M a new machine M
_{w}which starts with a blank tape, writes*w*on the tape, and then positions itself in a configuration (q_{0}, w)

The final decider is given in the following diagram.

From the discussion, it is clear that *M _{w}* halts on a blank tape if and only if

*M*halts on

*w.*Since this can be done for the arbitrary M and w, an algorithm for the blank-tape halting problem can be converted into an algorithm to solve the halting problem. But already it is proved that halting problem is undecidable. Thus, it is proved that the blank tape halting problem is undecidable.

#### Example 10.15

Prove that the problem ‘does a TM accept a regular language?’ is undecidable.

** Solution:** Suppose that the problem is decidable. Therefore, it must have a decider to accept it. The decider takes the input <M, w> where M is the TM and w is the string. It halts and accepts if w is a regular language ∈ Σ. Otherwise it halts and rejects if w is not regular.

The following is the decider for it.

Let there be a decider for deciding whether an arbitrary string w halts on a TM M. The decider takes two inputs—the machine M and the string w. This is the halting problem.

The halting problem can be reduced to the input of the regular language accepted by the TM problem using the following algorithm.

From M and w, design <M, w> such that:

- if
*M*does not accept*w*, then the decider for the regular language accepted by the TM problem accepts the non-regular language. - if
*M*accepts*w*, then it accepts the regular language Σ*.

The final decider is given in the following diagram.

If this problem is decidable, then it can be used to solve the halting problem. But it is already proved that the halting problem is undecidable. Thus, it is proved that the regular language accepted by the TM problem is undecidable.

#### Example 10.16

Prove that the problem ‘language generated by a TM is empty’ is undecidable.

** Solution:** The problem can be denoted symbolically as

_{TM}= {<M, w> | M is a TM and L(M) = Ø}

We have to prove that E_{TM} is undecidable.

Assume that E_{TM} is decidable; hence, a decider exists. Let R be the TM that decides E_{TM}. Construct a new TM S using R that decides whether the string w halts on the machine M or not (The halting problem).

Upon feeding the input <M, w> to the machine S, it is called R with input M. If R accepts, then S rejects as L(M) is empty. But the problem occurs when R rejects, as we do not know whether M accepts w or not. In this case, the input given to R is needed to be modified according to the following algorithm.

From M and w, design M_{w} such that:

On any arbitrary string x as input

- If x ≠ w, rejects.
- If x = w, run M on w and accept if M accepts.

(Here, M_{w} either accepts w or accepts nothing.)

The final decider is given in the following diagram.

Already, it is proved that S (the halting problem) is undecidable. So, E_{TM} is also undecidable.

#### Example 10.17

Prove that the problem ‘a given TM enters into an arbitrary state q ∈ Q while traversing a string w ∈ Σ^{+} ’ is undecidable.

** Solution:** This problem is called entry state problem. The undecidability of this problem can be proved by reducing the halting problem to it.

Assume that there exists an algorithm A that solves the entry state problem. This can be used to solve the halting problem.

The algorithm takes M and w. Modify M to get M_{1} in such a way that M_{1} halts in state q if and only if M halts.

M halts on a state q_{i} for input ‘i’, because δ(q_{i}, i) is undefined.

- Change every such undefined δ to δ(q
_{i}, i) = (q_{f}, i ,R) to get M_{1}where q_{f}is a final state. - Apply the entry state algorithm
*A*to (M_{1}, q_{i}, w).

If A produces the answer yes (i.e., state q_{i} is entered while traversing w), then (M, w) halts.

If A answers no, then (M, w) does not halt.

From the previous discussion, we are getting an algorithm for designing the halting problem decider. But it is already proved that the halting problem is undecidable. Thus, the entry state problem is also undecidable.

#### Example 10.18

Prove that the problem whether an arbitrary RE language is empty is undecidable.

** Solution:** This problem can be proved undecidable by reducing the membership problem to it.

Let us consider that this problem is decidable. Therefore, there is a decider which halts and accepts if the grammar for the RE language produces an empty string; otherwise, it halts and rejects if the grammar generates a non-empty string w.

Suppose that the membership problem is decidable. So, the decider A_{TM} halts and accepts if w is accepted by M, otherwise it halts and rejects if w is not accepted by A_{TM}.

Modify the machine M such that for input M and w,

- M saves its input on some specified location of its input tape.
- When M enters its final state upon traversing the input, it checks the stored input. It accepts if and only if it is same as stored in the input tape.

Construct a machine M_{w} for each w such that

_{w}) = L(M) ∩ {w}

Let T be the algorithm by which a grammar G_{W} can be constructed from it. If w ∈ L(M), then the language produced by the grammar G_{w}, i.e., L(G_{w}), is non-empty.

Put the output of T as the input to E. But, we know that the halting problem is undecidable, so the problem ‘whether an arbitrary RE language is empty’ is also undecidable.

#### Example 10.19

Prove that the problem ‘whether a recursively enumerable language L(M) is finite’ is undecidable.

** Solution:** This can be proved by reducing the halting problem to it.

Let M be the TM accepting L. Suppose that M_{f} is a decider for the finite language problem which takes the TM M as input.

Suppose that there is a decider for the halting problem which takes a TM M and a string w as input.

Now, reduce the halting problem to the finite language problem which constructs the machine M_{w} using the following process.

On input w to M,

- Design the machine M
_{w}such that when M enters into one of its halting states, M_{w}enters into its final state. M_{w}copies w on some special location of its input tape and then performs the same computation as M using the input w written on its input tape. - If M enters into any one of its halting states, M
_{w}halts reaching its final state. - If M does not enter into its halting state, M
_{w}does not halt and thus accepts nothing.

In other words, M_{w} accepts either the infinite language Σ^{+} or the finite language Φ.

The final decider is given in the following diagram.

Already, it is proved that the halting problem is undecidable. So, M_{f} is also undecidable.

#### Example 10.20

Prove that the problem ‘whether L(M) contains two strings of the same length’ is undecidable.

** Solution:** This can be proved by reducing the halting problem to it. Reduce the halting problem to this problem by constructing a machine M

_{w}using the following process.

On input w to M (the halting problem decider)

- M
_{w}copies w on some special location of its input tape and then performs the same computation as M using the input w written on its input tape. - If w = a or w = b, M enters into one of its halting states and M
_{w}reaches its final state. Thus, L(M_{w}) = {a, b} - Otherwise, reject. Thus L(M
_{w}) = {Φ}.

The final decider is given in the following diagram.

Already, it is proved that the halting problem is undecidable. So, M_{Eql} is also undecidable.

#### Example 10.21

Prove that the virus detection is undecidable.

** Solution:** A computer virus is an executable program that can replicate itself and spread from one computer to another. Every file or program that becomes infected can act as a virus itself, allowing it to spread to other files and computers. But the virus detection problem is undecidable! This can be proved using the undecidability of halting problem.

Let us define a virus by an algorithm called the ‘is-virus?’

For a program P,

Already, we have proved that the halting problem is undecidable. Hence, the virus detection problem is undecidable.

(As the virus detection problem is undecidable, there exists no anti-virus program! Amazing? Yes, it is true. The various anti-virus software just keep a record of the known viruses. If a program P matches with one of them, then P is declared as a virus. For this reason, we need to update our anti-virus software regularly.)

#### 10.7 Post’s Correspondence Problem (PCP)

The Post correspondence problem (PCP) was proposed by an American mathematician Emil Leon Post in 1946. This is a well-known undecidable problem in the theory of computer science. PCP is very useful for showing the undecidability of many other problems by means of reducibility.

Before discussing the theory of PCP, let us play a game. Let there be N cards where each of them are divided into two parts. Each card contains a top string and a bottom string.

** Example:** Let N = 5 and the cards be the following.

** Aim of the game:** Is to arrange the cards in such a manner that the top and the bottom strings become same.

** Solution for the example:** Solution is possible and the sequence is 4 3 2 5 1

Let us take another kind of example and try to find the solution.

** Example:** There are four types of cards, and each are five in number, which means there is a total 20 cards. There are four players. At the beginning of the game, each player will get five random cards. The game starts with the single card shifting, starting from one of the players. Getting a card from the left player, the player shifts one card from his/her collection to the immediate right player. Player able to show 5 cards arranged in a particular sequence, which constructs same top and bottom strings; then the player will win.

The four different cards are

** Solution:** Yes, it is possible. The sequence is 2 1 4 3 2.

But, for all types of cards, the solution is not possible. The game will continue for an infinite time. There is a condition which must be fulfilled to make the game halt. The condition is

- At least one card must contain the same starting character of the top and bottom strings. Though if the condition is fulfilled, it cannot be said confirm that the game will halt.

** The Post Correspondence Problem:** Given two sequences of strings w

_{1}, w

_{2}, . . . , w

_{n}and x

_{1}, x

_{2}, . . . , x

_{n}over Σ. The solution of the problem is to find a non-empty sequence of integers i

_{1}, i

_{2}, . . . , i

_{k}such that w

_{i1}w

_{i2}. . . w

_{ik}= x

_{i1}x

_{i2}. . . x

_{ik}.

The solution of PCP hides in the condition w_{i1}w_{i2} . . . w_{ik} = x_{i1}x_{i2} . . . x_{ik}.

If there exists a solution for a given instance of PCP, there may exist multiple solutions for that instance of PCP.

As an example, consider the previous example.

Σ = {0, 1} and the sequence of string w_{i}, x_{i} are as follows.

i | w _{i} | x _{i} |
---|---|---|

1 | 01 | 0 |

2 | 1 | 101 |

3 | 10 | 0 |

4 | 010 | 1 |

The problem has a solution i_{1} = 2, i_{2} = 1, i_{3} = 4, i_{4} = 3, i_{5} = 2 and the string is

#### Example 10.22

Find whether there is a solution for the following PCP problem.

i | w _{i} | x _{i} |
---|---|---|

1 | 01 | 0 |

2 | 1 | 01 |

3 | 10 | 0 |

4 | 010 | 1 |

** Solution:** To get a solution, the top and bottom strings of at least one card must start with the same character. But here, the top and bottom strings of no cards start with same character. Thus, this PCP problem does not have any solution.

#### 10.8 Modified Post Correspondence Problem

If the first substrings used in a PCP are w_{1} and x_{1} for all instances, then the PCP is called modified Post correspondence problem (MPCP). Therefore, the MPCP is

Given two sequences of strings w_{1}, w_{2}, . . . , w_{n} and x_{1}, x_{2}, . . . , x_{n} over Σ. The solution of the problem is to find a non-empty sequence of integers i_{2}, i_{3}, . . . , i_{k} such that w_{i1}w_{i2}w_{i3} . . . w_{ik} = x_{i1}x_{i2}x_{i3} . . . x_{ik}.

The derivation process of a string accepted by a given grammar can be reduced to the MPCP. We know that the MPCP needs two sequence of strings, say, denoted by two sets A and B. The derivation process can be reduced to MPCP with the help of the following table.

Top A | Bottom B | Grammar G |
---|---|---|

FS → | F | S: Start symbol |

a | a | For every symbol ∈ Σ |

V | V | For every non-terminal symbol |

E | → wE | String w |

y | x | For every production x → y |

→ | → |

#### Example 10.23

Let the grammar be

The string is w = aacb. Convert the derivation to generate the string to MPCP.

** Solution:** The grammar with the string is mapped in the following table.

The string is derived as

The conversion of the derivation to MPCP is shown as follows.

** Theorem 10.3:** The modified Post correspondence problem is undecidable.

** Proof:** This can be proved by reducing the membership problem to it.

Let MPC problem be decidable. Thus, there is a decider for the MPC problem which takes two sets A and B and halts and accepts if they satisfy the MPC condition or halts and rejects if they fail to satisfy the MPC condition. The following is the decider for the MPC problem.

Let there be a decider for deciding whether an arbitrary string w is accepted by a grammar G. The decider takes two inputs, w and G, and halts and accepts if w is accepted or halts and rejects if w is not accepted by G. This is the membership problem. The following is the decider for this.

The membership problem with input (G, w) can be reduced to the input of the MPC problem decider (A, B) as described earlier.

The two set of strings A and B has a solution if and only if w∈ G. Since the membership problem is undecidable, the MPC problem is also undecidable.

The modified PCP can be reduced to a PCP. This reduction can be used to prove that the PCP is undecidable.

#### 10.8.1 Reduction of MPCP to PCP

Given two sequences of strings w_{1}, w_{2}, . . . , w_{n} and x_{1}, x_{2}, . . . , x_{n} over Σ. A sequence of integers i_{2}, i_{3}, . . . , i_{k} exist such that w_{1}w_{i2}w_{i3} . . . w_{ik} = x_{1}x_{i2}x_{i3} . . . x_{ik}.

- Introduce a new symbol *.
- In the first list w
_{i}(i = 1, 2, . . . . . n), the new symbol * appears after every symbol. In the second list x_{i}(i = 1, 2, . . . . . n), the new symbol * appears before every symbol.(

If the w and x part of a MPCP is 01 and 101, respectively, then in PCP this becomes 1*0* and *1*0*1, respectively.)*Example:* - Take the first pair w
_{1}, x_{1}from the given MPCP, and add to the PCP instance another pair in which the *s remain as modified in (ii) but an extra * is added to w_{1}at the beginning.(

If in the previous example w and x are w*Example:*_{1}and x_{1}part of a MPCP, then in PCP this becomes *1*0* and *1*0*1, respectively.) - Since the first list has an extra * at the end, add another pair $ and *$ to the PCP instance. This is referred to as the final pair.

#### Example 10.24

Convert the following MPCP to an equivalent PCP.

i | w _{i} | x _{i} |
---|---|---|

1 | 01 | 011 |

2 | 10 | 0 |

3 | 01 | 11 |

4 | 1 | 0 |

** Solution:** This is in MPCP as there is a sequence 1, 4, 3, 2 which generates the string 0110110 in both halves.

Adding * after every symbol in w, before every symbol in x, and adding an extra * at the beginning of w_{1}, the modified sequence becomes

i | w _{i} | x _{i} |
---|---|---|

1 | *0*1* | *0*1*1 |

2 | 1*0* | *0 |

3 | 0*1* | *1*1 |

4 | 1* | *0 |

Adding extra sequence $ and *$ to the existing sequence as the final pair, the PCP becomes

i | w _{i} | x _{i} |
---|---|---|

1 | *0*1* | *0*1*1 |

2 | 1*0* | *0 |

3 | 0*1* | *1*1 |

4 | 1* | *0 |

5 | $ | *$ |

This is a PCP as there exists a sequence 1, 4, 3, 2, 5 which generates the string *0*1*1*0*1*1*0*$.

** Theorem 10.4:** The post correspondence problem is undecidable.

** Proof:** Let PCP be decidable. Thus, there is a decider for PCP which takes two sets w and x and halts and accepts if they satisfy the PCP condition or halts and rejects if they fail to satisfy the PCP condition. The following is the decider for PCP.

Let there be a decider for MPCP. The decider takes two inputs A and B and halts and accepts if a solution is found or halts and rejects if a solution is not found. The following is the decider for this.

The MPC problem with input (A, B) can be reduced to the input of a PCP decider (w, x) as described earlier.

The two set of strings w and x have a solution if and only if the two set of strings A and B have a solution. Since the MPC problem is undecidable, PCP is also undecidable.

#### Example 10.25

Prove that the problem ‘whether an arbitrary CFG G is ambiguous’ is undecidable.

** Solution:** To prove this, we reduce the PCP problem to the A

_{Amb}problem, where A

_{Amb}is considered as a decider for the ambiguity of the CFG problem. The PCP problem decider takes two lists A and B as input and generates a CFG G. If the PCP decider has a solution for the two lists A and B, then the CFG G is ambiguous.

This reduction is done by the following process.

Let A = {w_{1}, w_{2}, . . . . . w_{n}} and B = {x_{1}, x_{2}, . . . . . x_{n}}.

Let a_{1}, a_{2} . . . . . a_{n} be a list of new symbols generated by the languages.

Both L_{A} and L_{B} can be constructed from the following grammar.

Both of them are CFG.

We can easily construct a new CFG by the union operation of the two CFG since CFG are closed under the union operation.

If the given instance of the PCP has a solution for i_{1}, i_{2}, . . . . . i_{m}, then the string generated in the top and bottom halves are w_{i1} w_{i2} . . . . . w_{im} = x_{i1} x_{i2} . . . . . x_{im}. Thus, L_{A} = L_{B}. For the grammar L_{A} ∪ L_{B}, there exist two derivations of a same string, which means two parse trees. This makes L_{A} ∪ L_{B} ambiguous.

But it is already proved that the halting problem is undecidable. So, the problem A_{Amb} is also undecidable.

#### What We Have Learned So Far

- A Turing-acceptable language is called Turing-recognizable or recursively enumerable.
- A language is recursively enumerable if there is a Turing machine that halts and accepts the language or halts and rejects or loops for an infinite time.
- A language is called Turing-decidable if there exists a Turing machine which halts and accepts the language. Otherwise, it is undecidable.
- A recursive language is a subset of a recursively enumerable language.
- A reduction is a process of converting one problem into another solved problem in such a way that the solution of the second problem can be used to solve the first problem.
- The complement of a decidable language is also decidable.
- The problem ‘an arbitrary string w is accepted by an arbitrary Turing machine M’ is known as the membership problem, which is an undecidable problem.
- The problem ‘a string w halts on a Turing machine M’ is known as the halting problem, which is an undecidable problem.
- Given two sequences of strings w
_{1}, w_{2}, . . . , w_{n}and x_{1}, x_{2}, . . . , x_{n}over Σ. The solution of the problem is to find a non-empty sequence of integers i_{1}, i_{2}, . . . , i_{k}such that w_{i1}w_{i2}. . . w_{ik}= x_{i1}x_{i2}. . . x_{ik}is known as the Post correspondence problem (PCP). - Given two sequences of strings w
_{1}, w_{2}, . . . , w_{n}and x_{1}, x_{2}, . . . , x_{n}over Σ. The solution of the problem is to find a non-empty sequence of integers i_{2}, i_{3}, . . . , i_{k}such that w_{1}w_{i2}w_{i3}. . . w_{ik}= x_{1}x_{i2}x_{i3}. . . x_{ik}is known as the modified Post correspondence problem (MPCP). - The PCP and MPCP are both undecidable problems.

- Find at least three solutions to the PCP defined by the dominoes.
[UPTU 2002]

The solution is possible as X1, Y1 and X3, and Y3 have the same initial substring. The solution is 3112.*Solution:*Repeating the sequence 3112, we can get multiple solutions.

- Does the PCP with two lists X = {b, bab
^{3}, ba} and Y = {b^{3}, ba, a} have a solution.[UPTU 2003]

The solution is possible as X1, Y1 and X2, and Y2 have the same initial substring. The solution is 2113.*Solution:* - Does the PCP with two list X = {(a, ba), (b
^{2}a, a^{3}), (a^{2}b, ba)} has a solution?The solution is not possible as none of the top and bottom parts of the list have the same starting character.*Solution:* - Show that the following PCP has a solution and give the solution.
AB1111112100001311111
[JNTU 2008]

The solution is possible as the A and B parts of the first and third lists have the same starting characters. The solution is 123.*Solution:* - The lists A and B given in the following are an instance of PCP.
AB100120101131000010
Find the solution for the given PCP.

The solution is 1332.*Solution:* - Prove that if L
_{1}is regular and L_{2}is context free, then is recursive.L*Solution:*_{1}is regular, so it is recursive. The complement of the context-free language is not context free. But, the context-free language is recursive and the complement of the recursive language is recursive. It is proved that the union of two recursive languages is recursive. Hence,is recursive.

#### Multiple Choice Questions

- The Turing machine accepts
- Regular language
- Context-free language
- Context-sensitive language
- All of these

- A language is recursively enumerable if a Turing machine
- Halts and accepts
- Halts and rejects
- loops forever
- performs (a), (b), or (c)

- A language L is called decidable (or just decidable), if there exists a Turing machine M which
- Accepts L
- Rejects L
- Loops forever on L
- performs (a), (b), or (c)

- Find the true statement
- A recursively enumerable language is a subset of a recursive language
- A recursive language is a subset of a recursively enumerable language
- Both are equivalent
- Both may loop forever on the input to a Turing machine

- Which is false for recursive language?
- Find the decidable problem regarding the DFA.
- The problem that a set of null strings is accepted by a DFA M
- The problem that a string w is accepted by a DFA M
- The problem that two DFA, M
_{1}and M_{2}, satisfy the same language - All of these

- Which is true for reducibility?
- Converting one problem to another problem.
- Converting one solved problem to another unsolved problem.
- Converting one unsolved problem into another solved problem to solve the first problem.
- Converting one unsolved problem to another unsolved problem.

*Answers:*

- d
- d
- a
- b
- c
- d
- c

#### GATE Questions

- Which of the following statements is false?
- The halting problem of a Turing machine is undecidable.
- Determining whether a context-free grammar is ambiguous is undecidable.
- Given two arbitrary context-free grammars G
_{1}and G_{2}, it is undecidable whether L(G_{1}) = L(G_{2}). - Given two regular grammars G
_{1}and G_{2}, it is undecidable whether L(G_{1}) = L(G_{2}).

- Which of the following is not decidable?
- Given a Turing machine M, a string s, and an integer k, M accepts s within k steps
- The equivalence of two given Turing machines
- The language accepted by a given finite state machine is not empty.
- The language generated by a context-free grammar is non-empty.

- Consider the following decision problems:
P

_{1}: Does a given finite state machine accept a given stringP

_{2}: Does a given context-free grammar generate an infinite number of strings.Which of the following statements is true?

- Both P
_{1}and P_{2}are decidable - Neither P
_{1}nor P_{2}are decidable - Only P
_{1}is decidable - Only P
_{2}is decidable

- Both P
- Consider the following problem X.
Given a Turing machine M over the input alphabet Σ, any state q of M and a word w ∈ Σ*, does the computation of M on w visit the state q?

- Which of the following is true?
- The complement of a recursive language is recursive
- The complement of a recursively enumerable language is recursively enumerable
- The complement of a recursive language is either recursive or recursively enumerable
- The complement of a context-free language is context free

- L
_{1}is a recursively enumerable language over Σ. An algorithm A effectively enumerates its words as w_{1}, w_{2}, w_{3}, . . . Define another language L_{2}over Σ ∪ {#} as {w_{i}# w_{j}: w_{j}∈ L_{1}, i < j}. Here, # is a new symbol.Consider the following assertions.

S

_{1}: L_{1}is recursive implies that L_{2}is recursiveS

_{2}: L_{2}is recursive implies that L_{1}is recursiveWhich of the following statements is true?

- Both S
_{1}and S_{2}are true - S
_{1}is true but S_{2}is not necessarily true - S
_{2}is true but S_{1}is not necessarily true - Neither is necessarily true

- Both S
- Consider three decision problems P
_{1},P_{2}, and P_{3}. It is known that P_{1}is decidable and P_{2}is undecidable. Which one of the following is true?- P
_{3}is decidable if P_{1}is reducible to P_{3} - P
_{3}is undecidable if P_{3}is reducible to P_{2} - P
_{3}is undecidable if P_{2}is reducible to P_{3} - P
_{3}is decidable if P_{3}is reducible to P_{2}’s complement

- P
- Let L
_{1}be a recursive language, and let L_{2}be a recursively enumerable but not a recursive language. Which one of the following is true?_{1}is recursive and_{2}is recursively enumerable._{1}is recursive and_{2}is not recursively enumerable._{1}and_{2}are recursively enumerable._{1}is recursively enumerable and_{2}is recursive

- For S ∈ (0 + 1)*, let d(s) denote the decimal value of s [e.g., d(101) = 5]. Let L = {s ∈ (0 + 1)* | d(s) mod 5 = 2 and d(s) mod 7 ≠ 4}
Which one of the following statements is true?

- L is recursively enumerable, but not recursive
- L is recursive, but not context free
- L is context free, but not regular
- L is regular

- Let L
_{1}be a regular language, L_{2}be a deterministic context-free language, and L_{3}a recursively enumerable, but not recursive language. Which one of the following statements is false?- L
_{1}∩ L_{2}is a deterministic CFL - L
_{3}∩ L_{1}is recursive - L
_{1}∪ L_{2}is context free - L
_{1}∩ L_{2}∩ L_{3}is recursively enumerable

- L
- Which of the following problems is undecidable?
- Membership problem for CFGs.
- Ambiguity problem for CFGs.
- Finiteness problem for FSAs
- Equivalence problem for FSAs.

- The language L = {0
^{i}21^{i}| i ≥ 0} over alphabet {0, 1, 2} is- not recursive
- recursive and is a deterministic CFL.
- a regular language.
- not a deterministic CFL but a CFL.

- Which of the following are decidable?
- Whether the intersection of two regular languages is infinite
- Whether a given context-free language is regular
- Whether two pushdown automata accept the same language
- Whether a given grammar is context free

- (i) and (ii)
- (i) and (iv)
- (ii) and (iii)
- (ii) and (iv)

- If L and are recursively enumerable, then L is
- Regular
- Context free
- Context sensitive
- Recursive

- Which of the following statements is false?
- Every NFA can be converted to an equivalent DFA
- Every non-deterministic Turing machine can be converted to an equivalent deterministic Turing machine.
- Every regular language is also a context-free language
- Every subset of a recursively enumerable set is recursive.

- Let L1 be a recursive language. Let L
_{2}and L_{3}be the languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?- L
_{2}– L_{1}is recursively enumerable - L
_{1}– L_{3}is recursively enumerable - L
_{2}∩ L_{1}is recursively enumerable - L
_{2}∪ L_{1}is recursively enumerable

- L
- Let L = L
_{1}∩ L_{2}, where L_{1}and L_{2}are languages as defined in the following:L_{1}= {a^{m}b^{m}ca^{n}b^{n}, m, n ≥ 0), L_{2}= {a^{i}b^{j}c^{k}, i, j, k ≥ 0)Then, L is

- not recursive
- regular
- context-free but not regular
- recursively enumerable but not context free

- Which of the following problems are decidable?
- Does a given program ever produce an output?
- If L is a context-free language, then, is also context free?
- If L is a regular language, then is also regular?
- If L is a recursive language, then is also recursive?

- (i), (ii), (iii), (iv)
- (i), (ii)
- (ii), (iii), (iv)
- (iii), (iv)

*Answers:*

- d
- b
- a
- b
- a
- b
- b
- b
- b
- b
- b
- b
- b
- d
- d
- b
- a
- d

**Hints:**

1. From a regular grammar, FA can be designed. It can be tested whether two FA are equivalent or not.

3. A given CFG is infinite if there is at least one cycle in the directed graph generated from the production rules of the given CFG in CNF.

4. The problem is undecidable. But if the state is the beginning state, it must be traversed. Thus, it is partially decidable.

8. The complement of a recursively enumerable language is not recursively enumerable.

9. L = 5n + 2 but L ≠ 7n + 4. Hence, we can design a machine which halts and accepts if L = 5n + 2 and halts and rejects if L ≠ 7n + 4. So, it is decidable.

10. L_{1} and L_{2} are recursive. The intersection of two recursive languages is recursive. But the intersection of the recursive and the recursively enumerable languages are recursively enumerable and not recursive.

12. A DPDA can be designed which PUSH X for each appearance of ‘0’. No stack operation for traversing 2 and POP X for ‘1’. A Turing machine can be designed for it where for each ‘0’ it traverses the rightmost ‘1’ by replacing them by X and Y, respectively. If after X, 2 appears and after 2, Y appears, then it halts. Thus, it is recursive.

13. The intersection of two regular language is regular, i.e., CFL. Using Q3, we can find infiniteness.

16. The size of the L_{1} set is less than the size of the L_{3} set.

17. Two languages are CFL. The intersection of the two CFL is not a CFL, so not regular. (b and c are false). The answer will be ‘a’ or ‘d’.

#### Exercise

- Prove that any decision cannot be taken for A∪B
^{c}, if A is recursive and B is recursively enumerable. - Prove that A∪B
^{c}is recursively enumerable if A is recursive and B is recursively enumerable. - Prove that the problem that a regular language L accepted by a pushdown automata P is decidable.
- Prove that the problem that a regular string w is generated by a CFG G is decidable.
- Prove that the problem that the same string w accepted by two DFA, M
_{1}and M_{2}, is decidable. - Prove that the problem whether a DFA and a regular expression is equivalent is decidable.
- Prove that the problem whether two regular expressions R
_{1}and R_{2}are equivalent is decidable. - Prove that the problem that an arbitrary Turing machine M ever prints a string 101 on its tape is undecidable.
- Prove that the problem whether a string accepted by an arbitrary Turing machine M is regular is undecidable.
- Prove that the problem whether an arbitrary Turing machine accepts a single string is undecidable.
- Find a solution for the following Post correspondence problem.
List A = {01, 10, 01, 1}List B = {011, 0, 11, 0}