Chapter One

Complexity theory is a central topic in theoretical computer science. It has

direct applications to computability theory and uses computation models such
as Turing machines to help test complexity. Complexity theory helps computer
scientists relate and group problems together into complexity classes.
To test a problem’s complexity, computer scientists will try to solve the
problem on a Turing machine and see how many steps (time complexity) and
how much tape (space complexity) it requires to decide a problem.
Complexity theory can be one of the more challenging topics in theoretical
computer science since it requires a fair amount of background.
To clearly understand complexity theory, one should be familiar with the
topics: such as Regular languages, context-free grammars, and context-free
languages.

WSU, COMPUTER SCIENCE DEPARTMENT 1

 Chapter One Cont…
 A regular language is a language that can be expressed with a regular expression or
a deterministic or nondeterministic finite automata or state machine.
A language is a set of strings which are made up of characters from a specified
alphabet, or set of symbols.
Regular language is a language that can be expressed with a regular expression. It is a
subset of the set of all strings. Regular languages are used in parsing and designing
programming languages.
Regular Expressions are the most useful tools in string processing. It was initially a
term borrowed from automata theory in theoretical computer science. Broadly, it refers
to patterns to which a substring needs to be matched.
Regular languages and finite automata can model computational problems that
require a very small amount of memory. For example, a finite automaton can generate a
regular language to describe if a light switch is on or off but it cannot keep track of how
many times the light was switched on or off.

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 2

 Turing Machines
 A Turing machine is an automaton whose temporary storage is a tape. This
tape is divided into cells, each of which is capable of holding one symbol.
Associated with the tape is a read-write head that can travel right or left on the
tape and that can read and write a single symbol on each move
It provide a powerful computational model for solving problems in computer
science and testing the limits of computation
Turing machines are similar to finite automata/finite state machines but have the
advantage of unlimited memory.
They are capable of simulating common computers; a problem that a common
computer can solve (given enough memory) will also be solvable using a Turing
machine, and vice versa.
Turing machines were invented by the esteemed computer scientist Alan Turing
in 1936.
It is like an algorithm, executes on an input string of bits.
At the beginning, the input string is written on the tape, the tape head points to
the first cell of the string, and all other cells are blank.

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 3

What a Turing Machine Does
 When the tape reads any particular symbol, it decides what to do
(what to write to the tape at that point and then which direction
to move in next) depending on the set of transition functions.
 A transition function is essentially a specific instruction line in a
Turing machine’s program. You can think of the set of transition
functions as the complete program that specifies what the Turing
machine should do on any valid input it receives.
 In practice, a transition function takes the following form
 What state I am in right now
 What symbol I just read
 What symbol I should write
 What state I should change to next
 Which direction I should move in next

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 4

 The Standard Turing Machine
 Although we can envision a variety of automata with complex and
sophisticated storage devices, a Turing machine's storage is actually quite
simple. It can be visualized as a single, one-dimensional array of cells, each of
which can hold a single symbol.
 This array extends indefinitely in both directions and is therefore capable of
holding an unlimited amount of information.
 The information can be read and changed in any order. We call such a storage
device a tape because it is analogous to the magnetic tapes used in older
computers.
 Definition

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 5

Definition Cont…

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 6

In the definition of a Turing machine, we assume that that is,
that the input alphabet is a subset of the tape alphabet, not including the
blank.
 Blanks are ruled out as input for reasons that will become apparent shortly.
The transition function δ is defined as δ : Q × Γ → Q × Γ × {L,R}.
Example below transition shows the situation before and after the move

The situation (a) before the move and (b) after the move.

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 7

We can think of a Turing machine as a rather simple computer.
It has a processing unit, which has a finite memory, and in its tape, it has a
secondary storage of unlimited capacity.
The instructions that such a computer can carry out are very limited: It can
sense a symbol on its tape and use the result to decide what to do next.
The only actions the machine can perform are to rewrite the current symbol,
to change the state of the control, and to move the read-write head.
 This small instruction set may seem inadequate for doing complicated
things, but this is not so. Turing machines are quite powerful in principle.
The transition function δ defines how this computer acts, and we often call it
the “program” of the machine.

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 8

 Cont….
Consider the Turing machine defined by
Q = {q0, q1},
Σ = {a, b},
Γ = {a, b, },
F= {q1}, and
δ (q0, a)= (q0, b, R),
δ (q0, b)= (q0, b, R),
δ (q0, )= (q1, , L),
If this Turing machine is started in state q0 with the symbol ‘a’ under the read write
head, the applicable transition rule is δ (q0,a)= (q0,b,R). Therefore, the read-write
head will replace ‘a’ with ‘b’ , then move right on the tape.
The machine will remain in state q0. Any subsequent a will also be replaced with a b,
but b's will not be modified. When the machine encounters the first blank, it will
move left one cell, then halt in final state q1

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 9

