BAB I
PENDAHULUAN
A.
Latar
Belakang
Teori bahasa dan automata merupakan
salah satu mata kuliah yang wajib dijurusan-jurusan sistem informasi maupun
ilmu komputer. Diasumsikan para pembaca telah terbiasa dengan notasi-notasi
yang digunakan disini, misalnya mengenai hinpunan, yang telah diperoleh dari
kuliah-kuliah sebelumnya. Meskipun demikian bagi mereka diluar disiplin
informatika dapat pula segera memahaminya karena telah diusahakan untuk sebisa
mungkin memberikan penjelasan yang memadai untuk setiap hal baru yang
disampaikan.
Dimakalah ini kami akan fokus untuk
menjelaskan berbagai hal mengenai Teori bahasa dan automata. Sub-sub dari teori
bahasa dan automata ini seperti String, Grammar dan Mesin turing pun akan kami
jelaskan dalam makalah ini.
B.
Rumusan
Masalah
Kita harus mengerti dan memahami tentang :
1. Apa
itu teori bahasa?
2. Apa
itu otomata?
3. Apa
itu string?
4. Apa
itu grammar?
5. Apa
itu mesin turing?
BAB II
PEMBAHASAN
A.
TEORI
BAHASA DAN AUTOMATA
1.
Teori
Bahasa
Teori bahasa membicarakan bahasa formal (formal language),
terutama untuk kepentingan perancangan kompilator (compiler) dan pemroses
naskah (text processor). Bahasa formal adalah kumpulan kalimat. Semua kalimat
dalam sebuah bahasa dibangkitkan oleh sebuah tata bahasa (grammar) yang sama.
Sebuah bahasa formal bisa dibangkitkan oleh dua atau lebih tata bahasa berbeda.
Dikatakan bahasa formal karena grammar diciptakan mendahului pembangkitan
setiap kalimatnya. Bahasa manusia bersifat sebaliknya; grammar diciptakan untuk
meresmikan kata-kata yang hidup di masyarakat. Dalam pembicaraan selanjutnya
‘bahasa formal’ akan disebut ‘bahasa’ saja.
2.
Automata
Automata adalah mesin abstrak yang dapat mengenali
(recognize), menerima (accept), atau membangkitkan (generate) sebuah kalimat
dalam bahasa tertentu. Automata berasal dari bahasa Yunani automatos, yang
berarti sesuatu yang bekerja secara otomatis (mesin). Istilah automaton sebagai
bentuk tunggal dan automata sebagai bentuk jamak. Teori Automata adalah teori
tentang mesin abstrak yang :
·
bekerja sekuensial
·
menerima input
·
mengeluarkan output
Pengertian mesin bukan hanya mesin
elektronis/mekanis saja melainkan segala sesuatu (termasuk perangkat lunak)
yang memenuhi ketiga ciri di atas. Penggunaan automata pada perangkat lunak
terutama pada pembuatan kompiler bahasa pemrograman.
dua
fungsi automata dalam hubungannya dengan bahasa, yaitu :
·
fungsi automata sebagai
pengenal (RECOGNIZER) string-string dari suatu bahasa, dalam hal ini bahasa
sebagai masukan dari automata
·
fungsi automata sebagai
pembangkit (GENERATOR) string-string dari suatu bahasa, dalam hal ini bahasa
sebagai keluaran dari automata
Untuk mengenali string-string dari suatu bahasa,
akan dimodelkan sebuah automaton yang memiliki komponen sebagai berikut :
1. Pita
masukan, yang menyimpan string masukan yang akan dikenali;
2. Kepala
pita (tape head), untuk membaca/menulis ke pita masukan;
3. Finite
State Controller (FSC), yang berisi status-status dan aturan-aturan yang
mengatur langkah yang dilakukan oleh automaton berdasarkan status setiap saat
dan simbol masukan yang sedang dibaca oleh kepala pita;
4. Pengingat
(memory), untuk tempat penyimpanan dan pemrosesan sementara.
5. Automaton
pengenal, setelah membaca string masukan dan melakukan langkahlangkah
pemrosesan yang diperlukan, akan mengeluarkan keputusan apakah string tersebut
dikenali atau tidak.
Konfigurasi
adalah suatu mekanisme untuk menggambarkan keadaan suatu mesin pengenal, yang
terdiri atas :
·
Status FSC
·
Isi pita masukan dan
posisi kepala pita
·
Isi pengingat
Mesin pengenal bersifat deterministik bila dalam
setiap konfigurasi, hanya ada satu kemungkinan yang dapat dilakukan mesin, jika
tidak mesin pengenal bersifat non deterministik. Bahasa dalam bentuk tulisan
terdiri atas simbol-simbol satuan yang jika dikombinasikan akan mempunyai arti
yang berbeda-beda.
Simbol-simbol yang bisa dipergunakan dalam sebuah
bahasa terbatas jumlahnya, yang membentuk sebuah himpunan dan disebut sebagai
abjad (alphabet). Kadangkala digunakan istilah karakter yang maknanya sama
dengan simbol. Deretan karakter membentuk string. Bahasa (language)
didefinisikan sebagai himpunan semua string yang dapat dibentuk dari suatu
abjad. Kaidah/aturan pembentukan kata/kalimat disebut tata bahasa (grammar).
Sebagai keluaran dari automata, Bahasa memungkinkan
penyampaian gagasan dan pemikiran, tanpa itu komunikasi akan sulit terjadi.
Dalam lingkungan pemprograman komputer, bahasa pemprograman bertindak sebagai
sarana komunikasi antara manusia dan permasalahannya dengan komputer yang
dipakai untuk membantu memperoleh pemecahan.
Suatu solusi untuk suatu masalah akan menjadi lebih
mudah bila bahasa pemprograman lebih dekat dengan permasalahan tersebut. Oleh
karena itu, bahasa harus memiliki konstruksi yang merefleksikan masalah dan
independen dari komputer yang dipergunakan. Komputer digital, disisi lain, hanya
menerima dan memahami bahasa tingkat rendah mereka sendiri, terdiri dari
deretan nol dan satu, yang sulit dipahami oleh manusia.
Selain bahasa juga bisa menggunakan otomata sebagai
media, otomata adalah ilmu yang mempelajari mengenai mesin abstrak, bisa disebut
pula adalah suatu model abstrak dari komputer digital yang dapat menerima input
secara sekuensial dan dapat mengeluarkan output. Setiap otomata memiliki
beberapa fungsi dasar, dapat membaca input berupa string dari alphabet yang
diberikan dari input file.
Otomata merupakan suatu sistem yang terdiri dari
sejumlah berhingga status, dimana setiap status tersebut menyatakan informasi
mengenai input yang lalu, dan dapat pula dianggap sebagai mesin memori. Input
pada mesin otomata dianggap sebagai bahasa yang harus dikenali oleh mesin.
Disajikan dengan suatu input string, suatu acceptor apakah akan menerima
(mengenali) string tersebut atau menolaknya. Otomata yang lebih umum yaitu yang
mampu menghasilkan string output, dikenal dengan Tranducer.
3.
Contoh
Penggunaan Automata
Sebagai
contoh penggunaan otomata adalah:
a. Mesin
Turing.
b. Mesin
Karakter
c. Kompiler
d. Mesin
Jaja (Vending Machine)
Setelah kita mengetahui definisi bahasa dan
automata, pertanyaan selanjutnya adalah apakah hubungan antara teori automata
dan bahasa formal ? Secara garis besar ada dua fungsi automata dalam
hubungannya dengan bahasa, yaitu :
a. Fungsi
automata sebagai pengenal (RECOGNIZER) string-string dari suatu bahasa, dalam
hal ini bahasa sebagai masukan dari automata.
b. Fungsi
automata sebagai pembangkit (GENERATOR) string-string dari suatu bahasa, dalam
hal ini bahasa sebagai keluaran dari automata.
Di dalam praktik teori bahasa dan otomata (tbo)
terdapat beberapa pembelajaran yang diajarkan kepada mahsiswa seperti finite
state automata, deterministic finite automata, nondeterministic finite
automata, grammar, regular expression, mesin turing, dan lain-lain. Di dalam
tbo juga dijelaskan juga teori tentang finite state machine (fsm) yang di
dalamnya juga dijelaskan beberapa fungsi seperti fsm with output dan fsm with
no output, dalam fsm with output dijelaskan dua fungsi yaitu meanly machine dan
moore machine, dan juga dalam fsm with no output dijelaskan juga beberapa
fungsi yaitu finite state automata, deterministic finite automata, non-deterministik
finite sutomata, grammar. Yang sering digunakan dalam pembelajaran di teori dan
di praktik adalah finite state machine with no output seperti finite state
automata, deterministic automata, dan lain-lain, akan tetapi dalam pembelajaran
jarang sekali membahas finite state machine with output.
B.
STRING
1.Pengertian String
String
dalam pemrograman komputer adalah sebuah
deret simbol. Tipe data string adalah tipe data yang digunakan untuk menyimpan
barisan karakter.
Bahasa C++ merupakan turunan dari
bahasa C sehingga representasi string sebagai larik karakter masih berlaku.
Namun bahasa C++ juga menyediakan tipe data string yang terdapat dalam C++
Standard Template Library (STL).
Di PHP String adalah kumpulan dari karakter,
bilangan, spasi, dan yang lainnya yang berada dalam tanda petik.
2.
Pendeklarasian Srting
Contoh deklarasi string :Akan
dideklarasikan array str untuk menampung string sepanjang 6 (enam) karakter,
maka
:
Char
str [ 7 ] = “ string “ ; atau
Char
str [ 7 ] = {‘s’, ‘t’, ‘r’, ’i’, ‘n’, ‘g’, ‘\0’ } ;
Deklarasi
Variabel String :
Karena
string merupakan array dari char, maka pendeklarasiannya sama dengan
mendeklarasikan array dari char, yaitu :
Char
nama_var [ jml_karakter ]
Contoh
:
Char alamat [40] –> deklarasi variabel
alamat dengan tipe data string.
Nilai Variabel alamat terdiri dari
beberapa karakter maksimal 40 karakter (0 s/d 39)
3.
Fungsi-fungsi Manipulasi Pada String
a.
Fungsi
strcat()
:
berfungsi untuk menggabungkan string
Untuk menggunakan fungsi strcat
harus menambahkan file header <string.h>
B.U = strcat (tujuan, sumber)
Contoh
:
#include
<stdio.h>
#include
<conio.h>
#include
<string.h>
#include
<iostream.h>
main()
{
char
nmdepan[20],nmbelakang[20];
clrscr();
cout<<"Masukkan
nama depan = ";gets(nmdepan);
cout<<"Masukkan
nama belakang = ";gets(nmbelakang);
cout<<endl;
cout<<"Nama
Lengkap Saya adalah ="<<strcat(nmdepan , nmbelakang);
getch();
}
b.
Fungsi
strlen()
berfungsi untuk mengtahui panjang suatu string
Untuk
menggunakan fungsi strlen harus menambahkan file header <string.h>
B.U = strlen (variabel)
Contoh:
#include
<stdio.h>
#include
<conio.h>
#include
<string.h>
main()
{
char
nama [80];
int
panjang;
printf("Masukan
nama anda: ");gets(nama);
panjang=strlen(nama);
printf("Panjang
nama anda adalah %i karakter\n",panjang);
getch();
}
c.
Fungsi
strcpy()
berfungsi
untuk menyalin isi suatu string ke string lain
Untuk
menggunakan fungsi strlen harus menambahkan file header <string.h>
B.U = strcpy (var_tujuan string_asal)
Contoh:
#include
<conio.h>
#include
<string.h>
#include
<iostream.h>
main()
{
char
huruf[20];
char
pindah[20];
clrscr();
cout<<"Masukkan
Sembarang Kata = ";gets(huruf);
strcpy(pindah,
huruf);
cout<<"Pemindahannya
= "<<pindah;
getch();
}
d.
Fungsi
strchr()
:
berfungsi untuk mencari karakter dari suatu string, jika ditemukan maka akan
mengembalikan (menampilkan )string mulai dari karakter yang di cari, jika tidak
maka fungsi mengembalika ke nilai 0
Untuk
menggunakan fungsi strlen harus menambahkan file header <string.h>
B.U = char*strchr(const char* S, int ch)
Contoh:
#include
<iostream.h>
#include
<conio.h>
#include
<string.h>
main()
{
char*s
="saya suka belajar C++ : (T,T) ";
char*cari;
cari=strchr(s,'u');
cout<<cari<<endl;
getch();
}
e.
Fungsi
strcmp()
:
fungsi ini di gunakan untuk membandingkan string pertama dan string kedua.
hasil dari fungsi ini bertipe data integer (int).
0
(nol) =
jika a1 sama dengan a2
Kurang
dari 0 (negative) = jika a1 lebih keci
dari a2
Lebih
dari 0 (positif) = jika a1 lebih
besar dari a2
Untuk
menggunakan fungsi strcmp harus menambahkan file header <string.h>
B.U = var_int=strcmp(str1,str2)
Contoh:
#include
<iostream.h>
#include
<string.h>
#include
<conio.h>
main()
{
char
a1[] ="ICHSAN";
char
a2[] ="ichsan";
clrscr();
cout<<"hasil
perbandingan "<<a1<<" dan
"<<a1<<"=";
cout<<strcmp(a1,a1)<<endl;
cout<<"hasil
perbandingan "<<a2<<" dan
"<<a1<<"=";
cout<<strcmp(a2,a1)<<endl;
cout<<"hasil
perbandingan "<<a1<<" dan
"<<a2<<"=";
cout<<strcmp(a1,a2)<<endl;
getch();
C.
GRAMMAR
1.
Pengertian
Grammar
Suatu kumpulan aturan (production) yang menentukan
urut-urutan karakter. Suatu formal grammar adalah grammar biasa yang ditentukan
dengan menggunakan notasi yang ketat.
2.
Jenis
Grammar
Bahasa Pemrograman ditentukan 2 jenis Grammar :
a. Primary
Grammar
Disebut juga phrase-structure grammar,
menspesifikasikan bagian utama pada kompilator dan interpreter, yang disebut
parser. Grammar ini menspesifikasikan bagaimana kata-kata dalam bahasa
pemrograman dapat tergabung dan membentuk
program yang valid secara sintaks. Parsing adalah istilah pada bahasa
yang menggambarkan proses analisis sebuah kalimat bahasa menurut grammarnya.
b. Secondary Grammar
Umumnya digunakan untuk menspesifikasikan
bentuk yang benar, spelling dari
kata-kata pada bahasa komputer à disebut
dengan grammar leksikal. Bagian dari kompilator yang menganalisis kata-kata
secara individu pada input program disebut scanner.
Ada
dua kelas grammar yang berguna untuk teknologi compiler, yaitu:
a) EBNF
Grammar
•EExtended
Backus-Naus Form
•Metalanguage:
Bahasa yang digunakan untuk mendeskripsikan bahasa lain.
•Menggunakan
notasi matematis, ::=, <, >, |, *, +, {, }, [, ] disebut Metasymbol.
•Suatu
bahasa yang dideskripsikan dalam EBNF merupakan suatu kumpulan aturan.
b) Regular
Grammar
•
Regular Grammar disebut juga Regular
Language.
•Digunakan pada Teori Bahasa Otomata (Mesin
abstrack yang menggunakan model matematika, tetapi menggunakan matematika yang
benar-benar berbeda dengan matematika klasik dan kalkulus)
•
Bahasa pemrograman yang menggunakan
aturan sintaktik bahasa regular ini antara lain: Javascript & Perl.
Dalam hierarki-bahasa Chomsky, grammar regular adalah grammar
paling restriktif yang dapat membangkitkan sebuah kalimat.
Dalam hierarki tersebut, grammar regular mempunyai
kemampuan pembangkitan kalimat yang sangat
minimal karena:
1. Sisi kiri hanya boleh berisi sebuah
nonterminal,
2. Sisi kanan dalam setiap aturan produksinya
hanya boleh berisi satu nonterminal, dan posisinya hanya boleh berada di
akhiratausisi kanan rangkaian.
Deskripsi yang lebih sederhana, parser untuk grammar ini tidak dapat mengetahui konteks
pemunculan nonterminal yang tengah
didefinisikan, dan hanya dapat melihat
symbol terminal yang ada tepat didepannya.
Terminal
Symbols, Alphabet dan Strings
Alphabet
: representasi letter yang ditulis dalam huruf kecil (a,b,c,…z)
Terminal
Simbol (T) : individual karakter, termasuk di dalamnya adalah alphabet
{a,b,….z, 0,1,…9}
Strings
: urutan simbol terbatas (sequence finite symbol)
contoh : aba, ab12z, axy
operasi yang dapat dilakukan pada strings :
substrings, concatenation.
Non
Terminal (NT) : kumpulan string alphabeth yang ada pada formal language.
Non Terminal direpresentasikan dalam
huruf besar (A,B,….) dan diapit dengan
tanda <..> untuk membedakannya dengan
string.
Konsep
T dan NT direpresentasikan dalam Produksi.
Bentuk Umum Produksi NT ::= string T atau NT
Derivasi
& Reduksi
•Derivasi
merupakan uraian dari suatu Produksi.
•Reduksi
proses perubahan string ke dalam NT sehingga menjadi suatu grammar production.
3.
Klasifikasi Grammar
Chomsky (1963) mengklasifikasikan Grammar menjadi 4
kategori :
a.
Grammar
Type-0
•
Disebut Phrase Structure Grammar atau grammar tidak terbatas
•
Bentuknya : a ::= ß
Dimana,
a dan ß dapat berupa T atau NT, yang dapat saling bersubstitusi, karenanya
tidak relevan untuk bahasa pemrograman.
b.
Grammar
Type-1
•Disebut
Context Sensitive Grammar (CSG), produksi dari grammar ini adalah
derivasi/reduksi dari particular string
yang hanya terdapat pada particular context
•Bentuknya
:
a Aß ::= apß
•Dimana,
p menggantikan A untuk menutupi string a dan ß .
•Grammar
ini-pun tidak relevan untuk bahasa pemrograman.
c.
Grammar
Type-2
•Disebut
Context Free Grammar (CFG), grammar ini tidak membutuhkan context pengenal atau derivasi
•Bentuknya
: A ::= p
•Grammar
ini digunakan pada ALGOL-60 dan PASCAL
d.
Grammar
Type-3
•Disebut
Linier atau RegularGrammar, dimana dapat berupa single terminal simbol dan
terminal simbol atau kebalikannya
•Bentuknya
: A ::= t B | t atau A ::= B t | t
•Bentuk
ini banyak dijumpai pada bahasa pemrograman.
e.
CFG
(Context Free Grammar)
•CFG
ditemukan untuk membantu menspesifikasikan bahasa manusia dan ternyata sangat
cocok untuk mendefinisikan bahasa komputer, menyederhanakan penerjemahan bahasa
komputer dan aplikasi-a
•CFG
digunakan untuk menspesifikasikan struktur sintaks bahasa pemrograman serta
beragam basis data.
•CFG
adalah sekumpulan berhingga variabel yang juga disebut nonterminal atau
kategori sintaks, dimana masing-masing mempresentasikan bahasa. Bahasa-bahasa
yang direpresentasikan dengan variabel-variabel itu yang dideskripsikan secara
rekursif dalam bentukan lain dan symbol-simbol primitif disebut terminal.
Aturan-aturan yang berhubungan dengan variabel-variabel itu disebut produksi.
D.
MESIN
TURING
1.
Pengertian
Mesin Turing adalah model yang sangat sederhana dari
komputer. Secara esensial, mesin Turing
adalah sebuah finite automaton yang miliki sebuah tape tunggal dengan panjang
tak terhingga yang dapat membaca dan menulis data. Mesin Turing menggunakan notasi seperti ID-ID
pada PDA untuk menyatakan konfigurasi dari komputasinya. Stack pada PDA
memiliki keterbatasan akses. Elemen yang
dapat diakses hanya elemen yang ada pada top stack. Pada Mesin Turing, memori
akan berupa suatu tape yang pada dasarnya merupakan array dari sel-sel
penyimpanan.
Visualisasi
dari sebuah mesin Turing diberikan oleh gambar berikut:
Mesin terdiri dari sebuah finite control, yang dapat
berada dalam sebuah himpunan berhingga dari state. Terdapat sebuah tape yang dibagi ke dalam
kotak-kotak atau sel-sel. Setiap sel
dapat menampung sebuah dari sejumlah berhingga dari simbol. Pada awalnya, input yang merupakan string
dari simbol dengan panjang berhingga dipilih dari input alphabet, ditempatkan
pada tape. Sel-sel tape yang lain, perluasan secara infinite ke kiri dan ke
kanan, pada awalnya menampung simbol khusus yang dinamakan blank. Blank bukan
sebuah input symbol, dan mungkin terdapat simbol tape yang lain disamping input
symbol dan blank. Terdapat sebuah tape
head yang selalu ditempatkan pada salah satu dari sel-sel tape. Mesin turing dikatakan men-scan sel tersebut.
Pada awalnya, tape head berada pada sel paling kiri yang menampung input.
Sebuah pergerakan mesin Turing adalah sebuah fungsi dari state dari finite
control dan tape symbol yang di-scan.
Dalam
satu pergerakan, mesin Turing akan :
·
Merubah state. Next state dapat sama dengan current state.
·
Menulis sebuah tape
symbol dalam sel yang di-scan. Tape symbol ini mengganti symbol apapun yang ada
dalam sel tersebut. Secara opsional,
simbol yang dituliskan dapat sama dengan simbol yang sekarang ada dalam tape.
·
Memindahkan tape head
ke kiri atau ke kanan.
·
Notasi formal Mesin
Turing
4.
Komponen-komponen
Mesin Turing
Mesin
Turing dijelaskan oleh 7-tuple:
·
M = (Q, S, G, d, q0, B,
F)
Komponen-komponennya
adalah:
·
Q: Himpunan berhingga dari state dari finite
control.
·
S: himpunan berhingga
dari simbol-simbol input.
·
G: Himpunan dari tape
symbol. S merupakan subset dari G.
·
d: Fungsi transisi. Argumen d(q, X) adalah sebuah state q dan
sebuah tape symbol X. Nilai dari d(q,
X), jika nilai tersebut didefinisikan, adalah triple (p, Y, D), dimana:
·
p adalah next state
dalam Q
·
Y adalah simbol, dalam
G, ditulis dalam sel yang sedang di-scan, menggantikan simbol apapun yang ada
dalam sel tersebut.
·
D adalah arah, berupa L
atau R, berturut-turut menyatakan left
atau right, dan menyatakan arah dimana head bergerak.
·
q0: start state, sebuah
anggota dari Q, dimana pada saat awal finite control ditemukan.
·
B: simbol blank. Simbol ini ada dalam G tapi tidak dalam S,
yaitu B bukan sebuah simbol input.
·
F: himpunan dari final
state, subset dari Q.
5.
Deskripsi
Instantaneous (ID) untuk Mesin Turing
ID digunakan untuk mengetahui apa yang mesin Turing
kerjakan. ID direpresentasikan oleh
string X1X2X3… Xi-1qXiXi+1 … Xn, dimana:
– q adalah state dari TM
– Tape head men-scan simbol ke-i dari
kiri.
– X1X2 …Xn adalah bagian dari tape di
antara nonblank pada sel paling kiri dan paling kanan.
Pergerakan
TM M = (Q, S, G, d, q0, B, F) dinyatakan oleh notasi ├ atau ├. ├*M atau ├*
digunakan untuk menunjukkan nol, satu atau lebih pergerakan dari TM.
Anggap
d(q, Xi) = (p, Y, L), yaitu pergerakan selanjutnya adalah ke kiri. Maka
X1X2…
Xi-1qXiXi+1 … Xn
├
X1X2… Xi-2pXi-1 YXi+1 … Xn
Pergerakan
ini menyatakan perubahan ke state p. Tape head
sekarang diposisikan di sel i-1.
Jika
i = n dan Y = B maka simbol B yang ditulis pada Xn berhubungan dengan urutan
tak hingga dari blank–blank yang mengikuti dan tidak muncul dalam ID
selanjutnya. Dengan demikian
X1X2
…Xn-1 q Xn├ X1X2… Xn-2p Xn-1
Terdapat
dua pengecualian:
–
Jika i=1, maka M bergerak ke blank ke bagian kiri dari X1. Dalam kasus ini,
qX1X2
…Xn├ pBYX2… Xn
– Jika i = n dan Y = B maka simbol B
yang ditulis pada Xn berhubungan dengan urutan tak hingga dari blank–blank yang
mengikuti dan tidak muncul dalam ID selanjutnya. Dengan demikian
X1X2
…Xn-1 q Xn├ X1X2… Xn-2p Xn-1
Anggap
d(q, Xi) = (p, Y, R), yaitu pergerakan selanjutnya adalah ke kanan. Maka
X1X2…
Xi-1qXiXi+1 … Xn ├ X1X2… Xi-1 YpXi+1 … Xn
Tape
head telah bergerak ke sel i+1. Terdapat
dua pengecualian:
– Jika i = n, maka sel ke-i+1
menampung sebuah blank, dan sel tersebut bukan bagian dari ID sebelumnya. Dengan demikian
X1X2
… Xn-1 qXn├ X1 X2… Xn-1YpB
– Jika i = 1 dan Y = B maka simbol
B yang ditulis pada X1 berhubungan dengan urutan tak hingga dari blank–blank
dan tidak muncul dalam ID selanjutnya.
Dengan demikian
qX1X2
…Xn├ pX2… Xn
6.
Diagram
Transisi untuk Mesin Turing
Diagram transisi terdiri dari sebuah himpunan dari
node–node yang menyatakan state–state dari Mesin Turing .sebuah arc dari state
q ke state p diberi label oleh satu atau lebih item dengan bentuk X/Y D, dimana
X dan Y adalah tape symbol, dan D adalah arah, kiri (L) atau kanan
(R). Bahwa bila d(q, X) = (p, Y, D)
diperoleh label X/Y D pada arc dari q ke p. Dalam diagram arah D dinyatakan
dengan tanda ¬ untuk “left” dan ® untuk “right”. Start state
ditandai dengan kata “start” dan sebuah panah yang masuk ke dalam state
tersebut. Final state ditandai dengan putaran ganda.
Contoh:
Mesin Turing berikut menghitungan fungsi , yang dinamakan monus atau proper
substraction. Fungsi ini didefinisikan
oleh m
n = max(m – n, 0). Bahwa, m n = m – n jika m ³ n dan 0 jika m <
n. Mesin Turing yang melakukan operasi
ini adalah
M
= ({q0, q1, … , q6}, {0, 1}, {0, 1, B}, d, q0, B)
Aturan
untuk fungsi transisi d:
Diagram
transisi dari mesin Turing M:
BAB III
PENUTUP
A.
Kesimpulan
Teori bahasa
membicarakan bahasa formal (formal language), terutama untuk kepentingan
perancangan kompilator (compiler) dan pemroses naskah (text processor). Automata
adalah mesin abstrak yang dapat mengenali (recognize), menerima (accept), atau
membangkitkan (generate) sebuah kalimat dalam bahasa tertentu. Automata berasal
dari bahasa Yunani automatos, yang berarti sesuatu yang bekerja secara otomatis
(mesin). String dalam pemrograman komputer
adalah sebuah deret simbol. Tipe data string adalah tipe data yang
digunakan untuk menyimpan barisan karakter.
Grammar adalah suatu kumpulan
aturan (production) yang menentukan urut-urutan karakter. Suatu formal grammar
adalah grammar biasa yang ditentukan dengan menggunakan notasi yang ketat. Mesin
Turing adalah model yang sangat sederhana dari komputer. Secara esensial, mesin Turing adalah sebuah
finite automata yang miliki sebuah tape tunggal dengan panjang tak terhingga yang
dapat membaca dan menulis data.
B.
Saran
Setelah
kita mengetahui tentang apa itu teori bahasa dan automata, maka tidak ada
salahnya kalau kita berbagi apa yang kita ketahui kepada seseorang yang ingin
belajar dan mempraktekkannya seperti apa yang di terangkan oleh teori-teori.
DAFTAR PUSTAKA
John
E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. 2001. Introduction to Automata
Theory, Languange, and Computation.
Tidak ada komentar:
Posting Komentar