CSCI 3130: Formal languages
and automata theory
Tutorial 7
Chin
Reminder
• Homework 4 is due at 23:59, today!
Turing Machines
current state
q1
a/b L
q2
a b a ☐
…
Replace a with b, and move head left
new state
q1
a/b L
q2
a b b ☐
…
Turing Machines: Low-level Design
• Useful tools
1. Move to left/right until pointing to ‘x’
S = {a, b, x} G = {a, b, x, ☐}
a/a R
b/b R
a b a x b ☐
…
a b a x b ☐
…
q1
Turing Machines: Low-level Design
• Useful tools
2. Go to first symbol of the tape S = {a, b, x}
G = {a, b, x, a, b, x, ☐}
At the beginning


q0
x/x R

a/a R

b/b R
q1
Now, use tool 1.


a b a x b ☐
…
a b a x b ☐
…
Turing Machines: Low-level Design
• Useful tools
3. Go to last symbol of the tape S = {a, b, x}
Use component 1, then go 1 step to the left.
G = {a, b, x, ☐}
x/x R
a/a R
b/b R
q1
☐/☐
L
a b a x b ☐
…
a b a x b ☐
…
a b a x b ☐
…
Turing Machines
• Useful tips
1. Check if the input is in the right form to
•
reduce the possible inputs you have to deal with later
Turing Machines
• Exercise
1. L1 = {0n1n : n ≥ 0}
Turing Machines
L1 = {0n1n : n ≥ 0}
High-level idea:
If input is e, accept
Check if the string is of the form 00*11*
For each ‘0’
replace with ‘x’
find the first ‘1’ on the right and cross it
Check if everything on the tape is ‘x’
Turing Machines
L1 = {0n1n : n ≥ 0}
Implementation:
If input is e, accept
q0
☐/☐
R q
acc
Turing Machines
L1 = {0n1n : n ≥ 0}
Implementation:
Check if the string is of the form 00*11*
0/0 R
q0
0/0 R
q1
1/1 R
1/1 R
q2
☐/☐ L
Turing Machines
L1 = {0n1n : n ≥ 0}
Implementation:
Check if the string is of the form 00*11*
(Go back to the first position)
For each ‘0’
replace with ‘x’
find the first ‘1’ on the right and cross it
Check if everything on the tape is ‘x’
Turing Machines
L1 = {0n1n : n ≥ 0}
Implementation:
Go back to the first position
q0
0/0 L
1/1 L
q1

0/0 R
q1
Turing Machines
L1 = {0n1n : n ≥ 0}
Implementation:

For each ‘0’ (resp. ‘0’)

replace with ‘x’ (resp. ‘x’)
find the first ‘1’ on the right and cross it
Turing Machines
L1 = {0n1n : n ≥ 0}
Possible situations:

…

…
x 0 0 1 1 1 ☐
x 0 0 x 1 1 ☐

x x 0 x x ☐

x x x x 1 1 ☐
…
…
Turing Machines
L1 = {0n1n : n ≥ 0}
Implementation:

For each ‘0’ (resp. ‘0’)

replace with ‘x’ (resp. ‘x’)
find the first ‘1’ on the right and cross it
x/x R
0/0 R
q1 0/x R
q2 1/x L

…

…
x 0 0 x 1 1 ☐
q3
x x 0 x x 1 ☐
Turing Machines
L1 = {0n1n : n ≥ 0}
Implementation:

For each ‘0’ (resp. ‘0’)

replace with ‘x’ (resp. ‘x’)
find the first ‘1’ on the right and cross it
How to go back to the left after each iteration?
x/x R
0/0 R
q1 0/x R
q2 1/x L
x/x R
 
x/x
R
x/x L
q3 0/0 L
0/0 L

…

…
x x 0 x x 1 ☐
q4
x x 0 x x 1 ☐
Turing Machines
L1 = {0n1n : n ≥ 0}
Implementation:

For each ‘0’ (resp. ‘0’)

replace with ‘x’ (resp. ‘x’)
find the first ‘1’ on the right and cross it
What will happen after the last iteration?
x/x R
0/0 R
q1 0/x R
q2 1/x L
x/x R
 
x/x
R
x/x L
q3 0/0 L
0/0 L

…

…
x x x x x x ☐
q4
x x x x x x ☐
Turing Machines
L1 = {0n1n : n ≥ 0}
Implementation:
Check if everything on the tape is ‘x’
x/x R
q2
q1
q2
R q
acc
 
