The chomsky hierarchy the chomsky hierarchy

Theory of Computation Class Notes1

1based on the books by Sudkamp and by Hopcroft, Motwani and Ullman

6.7 Nondeterministic Turing Machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

6.8 Turing Machines as Language Enumerators . . . . . . . . . . . . . . . . . . . . . . . . 50

8.2 The Church-Turing Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

8.3 The Halting Problem for Turing Machines . . . . . . . . . . . . . . . . . . . . . . . . . 54

9.1.1 Programs that Print “Hello, World” . . . . . . . . . . . . . . . . . . . . . . . . 59

9.1.2 The Hypothetical “Hello, World” Tester . . . . . . . . . . . . . . . . . . . . . . 60

9.2.3 The Diagonalization Language . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

9.2.4 Proof that Ld is not Recursively Enumerable . . . . . . . . . . . . . . . . . . . 64

9.3.1 Reductions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

9.3.2 Turing Machine That Accepts the Empty Language . . . . . . . . . . . . . . . 70

9.5.1 Undecidability of Ambiguity for CFG’s . . . . . . . . . . . . . . . . . . . . . . 77

9.5.2 The Complement of a List Language . . . . . . . . . . . . . . . . . . . . . . . . 78

10.1.3 An NP Example: The Travelling Salesman Problem . . . . . . . . . . . . . . . 10.1.4 NP-complete Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

84

1.1 Sets

A set is a collection of elements. To indicate that x is an element of the set S, we write x ∈ S. The statement that x is not in S is written as x /∈ S. A set is specified by enclosing some description of its elements in curly braces; for example, the set of all natural numbers 0, 1, 2, · · · is denoted by N = {0, 1, 2, 3, · · ·}.

A set S1 is said to be a subset of S if every element of S1 is also an element of S. We write this as

S1 ⊆ S
If S1 ⊆ S, but S contains an element not in S1, we say that S1 is a proper subset of S; we write this as

1. S1 ∪ S2 = S1 ∩ S2,

2. S1 ∩ S2 = S1 ∪ S2,

(def.union)
(negation of disjunction)

(def.complement)

Observe that 2Sis a set of sets.

Example 1.1.1

Proof: (By induction on the number of elements in S).

Basis: |S| = 1 ⇒ 2S= {∅, S} ⇒ |2S| = 21= 2

1.2. FUNCTIONS AND RELATIONS 3

where Sk = {y1, y2, y3, . . . , yk}

A set which has as its elements ordered sequences of elements from other sets is called the Cartesian product of the other sets. For the Cartesian product of two sets, which itself is a set of ordered pairs, we write

S = S1 × S2 = {(x, y) | x ∈ S1, y ∈ S2}

A × A = {(head,head),(head,tail),(tail,head),(tail,tail)} the set of all possible throws of two coins.

The notation is extended in an obvious fashion to the Cartesian product of more than two sets; generally

1. Domain f = {x ∈ S1 | (x, y) ∈ f, for some y ∈ S2} = Df 2. Range f = {y ∈ S2 | (x, y) ∈ f, for some x ∈ S1} = Rf

4 CHAPTER 1. INTRODUCTION

A specific kind of relation is an equivalence relation. A relation denoted r on X is an equivalence relation if it satisfies three rules,
the reflexivity rule:

(x, x) ∈ r ∀x ∈X the symmetry rule:

i = j mod m if i − j is divisible by m; Z is partitioned into m equivalence classes:

{· · · , −2m, −m, 0, m, 2m, · · ·}
{· · · , −2m + 1, −m + 1, 1, m + 1, 2m + 1, · · · }
{· · · , −2m + 2, −m + 2, 2, m + 2, 2m + 2, · · · }
{· · · , −m − 1, −1, m − 1, 2m, 3m − 1, · · · }

• The cardinality of denumerable sets is #N = ℵ0 (“aleph0”)
• The cardinality of the set of the real numbers, #R = ℵ1 (“aleph1”)

A set is infinite if it has proper subset of the same cardinality.

The one to one correspondence between the natural numbers and the set of all integers exhibits the countability of set of integers. A correspondence is defined by the function

Example 1.3.3

