Theory of Computation

by Iqbal Hussain
 Text and Reference Material
1. Introduction to Computer Theory, by Daniel I.
Cohen, John Wiley and Sons, Inc., 1991,
Second Edition

2. Introduction to Languages and Theory of

Computation, by J. C. Martin, McGraw Hill Book
Co., 2011, Fourth Edition

2
• Every time we introduce a new machine, we will learn its
language; and every time we develop a new language, we
will try to find a machine that corresponds to it.

• This relationship between languages and machines will be

our way of investigating problems and their potential
solutions by automatic procedures, which we call
algorithms.

3
 What does automata mean?

It is the plural of automaton, and it means

“something that works automatically”

4
 What is Automata Theory?

Study of abstract computing devices, or

“machines”

5
 Languages
• In English, we distinguish 3 different entities: letters,
words, and sentences.
– Groups of letters make up words and groups of words
make up sentences.

– However, not all collections of letters form valid words, and

not all collections of words form valid sentences.

• This situation also exists with computer languages.

– Certain (but not all) strings of characters are recognizable

words (e.g., IF, ELSE, FOR, WHILE …); and certain (but
not all) strings of words are recognizable commands.
– The collection successful inputs is called the language of the
machine
6
 Basic Definitions
• A finite non-empty set of symbols (letters), is
called an alphabet. It is denoted by Σ ( Greek
letter sigma).

Example:
Σ={a,b}
Σ={0,1} //important as this is the language
//which the computer understands.
Σ={i,j,k}

7
 Strings

Concatenation of finite symbols from the

alphabet is called a string.

• Example:
If Σ= {a,b} then
a, abab, aaabb, ababababababababab

8
 Words
• Words are strings belonging to some language.

Example:
If Σ= {x} then a language L can be defined as
L={xn : n=1,2,3,…..} or L={x,xx,xxx,….}
Here x,xx,… are the words of L

9
 Defining Languages
• The languages can be defined in different ways ,
such as Descriptive definition, Recursive
definition, using Regular Expressions(RE) and
using Finite Automaton(FA) etc.

10
 Example
The language L of strings of odd length, defined
over Σ={a}, can be written as
L={a, aaa, aaaaa,…..}

• Example:

The language L of strings that does not start with

a, defined over Σ={a,b,c}, can be written as
L={b, c, ba, bb, bc, ca, cb, cc, …}

11
 Example
The language L of strings of length 2, defined
over Σ={0,1,2}, can be written as
L={00, 01, 02,10, 11,12,20,21,22}

• Example:
The language L of strings ending in 0,
defined over Σ ={0,1}, can be written as
L={0,00,10,000,010,100,110,…}

12
 Example
• The language EQUAL, of strings with number of
a’s equal to number of b’s, defined over Σ={a,b},
can be written as
{Λ ,ab,aabb,abab,baba,abba,…}

• The language EVEN-EVEN, of strings with even

number of a’s and even number of b’s, defined
over Σ={a,b}, can be written as
{Λ, aa, bb, aaaa,aabb,abab, abba, baab, baba,
bbaa, bbbb,…}

13
 Example
• The language {an bn }, of strings defined over
Σ={a,b}, as
{an bn: n=1,2,3,…}, can be written as
{ab, aabb, aaabbb,aaaabbbb,…}

• The language {an bn an }, of strings defined over

Σ={a,b}, as
{an bn an: n=1,2,3,…}, can be written as
{aba, aabbaa, aaabbbaaa,aaaabbbbaaaa,…}

14
 Example
• The language FACTORIAL, of strings defined
over Σ= {a}, as
{an! : n=1,2,3,…}, can be written as
{a,aa,aaaaaa,…}. It is to be noted that the
language FACTORIAL can be defined over any
single letter alphabet.
• The language DOUBLEFACTORIAL, of strings
defined over Σ= {a, b}, as
{an! bn!: n=1,2,3,…}, can be written as
{ab, aabb, aaaaaabbbbbb,…}

15
 Concatenation
• Let us define an operation, concatenation, in which two strings are
written down side by side to form a new longer string.
xxx concatenated with xx is the word xxxxx
xn concatenated with xm is the word xn+m

• For convenience, we may label a word in a given language by a new

symbol. For example,
xxx is called a, and xx is called b
• Then to denote the word formed by concatenating a and b, we can
write
ab = xxxxx

16
 Concatenation makes new Words?
• Note that in this simple example, we have:
ab = ba
But in general, this relationship does NOT hold for all
languages (e.g., houseboat and boathouse are two
different words in English).

17
 Definition: Length
• We define the function length of a string to be the
number of letters in the string.
• Example:
– If a = xxxx in the language L1, then length(a) = 4
– If c = 428 in the language L3, then length(c) = 3
– If d = 0 in the language L3, then length(d) = 1
– In any language that includes the null word Λ, then
length(Λ) = 0

• For any word w in any language, if length(w) = 0 then w

= Λ.

18
 Definition: Reverse
• If a is a word in some language L, then reverse(a) is the
same string of letters spelled backward, even if this
backward string is not a word in L.
• Example:
– reverse(xxx) = xxx
– reverse(145) = 541
– Note that 140 is a word in L3, but reverse(140) = 041 is NOT a
word in L3

19
 Kleene Closure
• Definition: Given an alphabet ∑, we define a language
in which any string of letters from ∑ is a word, even the
null string Λ. We call this language the closure of the
alphabet ∑, and denote this language by ∑*.

• Examples:
If ∑ = { x } then ∑* = { Λ, x, xx, xxx, … }
If ∑ = { 0, 1 } then ∑* = { Λ, 0, 1, 00, 01, 10, 11,
000, 001, … }
If ∑ = { a, b, c } then ∑* = { Λ, a, b, c, aa, ab, ac,
ba, bb, bc, ca, cb, cc, aaa, … }

20
 Lexicographic order
• Note that we listed the words in a language in size order
(i.e., words of shortest length first), and then listed all the
words of the same length alphabetically.

• This ordering is called lexicographic order, which we

will usually follow.

• The star in the closure notation is known as the Kleene

star.

21