Since one can make several different definitions of a Turing
machine, it is worthwhile to summarize the main features of
standard Turing machine:
1. The Turing machine has a tape that is unbounded in both
directions, allowing any number of left and right moves.
2. The Turing machine is deterministic in the sense that δ defines
at most one move for each configuration.
3. There is no special input file. We assume that at the initial time
the tape has some specified content. Some of this may be
considered input. Similarly, there is no special output device.
Whenever the machine halts, some or all of the contents of the
tape may be viewed as an output.

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 10

 Operation of Turing Machine

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 11

 Construction of A Turing Machine
Tape
...... ......

Read-Write head
Control Unit

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 12

 The Tape
No boundaries -- infinite length
...... ......

Read-Write head

The head moves Left or Right

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 13

 ...... ......

Read-Write head

The head at each transition (time step):

1. Reads a symbol
2. Writes a symbol
3. Moves Left or Right
davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 14
Example:
Time 0
...... a b a c ......

Time 1
...... a b k c ......

1. Reads a
2. Writes k
3. Moves Left
davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 15
 Time 1
...... a b k c ......

Time 2
...... a f k c ......

1. Reads b
2. Writes f
3. Moves Right

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 16

 The Input String
Input string Blank symbol

......   a b a c    ......

head
Head starts at the leftmost position
of the input string

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 17

States & Transitions
Read Write Move Left

q1 a  b, L q2

Move Right

q1 a  b, R q2
davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 18
Example:1
Time 1
......   a b a c    ......

q1
current state
q1 a  b, R q2

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 19

Example:2
Time 1
......   a b a c    ......

q1
q1 a  b, L q2

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 20

Example:3
Time 1
......   a b a c    ......

q1

Time 2
......   a b b c g   ......

q2

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 21

 Turing Machines are deterministic
Determinism
Allowed Not Allowed
a  b, R q2 a  b, R q2

q1 q1
q3 a  d, L q3
b  d, L

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 22

Example:
Partial Transition Function
......   a b a c    ......

q1
a  b, R q2 Allowed:

q1 No transition
for input symbol c
b  d, L q3

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 23

Halting

The machine halts in a state if there is

no transition to follow

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 24

Halting Example 1:

......   a b a c    ......

q1

q1 No transition from q1
HALT!!!

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 25

Halting Example 2:

......   a b a c    ......

q1

a  b, R q2
No possible transition
q1 from q1 and symbol c
q3
b  d, L HALT!!!
davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 26
Accepting States
q1 q2
Allowed

q1 q2 Not Allowed

•Accepting states have no outgoing transitions

•The machine halts and accepts

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 27

 Acceptance
If machine halts
Accept Input
string in an accept state

If machine halts
in a non-accept state
Reject Input or
string
If machine enters
an infinite loop
davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 28
Observation:
In order to accept an input string,
it is not necessary to scan all the
symbols in the string

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 29

Turing Machine Example
Input alphabet   {a , b }

Accepts the language: a*

a  a, R

  , L
q0 q1

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 30

Time 0   a a a  

q0

a  a, R

  , L
q0 q1

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 31

Time 1   a a a  

q0

a  a, R

  , L
q0 q1

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 32

Time 2   a a a  

q0

a  a, R

  , L
q0 q1

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 33

Time 3   a a a  

q0

a  a, R

  , L
q0 q1

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 34

Time 4   a a a  

q1

a  a, R Halt & Accept

  , L
q0 q1

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 35

Rejection Example

Time 0   a b a  

q0
a  a, R

  , L
q0 q1

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 36

Time 1   a b a  

q0

No possible Transition
a  a, R Halt & Reject

  , L
q0 q1

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 37

A simpler machine for same language
but for input alphabet   {a }

Accepts the language: a*

q0

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 38

Time 0   a a a  

q0

Halt & Accept

q0

Not necessary to scan input

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 39
Infinite Loop Example
A Turing machine
a * b ( a  b ) *
for language
b  b, L
a  a, R

  , L
q0 q1

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 40

Time 0   a b a  

q0

b  b, L
a  a, R

  , L
q0 q1

WSU, COMPUTER SCIENCE

davidtechnotips.com 41
DEPARTMENT
Time 1   a b a  

q0

b  b, L
a  a, R

  , L
q0 q1

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 42

Time 2   a b a  

q0

b  b, L
a  a, R

  , L
q0 q1

WSU, COMPUTER SCIENCE

davidtechnotips.com 43
DEPARTMENT
Time 2   a b a  
q0
Time 3   a b a  

Infinite loop
q0

Time 4   a b a  
q0

Time 5   a b a  
q0
WSU, COMPUTER SCIENCE
davidtechnotips.com 44
DEPARTMENT
Because of the infinite loop:

