4/14/2011
Turing and State Machines • State Machines – Called non-writing machines – Have no control on their external input – Cannot “write” or change their inputs
Mesin Turing
• Turing Machine – after A. M. Turing – A writing machine • Finite State Machine capable of modifying its own input symbols
Dosen Pembina : Danang Junaedi
– Fundamental Theoretical Model of all digital computers
IF-UTAMA
Turing Machine
Turing Machines •
• Tape divided into squares – each contains a symbol (blank squares store a 0) • Head has 3 operations:
IF_UTAMA
A Turing machine possesses the following parts: 1. 2. 3. 4.
1. Read symbol in square being scanned 2. Write new symbol in scanned square 3. Shift tape 1 square in either direction
IF-UTAMA
2
3
An infinite tape, A control unit, A state register, A control unit.
IF-UTAMA
4
1
4/14/2011
Turing Machine (contd)
Cycle of Computation 1. 2. 3. 4. 5.
Tape 1
1
1
1
Head
Start in state Si Read symbol under head Write new symbol Shift left/right Enter new state Sj
Finite-State Control Unit
IF-UTAMA
5
IF-UTAMA
Turing machines [2]
Turing Machine (contd) •
Status controller
head
…
• •
Head bergeser ke kirikanan dengan kecepatan tak terbatas Head membaca/menulis data pada pita Panjang pita tak terbatas
on/off switch
input tape
"guts" of the machine
tape read head
accept or reject
…
Pita 1 dimensi dengan panjang tak terhingga
IF-UTAMA
IF_UTAMA
6
7
Remember our finite automaton? IF-UTAMA
8
2
4/14/2011
Turing machines [2]
on/off switch
input tape
Turing machines [2] • A Turing machine (tm) tm) is a finite automaton with a twist:
"guts" of the machine
tape read/write head
A Turing machine
tape head can move left or right.
– The tape head can move in either direction (left OR right) – A square on the input tape can be overwritten with another symbol – By the way, there is no stack!
accept or reject
tape head can read or write!
IF-UTAMA
9
Turing Machine Properties
IF_UTAMA
10
Standard Turing Machine
• Anything a Universal Turing Machine can do, a digital computer can do • Anything a Universal Turing Machine cannot do, a digital computer cannot do • Emulation – A Universal Turing Machine can mimic or emulate the behavior of any other Turing Machine (and therefore, so can a computer) • Halting Problem – A Universal Turing Machine (and therefore a computer) cannot predict when the computation of another Turing Machine will complete, and when it will not
IF-UTAMA
IF-UTAMA
M = (Q, ∑, Γ, δ, q0, B, F) Q: finite set of internal states Γ: finite set of symbols - tape alphabet B ∈ Γ: blank ∑ ⊆ Γ − {B}: finite set of symbols - input alphabet δ: Q × Γ → Q × Γ × {L, R}
transition function
q0 ∈ Q: initial state F ⊆ Q: set of final states
11
IF-UTAMA
12
3
4/14/2011
Turing Machine Example
Standard Turing Machine δ: Q × Γ → Q × Γ × {L, R} current symbol
replacing symbol
Present State A B C D Halt
head move direction
Example δ(q0, a) = (q1, d, R) current symbol
replacing symbol
0
0
0
0
1
Next State, Write, Shift 0 1 -B, 0, R C, 1, R B, 1, R D, 0, L Halt A, 0, R D, 1, L Halt Halt
1
1
0
0
0
1
1
1
1
0
0
1
1
1
0
0
1
1
1
1
0
0
^A
head move to the right
0
^C
0
0
0
1
1
1
0
0
1
1
1
1
0
0
0
0
0
0
1
1
1
0
1
1
1
1
0
0
0
0
0
0
0
1
1
1
1
1
1
0
0
^A
^C
1
^C IF-UTAMA
13
8. 9.
14
Definisi Formal [3]
Model Fisik Mesin Turing 1. 2. 3. 4. 5. 6. 7.
IF-UTAMA
Pita dapat bergerak dua arah. Sebelum masuk ke dalam mesin, pita harus sudah berisi input. Jendela C menunjukkan simbol yang sedang dibaca oleh head. Selain dapat membaca, head juga dapat menulis. Jendela Q menunjukkan status mesin setiap saat. Pada saat awal, head pada sel pertama dan dalam status awal. Berdasarkan simbol yang sedang terbaca dan statusnya, mesin dapat menuliskan simbol atau menggerakkan head ke kiri atau ke kanan. Mesin berhenti bekerja jika berada pada status berhenti (halt state). Mesin dikatakan berhenti secara tak wajar (abnormal termination) jika terjadi dua kondisi berikut : – Head diminta bergerak ke kiri namun head sedang berada di sel pertama. – Tidak ada aturan transisi yang dapat diterapkan 0
1
1
0
q
C
Q
5
IF-UTAMA
IF_UTAMA
15
IF-UTAMA
16
4
4/14/2011
Contoh [3]
IF-UTAMA
Contoh (contd) [3]
17
Contoh (contd) [3]
18
Contoh (contd) [3]
Studi Kasus • Bagaimana untuk string aabba, abba, abab? Buktikan…!!! IF-UTAMA
IF_UTAMA
19
IF-UTAMA
20
5
4/14/2011
Contoh (contd) [3]
Contoh (contd) [3] Tidak ada transisi lagi dari state q4, mesin Turing berhenti dan karena state q4 termasuk state akhir, maka input tersebut diterima.
IF-UTAMA
21
Deskripsi sesaat [3]
IF-UTAMA
22
Cara Mengkonstruksi Mesin Turing [4] 1. 2. 3. 4.
Buat skenario kerja mesin turing. Identifikasi status-status mesin (Q). Identifikasi Γ. Terjemahkan skenario kerja ke dalam aturan transisi.
Studi Kasus • Bagaimana untuk string 1100, 0101, 000111? Buktikan…!!!
IF-UTAMA
IF_UTAMA
23
IF-UTAMA
24
6
4/14/2011
Contoh Konstruksi Mesin Turing [4]
Contoh Konstruksi Mesin Turing [4]
Buat mesin turing yang mengenali bahasa L = {0n1n | n = 1, 2, 3, …} •
•
Langkah 1 : Buat Skenario Kerja Mesin Turing – Jika pada saat awal, head membaca 0, maka tuliskan X, cari 1 ke kanan. – Jika sedang mencari 1 ke kanan, head membaca 0, maka cari 1 ke kanan. – Jika sedang mencari 1 ke kanan, head membaca 1, maka tuliskan Y, cari X ke kiri. – Jika sedang mencari 1 ke kanan, head membaca Y, maka cari 1 ke kanan – Jika sedang mencari X ke kiri, head membaca 0, maka cari X ke kiri. – Jika sedang mencari X ke kiri, head membaca Y, maka cari X ke kiri. – Jika sedang mencari X ke kiri, head membaca X, maka head bergerak ke kanan, kembali ke saat awal. – Jika pada saat awal, head membaca Y, maka cari β ke kanan. – Jika sedang mencari β ke kanan, head membaca Y, cari β ke kanan. – Jika sedang mencari β ke kanan, head membaca β, maka tuliskan β dan berhenti. IF-UTAMA
• •
25
Contoh Konstruksi Mesin Turing [4] – – – – –
IF_UTAMA
IF-UTAMA
26
Studi Kasus
Jika sedang mencari X ke kiri, head membaca Y, maka cari X ke kiri’ : δ(r, Y) = (r, L) Jika sedang mencari X ke kiri, head membaca X, maka head bergerak ke kanan, kembali ke saat awal’ : δ(r, X) = (p, R) Jika pada saat awal, head membaca Y, maka cari β ke kanan’ δ(p, Y) = (s, R) Jika sedang mencari β ke kanan, head membaca Y, maka cari β ke kanan’ : δ(s, Y) = (s, R) Jika sedang mencari β ke kanan, head membaca β, maka tuliskan β dan berhenti’ : δ(s, β) = (t, β)
IF-UTAMA
Langkah 2 : Identifikasi Q – p = saat awal. – q = sedang mencari 1 ke kanan. – r = sedang mencari X ke kiri. – s = sedang mencari β ke kanan. – t = berhenti. Langkah 3 : Identifikasi Γ – Γ = {0, 1, X, Y, β}. Langkah 4 : Buat δ – Jika pada saat awal, head membaca 0, maka tulis X, cari 1 ke kanan’ : δ(p, 0) = (q, X), dan δ(q, X) = (q, R) – Jika sedang mencari 1 ke kanan, head membaca 0, maka cari 1 ke kanan’ : δ(q, 0) = (q, R) – Jika sedang mencari 1 ke kanan, head membaca 1, maka tuliskan Y, cari X ke kiri’ : δ(q, 1) = (r, Y), dan δ(r, Y) = (r, L) – Jika sedang mencari 1 ke kanan, head membaca Y, maka cari 1 ke kanan’ : δ(q, Y) = (q, R) – Jika sedang mencari X ke kiri, head membaca 0, maka cari X ke kiri’ : δ(r, 0) = (r, L)
27
1. Sederhanakan transisi pada mesin turing yang mengenali bahasa L = {0n1n | n = 1, 2, 3, …} di atas dalam bentuk tabel transisi 2. Berdasarkan mesin turing pada nomor 1 buktikan apakah string berikut ini diterima atau ditolak a. 000111 b. 00111 3. Buat Mesin Turing yang mengenali bahasa L = {0n1n01 | n = 1, 2, 3, …} 4. Buat Mesin Turing yang mengenali bahasa L = {0n12n | n = 1, 2, 3, …}
IF-UTAMA
28
7
4/14/2011
Referensi 1. 2. 3.
4.
Zvi Kohavi, Switching and Finite Automata Theory, McGraw-Hill, 2005 http://www.normanlandis.com/documents/CSCI3255/T uring%20Machines.ppt, Tanggal Akses : 25 April 2009 http://idhaclassroom.com/download/Teknik-OtomasiBahasa-Kompilasi/Bahasa-Kompilasi.pdf, Tanggal Akses 14 Januari 2009 Roni Djuliawan, M.T., “Diktat & Handout Kuliah Teori Bahasa & Otomata”, Teknik Informatika – Universitas Widyatama, 2003
IF-UTAMA
IF_UTAMA
29
8
