```Language Recognition (11.4)
and Turing Machines (11.5)
Longin Jan Latecki
Temple University
Based on slides by Costas Busch from the course
http://www.cs.rpi.edu/courses/spring05/modcomp/
and …
1
Three Equivalent Representations
Regular
expressions
Finite
automata
Each
can
describe
the others
Regular
languages
Kleene’s Theorem:
For every regular expression, there is a deterministic
finite-state automaton that defines the same
language, and vice versa.
2
NFAs  Regular grammars
Thus, the language recognized by FSA
is a regular language
Every NFA can be converted into a corresponding regular
grammar and vice versa.
Each symbol A of the grammar is associated with a nonterminal node of the NFA sA, in particular, start symbol
S is associated with the start state sS.
Every transition is associated with a grammar production:
T(sA,a) = sB  A  aB.
Every production B   is associated with final state sB.
See Ex. 3, p. 771, and Ex. 4, p. 772.
3
Kleene’s Theorem
Languages
Generated by
Regular Expressions

Languages
Recognized
by FSA
4
We will show:
Languages
Generated by
Regular Expressions

Languages
Recognized
by FSA
Languages
Generated by
Regular Expressions

Languages
Recognized
by FSA
5
Proof - Part 1
Languages
Generated by
Regular Expressions

Languages
Recognized
by FSA
For any regular expression r
the language L (r ) is recognized
by FSA (= is a regular language)
Proof by induction on the size of r
6
Induction Basis
Primitive Regular Expressions:  ,  , 
NFAs
L ( M 1 )    L ( )
L ( M 2 )  { }  L (  )
a
regular
languages
L ( M 3 )  {a}  L ( a )
7
Inductive Hypothesis
Assume
for regular expressions r1 and r2
that
L ( r1 ) and L ( r2 ) are regular languages
8
Inductive Step
We will prove:
L  r1  r2 
L  r1  r2 
L  r1 * 
Are regular
Languages
L   r1  
9
By definition of regular expressions:
L  r1  r2   L  r1   L  r2 
L  r1  r2   L  r1  L  r2 
L  r1 *    L  r1   *
L   r1    L  r1 
10
By inductive hypothesis we know:
L ( r1 ) and L ( r2 ) are regular languages
We need to show:
Regular languages are closed under:
Union
L  r1   L  r2 
Concatenation L  r1  L  r2 
Star
 L  r1   *
11
Therefore:
L  r1  r2   L  r1   L  r2 
L  r1  r2   L  r1  L  r2 
Are regular
languages
L  r1 *    L  r1   *
And trivially: L (( r1 )) is a regular language
12
Proof - Part 2
Languages
Generated by
Regular Expressions

Languages
Recognized
by FSA
For any regular language L there is
a regular expression r with L ( r )  L
Proof by construction of regular expression
13
Since L is regular take the
NFA M that accepts it
L(M )  L
Single final state
14
From M construct the equivalent
Generalized Transition Graph
in which transition labels are regular expressions
Example:
M
a
c
a,b
a
c
ab
15
b
b
Another Example:
a
q1
q0
a,b
q2
b
a
q0
b
b
q1 a  b
q2
b
16
Reducing the states:
a
q0
b
b
q1 a  b
q2
b
bb * a
q0
b
bb * ( a  b )
q2
17
Resulting Regular Expression:
bb * a
q0
b
bb * ( a  b )
q2
r  ( bb * a ) * bb * ( a  b ) b *
L (r )  L (M )  L
18
In General
Removing states:
e
c
d
qi
qj
q
a
b
ae * d
ce * b
ce * d
qj
qi
ae * b
19
The final transition graph:
r4
r1
r3
q0
r2
qf
The resulting regular expression:
r  r1 * r2 ( r4  r3 r1 * r2 ) *
L (r )  L (M )  L
20
Models of computing
DFA
Push down automata
Bounded Turing M’s
Turing machines
-
regular languages
Context-free
Context sensitive
Phrase-structure
21
Foundations
The theory of
computation and the
practical application it
computer — was
developed by an
Englishman called Alan
Turing.
22
Alan Turing
London
1939-42: Breaking of U-boat Enigma,
saving battle of the Atlantic
College, Cambridge University
1946: Computer and software design
1932-35: Quantum mechanics,
probability, logic
1948: Manchester University
1936: The Turing machine,
computability, universal machine
1936-38: Princeton University. Ph.D.
Logic, algebra, number theory
Introduced to German Enigma cipher
machine
1939-40: The Bombe, machine for
Enigma decryption
1949: First serious mathematical use
of a computer
1950: The Turing Test for machine
intelligence
1952: Arrested as a homosexual, loss
of security clearance
1954 (7 June): Death (suicide) by
cyanide poisoning, Wilmslow, Cheshire.
—from Andrew Hodges
http://www.turing.org.uk/turing/
23
The Decision Problem
In 1928 the German mathematician,
whether there could be a mechanical
way (i.e. by means of a fully specifiable
set of instructions) of determining
whether some statement in a formal
system like arithmetic was provable or
not.
In 1936 Turing published a paper the
aim of which was to show that there
was no such method.
“On computable numbers, with an
application to the Entscheidungs
problem.” Proceedings of the
London Mathematical Society,
2(42):230-265).
24
The Turing Machine
In order to argue for this claim,
he needed a clear concept of
“mechanical procedure.”
His idea — which came to be
called the Turing machine — was
this:
(1) A tape of infinite length
(2) Finitely many squares of
the tape have a single
symbol from a finite
language.
(3) Someone (or something)
and write in them.
(4) At any time, the machine is in
one of a finite number of
internal states.
(5) The machine has instructions
that determine what it does
given its internal state and
the symbol it encounters on
the tape. It can
 change its internal state;
 change the symbol on the
square;
 move forward;
 move backward;
 halt (i.e. stop).
25
Current state = 10
If current state = 1
and current symbol = 0
then new state = 10
new symbol = 1
move right
1
0
1
1
1
26
Current state = 10
If current state = 1
and current symbol = 0
then new state = 10
new symbol = 1
move right
1
1
1
1
1
27
Current state = 10
If current state = 1
and current symbol = 0
then new state = 10
new symbol = 1
move right
1
1
1
1
1
28
Functions
It is essential to the idea of a Turing
machine that it is not a physical machine, but
an abstract one — a set of procedures.
It makes no difference whether the machine
is embodied by a person in a boxcar on a
track, or a person with a paper and pencil, or
a smart and well-trained flamingo.
29
Turing’s Theorem
In the 1936 paper Turing proved that there are “generalpurpose” Turing machines that can compute whatever any
other Turing machine.
This is done by coding the function of the special-purpose
machine as instructions of the other machine — that is by
“programming” it. This is called Turing’s theorem.
These are universal Turing machines, and the idea of a
coding for a particular function fed into a universal Turing
machine is basically our conception of a computer and a
stored program.
The concept of the universal Turing machine is just the
concept of the computer as we know it.
30
First computers: custom computing
machines
Control
Work tape (memory)
1950 -- Eniac: the control
is hardwired manually for
each problem.
Output tape (write only)
1940:
VON NEUMANN:
DISTINCTION BETWEEN DATA AND INSTRUCTIONS
31
Can Machines Think?
In “Computing machinery and intelligence,” written
in 1950, Turing asks whether machines can think.
He claims that this question is too vague, and
proposes, instead, to replace it with a different
one.
That question is: Can machines pass the “imitation
game” (now called the Turing test)? If they can,
they are intelligent.
Turing is thus the first to have offered a rigorous
test for the determination of intelligence quite
generally.
32
The Turing Test
The game runs as follows. You sit at a computer
terminal and have an electronic conversation. You
don’t know who is on the other end; it could be a
person or a computer responding as it has been
programmed to do.
If you can’t distinguish between a human being and
a computer from your interactions, then the
computer is intelligent.
Note that this is meant to be a sufficient condition of
intelligence only. There may be other ways to be
intelligent.
33
Artificial Intelligence
34
The Church-Turning Thesis
Turing, and a logician
called Alonzo Church
(1903-1995),
independently developed
the idea (not yet proven
by widely accepted) that
whatever can be
computed by a
mechanical procedure
can be computed by a
Turing machine.
This is known as the
Church-Turing thesis.
35
AI: The Argument
We’ve now got the materials to show that AI is possible:
P1: Any function that can be computed by a mechanical procedure can be
computed by a Turing machine. (Church-Turing thesis)
P2: Thinking is nothing more than the computing of functions by
mechanical procedures (i.e., thinking is symbol manipulation).
(Functionalist-Computationalist thesis)
C1: Therefore, thinking can be performed by a Turing machine.
P3: Turing machines are multiply realizable. In particular, they can be
realized by computers, robots, etc.

It is possible to build a computer, robot, etc. that can think. That is,
AI is possible.
36
Turing Machines
37
The Language Hierarchy
n n n
a b c
?
ww ?
Context-Free Languages
n n
a b
ww
R
Regular Languages
a*
a*b*
38
Languages accepted by
Turing Machines
ww
n n n
a b c
Context-Free Languages
n n
a b
ww
R
Regular Languages
a*
a*b*
39
Tape
......
A Turing Machine
......
Control Unit
40
The Tape
No boundaries -- infinite length
......
......
The head moves Left or Right
41
......
......
The head at each time step:
2. Writes a symbol
3. Moves Left or Right
42
Example:
......
......
Time 0
a
b
a
c
......
c
......
Time 1
a
b k
2. Writes k
3. Moves Left
43
......
......
Time 1
a
b k
c
......
c
......
Time 2
a
f
k
2. Writes f
3. Moves Right
44
The Input String
Input string
......

 a
b
a c
Blank symbol
 

......
Head starts at the leftmost position
of the input string
45
Input string
......

 a
b
a c
Blank symbol
 

......
Remark: the input string is never empty
46
States & Transitions
q1
Write
a  b, L
Move Left
q2
Move Right
q1
a  b, R
q2
47
Example:
Time 1
......

 a
b
a c
 

......
q1
current state
q1
a  b, R
q2
48
......
Time 1

 a
b
a c
 

......
 

......
q1
......
Time 2

 a
b
b c
q2
q1
a  b, R
q2
49
Example:
......
Time 1

 a
b
a c
 

......
 

......
q1
......
Time 2

 a
b
b c
q2
q1
a  b, L
q2
50
Example:
......
Time 1


a
b
a c
 

......

......
q1
......
Time 2


a
b
b c
g 
q2
q1
  g,R
q2
51
Determinism
Turing Machines are deterministic
Not Allowed
Allowed
a  b, R
q2
a  b, R
q2
a  d,L
q3
q1
q1
b  d,L
q3
No lambda transitions allowed
52
Partial Transition Function
Example:
......

 a
b
a c
 

......
q1
a  b, R
q2
q1
b  d,L
q3
Allowed:
No transition
for input symbol c
53
Halting
The machine halts if there are
no possible transitions to follow
54
Example:
......

 a
b
a c
 

......
q1
a  b, R
q2
q1
b  d,L
q3
No possible transition
HALT!!!
55
Final States
q1
q2
Allowed
q1
q2
Not Allowed
• Final states have no outgoing transitions
• In a final state the machine halts
56
Acceptance
Accept Input
If machine halts
in a final state
Reject Input
If machine halts
in a non-final state
or
If machine enters
an infinite loop
57
Turing Machine Example
A Turing machine that accepts the language:
aa *
a  a, R
q0
  , L
q1
58
Time 0


a
a
a 

q0
a  a, R
q0
  , L
q1
59
Time 1


a
a
a 

q0
a  a, R
q0
  , L
q1
60
Time 2


a
a 
a

q0
a  a, R
q0
  , L
q1
61
Time 3


a
a
a 

q0
a  a, R
q0
  , L
q1
62
Time 4


a
a 
a

q1
a  a, R
q0
Halt & Accept
  , L
q1
63
Rejection Example
Time 0


a
b
a 

q0
a  a, R
q0
  , L
q1
64
Time 1


a
b
a 

q0
No possible Transition
Halt & Reject
a  a, R
q0
  , L
q1
65
Infinite Loop Example
A Turing machine
for language aa *  b ( a  b ) *
b  b, L
a  a, R
q0
  , L
q1
66
Time 0


a
b
a 

q0
b  b, L
a  a, R
q0
  , L
q1
67
Time 1


a
b
a 

q0
b  b, L
a  a, R
q0
  , L
q1
68
Time 2


a
b
a 

q0
b  b, L
a  a, R
q0
  , L
q1
69
Time 2


a
b
a 

b
a 

b
a 

b
a 

q0


a
q0
Time 4


a
q0
Time 5


a
q0
Infinite loop
Time 3
70
Because of the infinite loop:
•The final state cannot be reached
•The machine never halts
•The input is not accepted
71
Another Turing Machine Example
Turing machine for the language
y  y, R
q3
q4
  , L
y  y, R
q0
n n
{a b }
y  y, R
y  y, L
a  a, R
a  a, L
a  x, R
q1
b  y, L
q2
x  x, R
72
Time 0
 a a b b  
q0
y  y, R
q3
q4
  , L
y  y, R
q0
y  y, R
y  y, L
a  a, R
a  a, L
a  x, R
q1
b  y, L
q2
x  x, R
73
Time 1
 x a b b  
q1
y  y, R
q3
q4
  , L
y  y, R
q0
y  y, R
y  y, L
a  a, R
a  a, L
a  x, R
q1
b  y, L
q2
x  x, R
74
Time 2
 x a b b  
q1
y  y, R
q3
q4
  , L
y  y, R
q0
y  y, R
y  y, L
a  a, R
a  a, L
a  x, R
q1
b  y, L
q2
x  x, R
75
Time 3
 x a
y b  
q2
y  y, R
q3
q4
  , L
y  y, R
q0
y  y, R
y  y, L
a  a, R
a  a, L
a  x, R
q1
b  y, L
q2
x  x, R
76
Time 4
 x a
y b  
q2
y  y, R
q3
q4
  , L
y  y, R
q0
y  y, R
y  y, L
a  a, R
a  a, L
a  x, R
q1
b  y, L
q2
x  x, R
77
Time 5
 x a
y b  
q0
y  y, R
q3
q4
  , L
y  y, R
q0
y  y, R
y  y, L
a  a, R
a  a, L
a  x, R
q1
b  y, L
q2
x  x, R
78
Time 6
 x x
y b  
q1
y  y, R
q3
q4
  , L
y  y, R
q0
y  y, R
y  y, L
a  a, R
a  a, L
a  x, R
q1
b  y, L
q2
x  x, R
79
Time 7
 x x
y b  
q1
y  y, R
q3
q4
  , L
y  y, R
q0
y  y, R
y  y, L
a  a, R
a  a, L
a  x, R
q1
b  y, L
q2
x  x, R
80
Time 8
 x x
y y  
q2
y  y, R
q3
q4
  , L
y  y, R
q0
y  y, R
y  y, L
a  a, R
a  a, L
a  x, R
q1
b  y, L
q2
x  x, R
81
Time 9
 x x
y y  
q2
y  y, R
q3
q4
  , L
y  y, R
q0
y  y, R
y  y, L
a  a, R
a  a, L
a  x, R
q1
b  y, L
q2
x  x, R
82
Time 10
 x x
y y  
q0
y  y, R
q3
q4
  , L
y  y, R
q0
y  y, R
y  y, L
a  a, R
a  a, L
a  x, R
q1
b  y, L
q2
x  x, R
83
Time 11
 x x
y y  
q3
y  y, R
q3
q4
  , L
y  y, R
q0
y  y, R
y  y, L
a  a, R
a  a, L
a  x, R
q1
b  y, L
q2
x  x, R
84
Time 12
 x x
y y  
q3
y  y, R
q3
q4
  , L
y  y, R
q0
y  y, R
y  y, L
a  a, R
a  a, L
a  x, R
q1
b  y, L
q2
x  x, R
85
Time 13
 x x
y y  
q4
Halt & Accept
y  y, R
q3
q4
  , L
y  y, R
q0
y  y, R
y  y, L
a  a, R
a  a, L
a  x, R
q1
b  y, L
q2
x  x, R
86
Observation:
If we modify the
n n
machine for the language { a b }
we can easily construct
n n n
a machine for the language { a b c }
87
Formal Definitions
for
Turing Machines
88
Transition Function
q1
a  b, R
q2
 ( q1 , a )  ( q 2 , b , R )
89
Transition Function
q1
c  d,L
q2
 ( q1 , c )  ( q 2 , d , L )
90
Turing Machine:
States
Input
alphabet
Tape
alphabet
M  (Q ,  ,  ,  , q 0 ,  , F )
Transition
function
Initial
state
Final
states
blank
91
Configuration


c
a
b
a 

q1
Instantaneous description:
ca q1 ba
92
Time 4
 x a
q2
A Move:
Time 5
y b  
 x a
y b  
q0
q 2 xayb  x q 0 ayb
93
Time 4
 x a
y b  
q2
 x a
y b  
q0
Time 6
 x x
Time 5
y b  
q1
Time 7
 x x
y b  
q1
q 2 xayb  x q 0 ayb  xx q1 yb  xxy q1 b
94
q 2 xayb  x q 0 ayb  xx q1 yb  xxy q1 b

Equivalent notation:
q 2 xayb  xxy q1 b
95
Initial configuration:
q0 w
Input string
w
 a a b b  
q0
96
The Accepted Language
For any Turing Machine
L ( M )  {w :
M

q 0 w  x1 q f x 2 }
Initial state
Final state
97
Standard Turing Machine
The machine we described is the standard:
• Deterministic
• Infinite tape in both directions
•Tape is the input/output file
98
Computing Functions
with
Turing Machines
99
A function
f (w)
Result Region: S
Domain: D
w D
has:
f (w)
f (w)  S
100
A function may have many parameters:
Example:
f ( x, y )  x  y
101
Integer Domain
Decimal:
5
Binary:
101
Unary:
11111
We prefer unary representation:
easier to manipulate with Turing machines
102
Definition:
f
A function
is computable if
there is a Turing Machine M such that:
Initial configuration

w

q 0 initial state
Final configuration

f (w)

q f final state
For all w  D Domain
103
In other words:
f
A function
is computable if
there is a Turing Machine M such that:

q0 w
Initial
Configuration

q f f (w)
Final
Configuration
For all w  D Domain
104
Example
The function f ( x , y )  x  y
x, y
is computable
are integers
Turing Machine:
Input string:
x0 y
unary
Output string:
xy 0
unary
105
y
x
Start
 1
1

1 0 1

1

q0
initial state
The 0 is the delimiter that
separates the two numbers
106
y
x
Start
 1
1


1 0 1
1

q 0 initial state
x y
Finish
 1
qf
1

1
1 0 
final state
107
The 0 helps when we use
the result for other operations
x y
Finish
 1
qf
1

1
1 0 
final state
108
Turing machine for function
1  1, R
f ( x, y )  x  y
1  1, R



,
L
0

1
,
R
q1
q0
1  1, L
q 2 1  0, L
q3
  , R
q4
109
Execution Example:
x  11
y  11
(2)
(2)
Time 0
x
 1
y
1 0 1 1

q0
Final Result
x y
 1
q4
1 1 1 0 
110
Time 0
 1
1 0 1 1

q0
1  1, R
1  1, R



,
L
0

1
,
R
q1
q0
1  1, L
q 2 1  0, L
q3
  , R
q4
111
Time 1
 1
1 0 1 1 
q0
1  1, R
1  1, R



,
L
0

1
,
R
q1
q0
1  1, L
q 2 1  0, L
q3
  , R
q4
112
Time 2
 1
1 0 1 1

q0
1  1, R
1  1, R



,
L
0

1
,
R
q1
q0
1  1, L
q 2 1  0, L
q3
  , R
q4
113
Time 3
 1
1 1
1 1 
q1
1  1, R
1  1, R



,
L
0

1
,
R
q1
q0
1  1, L
q 2 1  0, L
q3
  , R
q4
114
Time 4
 1
1 1 1 1

q1
1  1, R
1  1, R



,
L
0

1
,
R
q1
q0
1  1, L
q 2 1  0, L
q3
  , R
q4
115
Time 5
 1
1 1
1 1 
q1
1  1, R
1  1, R



,
L
0

1
,
R
q1
q0
1  1, L
q 2 1  0, L
q3
  , R
q4
116
Time 6
 1
1 1 1 1

q2
1  1, R
1  1, R



,
L
0

1
,
R
q1
q0
1  1, L
q 2 1  0, L
q3
  , R
q4
117
Time 7
 1
1 1
1 0 
q3
1  1, R
1  1, R



,
L
0

1
,
R
q1
q0
1  1, L
q 2 1  0, L
q3
  , R
q4
118
Time 8
 1
1 1 1 0

q3
1  1, R
1  1, R



,
L
0

1
,
R
q1
q0
1  1, L
q 2 1  0, L
q3
  , R
q4
119
Time 9
 1
1 1
1 0 
q3
1  1, R
1  1, R



,
L
0

1
,
R
q1
q0
1  1, L
q 2 1  0, L
q3
  , R
q4
120
Time 10
 1
1 1 1 0

q3
1  1, R
1  1, R



,
L
0

1
,
R
q1
q0
1  1, L
q 2 1  0, L
q3
  , R
q4
121
Time 11
 1
1 1
1 0 
q3
1  1, R
1  1, R



,
L
0

1
,
R
q1
q0
1  1, L
q 2 1  0, L
q3
  , R
q4
122
Time 12
 1
1 1 1 0

q4
1  1, R
1  1, R



,
L
0

1
,
R
q1
q0
1  1, L
q 2 1  0, L
q3
  , R
HALT & accept
q4
123
Another Example
The function
f ( x)  2 x
x
is computable
is integer
Turing Machine:
Input string:
Output string:
x
unary
xx
unary
124
x
Start
 1
1

1 
q 0 initial state
2x
Finish
 1
qf
1

1
1 1 
final state
125
Turing Machine Pseudocode for f ( x )  2 x
• Replace every 1 with \$
• Repeat:
• Find rightmost \$, replace it with 1
• Go to right end, insert 1
Until no more \$ remain
126
Turing Machine for f ( x )  2 x
1  \$, R
1  1, L
1  1, R



,
L
\$

1
,
R
q
q0
1
  , R
q2
  1, L
q3
127
Example
Start
 1
1 
Finish
 1
q0
1 1
1 
q3
1  \$, R
1  1, L
1  1, R



,
L
\$

1
,
R
q
q0
1
  , R
q3
q2
  1, L
128
Another Example
The function
is computable
1
if x  y
0
if x  y
f ( x, y ) 
129
Turing Machine for
1
if x  y
0
if x  y
f ( x, y ) 
Input:
Output:
x0 y
1
or
0
130
Turing Machine Pseudocode:
• Repeat
Match a 1 from x with a 1 from y
Until all of x
or y is matched
• If a 1 from x is not matched
erase tape, write 1
(x  y)
else
erase tape, write 0
(x  y)
131
Combining Turing Machines
132
Block Diagram
input
Turing
Machine
output
133
Example:
x y
if x  y
0
if x  y
f ( x, y ) 
x, y
x, y
Comparer
x y
Eraser
0
x y
x y
134
```