#Q+= #J = #N
Q+is the set of the rational numbersp q> 0, where p and q are integers, q ̸= 0.

statements P1, P2, · · · , Pn is the induction hypothesis, and the argument connecting the induction

6 CHAPTER 1. INTRODUCTION

(b) For the induction hypothesis, we assume that the property holds with n = k; (a) the basis by substituting 0 for n in�n i=0i2 = n(n+1)(2n+1) and observing that both sides are 0.

(c) In the induction step, we show that the property holds for n = k + 1; i.e.,�k i=0i2 = k(k+1)(2k+1)

(k)(k+1)(2k+1)

6 + (k + 1)2=(k+1)(k+2)(2k+3) 6

Show that√2 is not a rational number.

As in all proofs by contradiction, we assume the contrary of what we want to show. Here we assume

Therefore n2must be even. This implies that n is even, so that we can write n = 2k or 2m2= 4k2
and
m2= 2k2

1.4. PROOF TECHNIQUES 7

logically sound, we must conclude that our initial assumption was false.

To illustrate Cantor’s diagonalization method, we prove that the set A = {f|f a total function,

enumeration. However f is total and f : N → N. Hence the set A is uncountable since such an f can be given for any chosen enumeration.

Therefore A cannot be enumerated; hence A is uncountable.

Remarks:

The set of all infinite sequences of 0’s and 1’s is uncountable. With each infinite sequence of 0’s and

Languages and Grammars

2.1 Languages

Σ = {a, b}
L1 = {ab, ba, aa, bb, ε}
L2 = {w|w = (ab)k, k = 0, 1, 2, 3, . . .}
= {ε, ab, abab, ababab, . . .}

The concatenation of two strings w and v is the string obtained by appending the symbols of v to the right end of w, that is, if

wv = a1a2 . . . anb1b2 . . . bm

which completes the induction step.

for all w. Note that εw = wε = w for all w. The reverse of a string is obtained by writing the symbols in reverse order; if w is a string as shown above, then its reverse wRis
wR= an . . . a2a1
If
w = uv,
then v is said to be prefix and u a suffix of w.

The length of a string w, denoted by |w|, is the number of symbols in the string. Note that,
|ε| = 0
If u and v are strings, then the length of their concatenation is the sum of the individual lengths, |uv| = |u| + |v|
Let us show that |uv| = |u| + |v|. To prove this by induction on the length of strings, let us define the length of a string recursively, by

By the induction hypothesis (which is applicable since w is of length n). |uw| = |u| + |w|.

so that
|uv| = |u| + |w| + 1 = |u| + |v|.

{a, aa, aab}.

L1L2 = {xy|x ∈ L1and y ∈ L2}
We define Lnas L concatenated with itself n times, with the special case

Example 2.1.4

The string aabbaaabbb is in L2.The star-closure or Kleene closure of a language is defined as

2. If r and r1 are regular expressions so are (r), (r∗), (r1 + r2), (r.r1).

3. A string is a regular expression if it can be derived from the primitive regular expressions by applying a finite number of the operations +, * and concatenation.

3. αα∗+ ε = α∗.

4. α(β + γ) = αβ + αγ.

In general, the distribution law does not hold for the closure operation. For example, the statement α∗+ β∗?= (α + β)∗ is false because the right hand side denotes no string in which both α and β appear.

2.3. GRAMMARS 13

Successive strings are derived by applying the productions of the grammar in arbitrary order. A production can be used whenever it is applicable, and it can be applied as often as desired. If

w1 ⇒ w2 ⇒ w3 · · · ⇒ w we say that w1 derives w, and write w1∗⇒ w.

14 CHAPTER 2. LANGUAGES AND GRAMMARS

Example 2.3.1

S → ε

Then

Example 2.3.2

P:

< expression >→< expression >< operation >< expression >⇒< variable >< operation >< expression >
⇒ A < operation >< expression >
⇒ A+ < expression >
⇒ A+ < expression >< operation >< expression >⇒ A+ < variable >< operation >< variable >⇒ A + B < operation >< expression >
⇒ A + B∗ < expression >
⇒ A + B∗ < variable >
⇒ A + B ∗ C