x/x R
0/0 R
0/x R
☐/☐
x/x L
1/x L
q3
x/x R
0/0 L
0/0 L
q4

x x x x x x ☐ ☐ …
x/x R
 
x/x R

x x x x x x ☐ ☐ …
Turing Machines
If input is e, accept
Check if the string is of the form 00*11*
(Go back to the first position)
For each ‘0’
replace with ‘x’
find the first ‘1’ on the right and cross it
Check if everything on the tape is ‘x’
L1 = {0n1n : n ≥ 0}
Implementation:
Putting everything together
x/x R
q2
x/x R
0/0 R
q1 0/x R
q2 1/x L
☐/☐
q0
R q
acc
☐/☐
 
x/x L
x/x R
q3 0/0 L
R q
acc
0/0 R
0/0 L
q0
q4
x/x R
 
x/x R
q0
0/0 L
1/1 L

0/0 R
0/0 R
q1
q1
q1
1/1 R
1/1 R
q2
☐/☐
L
Turing Machines
If input is e, accept
Check if the string is of the form 00*11*
(Go back to the first position)
For each ‘0’
replace with ‘x’
find the first ‘1’ on the right and cross it
Check if everything on the tape is ‘x’
L1 = {0n1n : n ≥ 0}
Implementation:
Putting everything together
☐/☐
R
0/0 R
q0
0/0 R

q1
0/0 L
1/1 L
1/1 R
1/1 R
q2
☐/☐
L
q3
x/x R
q8
 
0/x R
x/x R
0/0 R
q4 0/x R
q5 1/x L
x/x R
 
x/x R
 
x/x L
x/x R
q6 0/0 L
0/0 L
q7
☐/☐
R q
acc
Variants of Turing Machines
• Turning machine with left reset
– The machine’s head can move one symbol to the right, or
– jump to the leftest position of the tape
– It cannot move one symbol to the left
Show that it is equivalent to a Turing Machine.
Variants of Turing Machines
Show that TM with left reset is equivalent to a TM
• Two steps
1. Show how to simulate a TM with left reset on a TM
2. Show how to simulate a TM on a TM with left reset
Variants of Turing Machines
1. Show how to simulate a TM with left reset on a TM
•
•
How to go to first symbol of the tape? e.g. a/b reset



S = {a, b, x} G = {a, b, x, a, b, x, ☐}
At the beginning

q0
x/x R

a/a R

b/b R
To reset
x/x L
a/a L
b/b L
a b a x b ☐
…
a b a x b ☐
…
a b a x b ☐
…
a b a x b ☐
…
q1
q1
Variants of Turing Machines
1. Show how to simulate a TM with left reset on a TM
•
•
•
•
Every time you change the symbol in the first position
e.g. a / bR
Add dots to the symbols


e.g. a / bR
a b a x b ☐
…
a b a x b ☐
…
b b a x b ☐
…
b b a x b ☐
…
Variants of Turing Machines
2. Show how to simulate a TM on a TM with left reset
Idea:
First, mark the current position with a dot
Then reset and mark the first position with a *
Reset
While (the dot is not one symbol to the right of the * position)
Move the star to one position to the right
Now the star is at the position you want to reach
Remove the dot, reset, and go to the star position
*
.
…
.
…
…
* .
…
Variants of Turing Machines
While (the dot is not one symbol to the right of the * position)
Move the star to one position to the right
* .
• How?
1. reset
* .
2. Go to the * position
* .
3. Move one position to the right
4. If it is a dot, done
* * .
Else mark it with a *
* * .
5. reset
6. Find the first * and remove it
…
…
…
…
…
* * .
…
* .
…
Variants of Turing Machines
2. Show how to simulate a TM on a TM with left reset
•
e.g. a/x L
a b a x b ☐
…
a b x b b ☐
…
Variants of Turing Machines
2. Show how to simulate a TM on a TM with left reset
•
1.
2.
3.
4.
e.g. a/x L

a/x reset
*
a/a reset
*
a/a R
*
b/b reset
a b a x b ☐
…
a b x x b ☐
…
a* b x x b ☐
…
a* b x x b ☐
…
a* b* x x b ☐
…
Variants of Turing Machines
2. Show how to simulate a TM on a TM with left reset
• e.g. a/x L
*
5. a/a R
* *
6. b/b R

7. x/x reset
8. a/a R
Done.
a b* x x b ☐
…
a b* x x b ☐
…
a b* x x b ☐
…
End
• Questions?
Descargar

CSCI 3130: Formal languages and automata theory …