•The accepting state cannot be reached

•The machine never halts

•The input string is rejected

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 45

 JFLAP (Java Formal Languages and
Automata Package)

JFLAP (Java Formal Languages and Automata

Package) is interactive educational software
written in Java for experimenting with topics in
the computer science area of formal languages and
automata theory,
JFLAP is software for experimenting with formal
languages topics including nondeterministic finite
automata, nondeterministic pushdown automata,
multi-tape Turing machines, several types of
grammars, parsing

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 46

 In addition to constructing and testing
examples for these, JFLAP allows one to
experiment with construction proofs from one
form to another, such as converting an NFA
to a DFA to a minimal state DFA to a
regular expression or regular grammar.
 Get the simulator(JFLAP)
http://davidtechnotips.com/Resources/
 Read for more understanding…
http://www.jflap.org

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 47

 Another Turing Machine Example
n n
Turing machine for the language L= {a b } Q={q0,q1,q2,q3,q4}
a a bb
Algorithm:
1. Match a’s with b’s:
2. Repeat:
3. replace leftmost a with x
4. find leftmost b and replace it with y
5. Repeat Until there are no more a’s or b’s
6. If there is a remaining a or b reject

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 48

 Another Turing Machine Example
n n
Turing machine for the language L= {a b }
n 1
q4 y  y, R y  y, L
y  y, R a  a, R a  a, L
  , L

y  y, R a  x, R b  y, L
q3 q0 q1 q2
x  x, R

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 49

 Time 0  a a b b  

q0
q4 y  y, R y  y, L
y  y, R a  a, R a  a, L
  , L
y  y, R a  x, R b  y, L
q3 q0 q1 q2
x  x, R

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 50

Time 1  x a b b  

q1
q4 y  y, R y  y, L
y  y, R a  a, R a  a, L
  , L
y  y, R a  x, R b  y, L
q3 q0 q1 q2
x  x, R

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 51

Time 2  x a b b  

q1
q4 y  y, R y  y, L
y  y, R a  a, R a  a, L
  , L
y  y, R a  x, R b  y, L
q3 q0 q1 q2
x  x, R

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 52

 Time 3  x a y b  

q2
q4 y  y, R y  y, L
y  y, R a  a, R a  a, L
  , L

y  y, R a  x, R b  y, L
q3 q0 q1 q2
x  x, R

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 53

 Time 4  x a y b  

q2
q4 y  y, R y  y, L
y  y, R a  a, R a  a, L
  , L

y  y, R a  x, R b  y, L
q3 q0 q1 q2
x  x, R

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 54

 Time 5  x a y b  

q0
q4 y  y, R y  y, L
y  y, R a  a, R a  a, L
  , L

y  y, R a  x, R b  y, L
q3 q0 q1 q2
x  x, R

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 55

 Time 6  x x y b  

q1
q4 y  y, R y  y, L
y  y, R a  a, R a  a, L
  , L

y  y, R a  x, R b  y, L
q3 q0 q1 q2
x  x, R

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 56

Time 7  x x y b  

q1
q4 y  y, R y  y, L
y  y, R a  a, R a  a, L
  , L
y  y, R a  x, R b  y, L
q3 q0 q1 q2
x  x, R

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 57

Time 8  x x y y  

q2

q4 y  y, R y  y, L
y  y, R a  a, R a  a, L
  , L

y  y, R a  x, R b  y, L
q3 q0 q1 q2
x  x, R

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 58

Time 9  x x y y  

q2
q4 y  y, R y  y, L
y  y, R a  a, R a  a, L
  , L
y  y, R a  x, R b  y, L
q3 q0 q1 q2
x  x, R

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 59

 Time 10  x x y y  

q0
q4 y  y, R y  y, L
y  y, R a  a, R a  a, L
  , L

y  y, R a  x, R b  y, L
q3 q0 q1 q2
x  x, R

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 60

Time 11  x x y y  

q3
q4 y  y, R y  y, L
y  y, R a  a, R
  , L a  a, L

y  y, R a  x, R b  y, L
q3 q0 q1 q2
x  x, R

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 61

 Time 12  x x y y  

q3

q4 y  y, R y  y, L
y  y, R a  a, R a  a, L
  , L

y  y, R a  x, R b  y, L
q3 q0 q1 q2
x  x, R

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 62

 Time 13  x x y y  

q4
Halt & Accept

q4 y  y, R y  y, L
y  y, R a  a, R a  a, L
  , L

y  y, R a  x, R b  y, L
q3 q0 q1 q2
x  x, R
davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 63
davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 64
The string abab, abb, aab, aaaabb is not accepted by the
TM, because it is not in the form of {a n b n }

The End

davidtechnotips.com WSU, COMPUTER SCIENCE DEPARTMENT 65