Rabu, 25 Januari 2012
TEORI BAHASA DAN AUTOMATA
IRVA IYATUL MUALIMAH
0955201025
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.
Automata
Automata adalah mesin abstrak yang dapat mengenali $28recognize), menerima
(accept), atau membangkitkan (generate) sebuah kalimat dalam bahasa tertentu.
Beberapa Pengertian Dasar
• Simbol adalah sebuah entitas abstrak (seperti halnya pengertian titik dalam
geometri). Sebuah huruf atau sebuah angka adalah contoh simbol.
• String adalah deretan terbatas (finite) simbol-simbol. Sebagai contoh, jika a, b,
dan c adalah tiga buah simbol maka abcb adalah sebuah string yang dibangun dari
ketiga simbol tersebut.
• Jika w adalah sebuah string maka panjang string dinyatakan sebagai w dan
didefinisikan sebagai cacahan (banyaknya) simbol yang menyusun string tersebut.
Sebagai contoh, jika w = abcb maka w= 4.
• String hampa adalah sebuah string dengan nol buah simbol. String hampa
dinyatakan dengan simbol ε (atau ^) sehingga ε= 0. String hampa dapat
dipandang sebagai simbol hampa karena keduanya tersusun dari nol buah simbol.
• Alfabet adalah hinpunan hingga (finite set) simbol-simbol
Operasi Dasar String
Diberikan dua string : x = abc, dan y = 123
• Prefik string w adalah string yang dihasilkan dari string w dengan menghilangkan
nol atau lebih simbol-simbol paling belakang dari string w tersebut.
Contoh : abc, ab, a, dan ε adalah semua Prefix(x)
• ProperPrefix string w adalah string yang dihasilkan dari string w dengan
menghilangkan satu atau lebih simbol-simbol paling belakang dari string w
tersebut.
Contoh : ab, a, dan ε adalah semua ProperPrefix(x)
• Postfix (atau Sufix) string w adalah string yang dihasilkan dari string w dengan
menghilangkan nol atau lebih simbol-simbol paling depan dari string w tersebut.
Contoh : abc, bc, c, dan ε adalah semua Postfix(x)
• ProperPostfix (atau PoperSufix) string w adalah string yang dihasilkan dari string
w dengan menghilangkan satu atau lebih simbol-simbol paling depan dari string w
tersebut.
Contoh : bc, c, dan ε adalah semua ProperPostfix(x)
• Head string w adalah simbol paling depan dari string w.
Contoh : a adalah Head(x)
Asep Juarna, Catatan Teori Bahasa dan Automata, hal 2
• Tail string w adalah string yang dihasilkan dari string w dengan menghilangkan
simbol paling depan dari string w tersebut.
Contoh : bc adalah Tail(x)
• Substring string w adalah string yang dihasilkan dari string w dengan
menghilangkan nol atau lebih simbol-simbol paling depan dan/atau simbol-simbol
paling belakang dari string w tersebut.
Contoh : abc, ab, bc, a, b, c, dan ε adalah semua Substring(x)
• ProperSubstring string w adalah string yang dihasilkan dari string w dengan
menghilangkan satu atau lebih simbol-simbol paling depan dan/atau simbol-
simbol paling belakang dari string w tersebut.
Contoh : ab, bc, a, b, c, dan ε adalah semua Substring(x)
• Subsequence string w adalah string yang dihasilkan dari string w dengan
menghilangkan nol atau lebih simbol-simbol dari string w tersebut.
Contoh : abc, ab, bc, ac, a, b, c, dan ε adalah semua Subsequence(x)
• ProperSubsequence string w adalah string yang dihasilkan dari string w dengan
menghilangkan satu atau lebih simbol-simbol dari string w tersebut.
Contoh : ab, bc, ac, a, b, c, dan ε adalah semua Subsequence(x)
• Concatenation adalah penyambungan dua buah string. Operator concatenation
adalah concate atau tanpa lambang apapun.
Contoh : concate(xy) = xy = abc123
• Alternation adalah pilihan satu di antara dua buah string. Operator alternation
adalah alternate atau .
Contoh : alternate(xy) = xy = abc atau 123
0955201025
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.
Automata
Automata adalah mesin abstrak yang dapat mengenali $28recognize), menerima
(accept), atau membangkitkan (generate) sebuah kalimat dalam bahasa tertentu.
Beberapa Pengertian Dasar
• Simbol adalah sebuah entitas abstrak (seperti halnya pengertian titik dalam
geometri). Sebuah huruf atau sebuah angka adalah contoh simbol.
• String adalah deretan terbatas (finite) simbol-simbol. Sebagai contoh, jika a, b,
dan c adalah tiga buah simbol maka abcb adalah sebuah string yang dibangun dari
ketiga simbol tersebut.
• Jika w adalah sebuah string maka panjang string dinyatakan sebagai w dan
didefinisikan sebagai cacahan (banyaknya) simbol yang menyusun string tersebut.
Sebagai contoh, jika w = abcb maka w= 4.
• String hampa adalah sebuah string dengan nol buah simbol. String hampa
dinyatakan dengan simbol ε (atau ^) sehingga ε= 0. String hampa dapat
dipandang sebagai simbol hampa karena keduanya tersusun dari nol buah simbol.
• Alfabet adalah hinpunan hingga (finite set) simbol-simbol
Operasi Dasar String
Diberikan dua string : x = abc, dan y = 123
• Prefik string w adalah string yang dihasilkan dari string w dengan menghilangkan
nol atau lebih simbol-simbol paling belakang dari string w tersebut.
Contoh : abc, ab, a, dan ε adalah semua Prefix(x)
• ProperPrefix string w adalah string yang dihasilkan dari string w dengan
menghilangkan satu atau lebih simbol-simbol paling belakang dari string w
tersebut.
Contoh : ab, a, dan ε adalah semua ProperPrefix(x)
• Postfix (atau Sufix) string w adalah string yang dihasilkan dari string w dengan
menghilangkan nol atau lebih simbol-simbol paling depan dari string w tersebut.
Contoh : abc, bc, c, dan ε adalah semua Postfix(x)
• ProperPostfix (atau PoperSufix) string w adalah string yang dihasilkan dari string
w dengan menghilangkan satu atau lebih simbol-simbol paling depan dari string w
tersebut.
Contoh : bc, c, dan ε adalah semua ProperPostfix(x)
• Head string w adalah simbol paling depan dari string w.
Contoh : a adalah Head(x)
Asep Juarna, Catatan Teori Bahasa dan Automata, hal 2
• Tail string w adalah string yang dihasilkan dari string w dengan menghilangkan
simbol paling depan dari string w tersebut.
Contoh : bc adalah Tail(x)
• Substring string w adalah string yang dihasilkan dari string w dengan
menghilangkan nol atau lebih simbol-simbol paling depan dan/atau simbol-simbol
paling belakang dari string w tersebut.
Contoh : abc, ab, bc, a, b, c, dan ε adalah semua Substring(x)
• ProperSubstring string w adalah string yang dihasilkan dari string w dengan
menghilangkan satu atau lebih simbol-simbol paling depan dan/atau simbol-
simbol paling belakang dari string w tersebut.
Contoh : ab, bc, a, b, c, dan ε adalah semua Substring(x)
• Subsequence string w adalah string yang dihasilkan dari string w dengan
menghilangkan nol atau lebih simbol-simbol dari string w tersebut.
Contoh : abc, ab, bc, ac, a, b, c, dan ε adalah semua Subsequence(x)
• ProperSubsequence string w adalah string yang dihasilkan dari string w dengan
menghilangkan satu atau lebih simbol-simbol dari string w tersebut.
Contoh : ab, bc, ac, a, b, c, dan ε adalah semua Subsequence(x)
• Concatenation adalah penyambungan dua buah string. Operator concatenation
adalah concate atau tanpa lambang apapun.
Contoh : concate(xy) = xy = abc123
• Alternation adalah pilihan satu di antara dua buah string. Operator alternation
adalah alternate atau .
Contoh : alternate(xy) = xy = abc atau 123
TEORI BAHASA DAN OTOMATA
Otomata (Automata)
• Otomata adalah mesin abstrak yang dapat mengenali (recognize), menerima (accept), atau membangkitkan (generate) sebuah kalimat dalam bahasa tertentu.
Beberapa Pengertian Dasar :
• Simbol adalah sebuah entitas abstrak (seperti halnya pengertian titik dalam geometri). Sebuah huruf atau sebuah angka adalah contoh simbol.
• String adalah deretan terbatas (finite) simbol-simbol. Sebagai contoh, jika a, b, dan c adalah tiga buah simbol maka abcb adalah sebuah string yang dibangun dari ketiga simbol tersebut.
• Jika w adalah sebuah string maka panjang string dinyatakan sebagai w dan didefinisikan sebagai cacahan (banyaknya) simbol yang menyusun string tersebut. Sebagai contoh, jika w = abcb maka w= 4.
• String hampa adalah sebuah string dengan nol buah simbol. String hampa dinyatakan dengan simbol (atau ^) sehingga = 0. String hampa dapat dipandang sebagai simbol hampa karena keduanya tersusun dari nol buah simbol.
• Alfabet adalah hinpunan hingga (finite set) simbol-simbol
Operasi Dasar String
Diberikan dua string : x = abc, dan y = 123
• Prefik string w adalah string yang dihasilkan dari string w dengan menghilangkan nol atau lebih simbol-simbol paling belakang dari string w tersebut.
Contoh : abc, ab, a, dan adalah semua Prefix(x)
• ProperPrefix string w adalah string yang dihasilkan dari string w dengan menghilangkan satu atau lebih simbol-simbol paling belakang dari string w tersebut.
Contoh : ab, a, dan adalah semua ProperPrefix(x)
• Postfix (atau Sufix) string w adalah string yang dihasilkan dari string w dengan menghilangkan nol atau lebih simbol-simbol paling depan dari string w tersebut.
Contoh : abc, bc, c, dan adalah semua Postfix(x)
• ProperPostfix (atau PoperSufix) string w adalah string yang dihasilkan dari string w dengan menghilangkan satu atau lebih simbol-simbol paling depan dari string w tersebut.
Contoh : bc, c, dan adalah semua ProperPostfix(x)
• Head string w adalah simbol paling depan dari string w.
Contoh : a adalah Head(x)
• Tail string w adalah string yang dihasilkan dari string w dengan menghilangkan simbol paling depan dari string w tersebut.
Contoh : bc adalah Tail(x)
• Substring string w adalah string yang dihasilkan dari string w dengan menghilangkan nol atau lebih simbol-simbol paling depan dan/atau simbol-simbol paling belakang dari string w tersebut.
Contoh : abc, ab, bc, a, b, c, dan adalah semua Substring(x)
• ProperSubstring string w adalah string yang dihasilkan dari string w dengan menghilangkan satu atau lebih simbol-simbol paling depan dan/atau simbol-simbol paling belakang dari string w tersebut.
Contoh : ab, bc, a, b, c, dan adalah semua Substring(x)
• Subsequence string w adalah string yang dihasilkan dari string w dengan menghilangkan nol atau lebih simbol-simbol dari string w tersebut.
Contoh : abc, ab, bc, ac, a, b, c, dan adalah semua Subsequence(x)
• ProperSubsequence string w adalah string yang dihasilkan dari string w dengan menghilangkan satu atau lebih simbol-simbol dari string w tersebut.
Contoh : ab, bc, ac, a, b, c, dan adalah semua Subsequence(x)
• Concatenation adalah penyambungan dua buah string. Operator concatenation adalah concate atau tanpa lambang apapun.
Contoh : concate(xy) = xy = abc123
GRAMMAR DAN BAHASA
Konsep Dasar
• Anggota alfabet dinamakan simbol terminal.
• Kalimat adalah deretan hingga simbol-simbol terminal.
• Bahasa adalah himpunan kalimat-kalimat. Anggota bahasa bisa tak hingga kalimat.
• Simbol-simbol berikut adalah simbol terminal :
huruf kecil, misalnya : a, b, c, 0, 1, ..
simbol operator, misalnya : +, , dan
simbol tanda baca, misalnya : (, ), dan ;
string yang tercetak tebal, misalnya : if, then, dan else.
• Simbol-simbol berikut adalah simbol non terminal /Variabel :
huruf besar, misalnya : A, B, C
huruf S sebagai simbol awal
string yang tercetak miring, misalnya : expr
• Huruf yunani melambangkan string yang tersusun atas simbol-simbol terminal atau simbol-simbol non terminal atau campuran keduanya, misalnya : , , dan .
• Sebuah produksi dilambangkan sebagai , artinya : dalam sebuah derivasi dapat dilakukan penggantian simbol dengan simbol .
• Derivasi adalah proses pembentukan sebuah kalimat atau sentensial. Sebuah derivasi dilambangkan sebagai : .
• Sentensial adalah string yang tersusun atas simbol-simbol terminal atau simbol-simbol non terminal atau campuran keduanya.
• Kalimat adalah string yang tersusun atas simbol-simbol terminal. Kalimat adalah merupakan sentensial, sebaliknya belum tentu..
A. Mesin Pengenal Bahasa
Untuk setiap kelas bahasa Chomsky, terdapat sebuah mesin pengenal bahasa. Masing-masing mesin tersebut adalah :
Kelas Bahasa Mesin Pengenal Bahasa
Unrestricted Grammar (UG) Mesin Turing (Turing Machine), TM
Context Sensitive Grammar (CSG) Linear Bounded Automata, LBA
Context Free Gammar (CFG) Pushdown Automata, PDA
Regular Grammar, RG Finite State Automata, FSA
FINITE STATE AUTOMATA (FSA)
• FSA didefinisikan sebagai pasangan 5 tupel : (Q, ∑, δ, S, F).
Q : himpunan hingga state
∑ : himpunan hingga simbol input (alfabet)
δ : fungsi transisi, menggambarkan transisi state FSA akibat pembacaan simbol input.
Fungsi transisi ini biasanya diberikan dalam bentuk tabel.
S Q : state AWAL
F Q : himpunan state AKHIR
Contoh : FSA untuk mengecek parity ganjil
Q ={Gnp, Gjl} ∑ = {0,1}
tabel transisi
δ 0 1
Gnp Gnp Gjl
Gjl Gjl Gnp
S = Gnp, F = {Gjl}
NAMA : IMAM ANSORI
NIM : 0955201023
Otomata (Automata)
• Otomata adalah mesin abstrak yang dapat mengenali (recognize), menerima (accept), atau membangkitkan (generate) sebuah kalimat dalam bahasa tertentu.
Beberapa Pengertian Dasar :
• Simbol adalah sebuah entitas abstrak (seperti halnya pengertian titik dalam geometri). Sebuah huruf atau sebuah angka adalah contoh simbol.
• String adalah deretan terbatas (finite) simbol-simbol. Sebagai contoh, jika a, b, dan c adalah tiga buah simbol maka abcb adalah sebuah string yang dibangun dari ketiga simbol tersebut.
• Jika w adalah sebuah string maka panjang string dinyatakan sebagai w dan didefinisikan sebagai cacahan (banyaknya) simbol yang menyusun string tersebut. Sebagai contoh, jika w = abcb maka w= 4.
• String hampa adalah sebuah string dengan nol buah simbol. String hampa dinyatakan dengan simbol (atau ^) sehingga = 0. String hampa dapat dipandang sebagai simbol hampa karena keduanya tersusun dari nol buah simbol.
• Alfabet adalah hinpunan hingga (finite set) simbol-simbol
Operasi Dasar String
Diberikan dua string : x = abc, dan y = 123
• Prefik string w adalah string yang dihasilkan dari string w dengan menghilangkan nol atau lebih simbol-simbol paling belakang dari string w tersebut.
Contoh : abc, ab, a, dan adalah semua Prefix(x)
• ProperPrefix string w adalah string yang dihasilkan dari string w dengan menghilangkan satu atau lebih simbol-simbol paling belakang dari string w tersebut.
Contoh : ab, a, dan adalah semua ProperPrefix(x)
• Postfix (atau Sufix) string w adalah string yang dihasilkan dari string w dengan menghilangkan nol atau lebih simbol-simbol paling depan dari string w tersebut.
Contoh : abc, bc, c, dan adalah semua Postfix(x)
• ProperPostfix (atau PoperSufix) string w adalah string yang dihasilkan dari string w dengan menghilangkan satu atau lebih simbol-simbol paling depan dari string w tersebut.
Contoh : bc, c, dan adalah semua ProperPostfix(x)
• Head string w adalah simbol paling depan dari string w.
Contoh : a adalah Head(x)
• Tail string w adalah string yang dihasilkan dari string w dengan menghilangkan simbol paling depan dari string w tersebut.
Contoh : bc adalah Tail(x)
• Substring string w adalah string yang dihasilkan dari string w dengan menghilangkan nol atau lebih simbol-simbol paling depan dan/atau simbol-simbol paling belakang dari string w tersebut.
Contoh : abc, ab, bc, a, b, c, dan adalah semua Substring(x)
• ProperSubstring string w adalah string yang dihasilkan dari string w dengan menghilangkan satu atau lebih simbol-simbol paling depan dan/atau simbol-simbol paling belakang dari string w tersebut.
Contoh : ab, bc, a, b, c, dan adalah semua Substring(x)
• Subsequence string w adalah string yang dihasilkan dari string w dengan menghilangkan nol atau lebih simbol-simbol dari string w tersebut.
Contoh : abc, ab, bc, ac, a, b, c, dan adalah semua Subsequence(x)
• ProperSubsequence string w adalah string yang dihasilkan dari string w dengan menghilangkan satu atau lebih simbol-simbol dari string w tersebut.
Contoh : ab, bc, ac, a, b, c, dan adalah semua Subsequence(x)
• Concatenation adalah penyambungan dua buah string. Operator concatenation adalah concate atau tanpa lambang apapun.
Contoh : concate(xy) = xy = abc123
GRAMMAR DAN BAHASA
Konsep Dasar
• Anggota alfabet dinamakan simbol terminal.
• Kalimat adalah deretan hingga simbol-simbol terminal.
• Bahasa adalah himpunan kalimat-kalimat. Anggota bahasa bisa tak hingga kalimat.
• Simbol-simbol berikut adalah simbol terminal :
huruf kecil, misalnya : a, b, c, 0, 1, ..
simbol operator, misalnya : +, , dan
simbol tanda baca, misalnya : (, ), dan ;
string yang tercetak tebal, misalnya : if, then, dan else.
• Simbol-simbol berikut adalah simbol non terminal /Variabel :
huruf besar, misalnya : A, B, C
huruf S sebagai simbol awal
string yang tercetak miring, misalnya : expr
• Huruf yunani melambangkan string yang tersusun atas simbol-simbol terminal atau simbol-simbol non terminal atau campuran keduanya, misalnya : , , dan .
• Sebuah produksi dilambangkan sebagai , artinya : dalam sebuah derivasi dapat dilakukan penggantian simbol dengan simbol .
• Derivasi adalah proses pembentukan sebuah kalimat atau sentensial. Sebuah derivasi dilambangkan sebagai : .
• Sentensial adalah string yang tersusun atas simbol-simbol terminal atau simbol-simbol non terminal atau campuran keduanya.
• Kalimat adalah string yang tersusun atas simbol-simbol terminal. Kalimat adalah merupakan sentensial, sebaliknya belum tentu..
A. Mesin Pengenal Bahasa
Untuk setiap kelas bahasa Chomsky, terdapat sebuah mesin pengenal bahasa. Masing-masing mesin tersebut adalah :
Kelas Bahasa Mesin Pengenal Bahasa
Unrestricted Grammar (UG) Mesin Turing (Turing Machine), TM
Context Sensitive Grammar (CSG) Linear Bounded Automata, LBA
Context Free Gammar (CFG) Pushdown Automata, PDA
Regular Grammar, RG Finite State Automata, FSA
FINITE STATE AUTOMATA (FSA)
• FSA didefinisikan sebagai pasangan 5 tupel : (Q, ∑, δ, S, F).
Q : himpunan hingga state
∑ : himpunan hingga simbol input (alfabet)
δ : fungsi transisi, menggambarkan transisi state FSA akibat pembacaan simbol input.
Fungsi transisi ini biasanya diberikan dalam bentuk tabel.
S Q : state AWAL
F Q : himpunan state AKHIR
Contoh : FSA untuk mengecek parity ganjil
Q ={Gnp, Gjl} ∑ = {0,1}
tabel transisi
δ 0 1
Gnp Gnp Gjl
Gjl Gjl Gnp
S = Gnp, F = {Gjl}
NAMA : IMAM ANSORI
NIM : 0955201023
AUTOMATA HINGGA DETERMINISTIK (AHD)
.
AUTOMATA HINGGA DETERMINISTIK (AHD)
AHD dapat dilengkapi dengan fungsi Next-State berikut:
a) M(q, ^) = q untuk semua q anggota K
b) M(M(q, t), T), untuk semua t anggota VT dan T anggota VT
Dari definisi pertama, terlihat bahwa sebuah AHD tidak bisa mengubah stata tanpa membaca sebuah karakter masukan. Definisi kedua adalah sebuah definisi yang bersifat rekursif, yang menunjukkan di stata mana AHD berada pada saat di mulai di stata q dengan mendapat input berupa string w = tT.
Sebuah string w adalah diterima oleh sebuah F = (K, VT, M, S, Z) jika M(S, W) = p, sedemikian hingga w adalah anggota VT dan p anggota Z.
Atau dengan kata lain, string w diterima oleh AHD jika setelah membaca habis semua karakter dari untai, AHD berada pada sebuah Stata Akhir. Himpunan semua untai w anggota VT yang diterima oleh AHD F dinotasikan sebagai L(F).
AHD pada contoh ini merupakan sebuah AHD yang menerima untai yang terdiri dari simbol 0 dan 1. AHD tersebut dapat dinyatakan sebagai berikut :
F = ( {S, A, B, C}, {0, 1}, M, S, {S} ) dimana fungsi next state M adalah :
M(S, 0) = B M(S, 1) = A
M(A, 0) = C M(A, 1) = S
M(B, 0) = S M(B, 1) = C
M(C, 0) = A M(C, 1) = B
Fungsi stata berikut dari AHD kadang-kadang lebih mudah disajikan dalam bentuk tabel. Untuk contoh di atas tabel yang terbentuk adalah :
| STATA | INPUT |
| 0 1 | |
SA B C | B A C S S C A B |
Contoh dari string yang diterima AHD di atas adalah 110101 dan contoh string yang tidak dapat diterima adalah 11101. Bagan operasi AHD pada kedua untai di atas adalah sebagai berikut :
Penelusuran string 110101 : Penelusuran string 11101 :
M(S, 110101) = M(A, 10101) M(S, 11101) = M(A, 1101)
= M(S, 0101) = M(S, 101)
= M(B, 101) = M(A, 01)
= M(C, 01) = M(C, 1)
= M(A, 1) = M(B, ^)
= M(S, ^) = B (ditolak)
= S (diterima)
TEORI BAHASA DAN AUTOMATA
sedikit penjelasan buat teman-teman semua,, semoga bermanfaat ye,,,
/\_/\
FSA (Finite State Automata) merupakan tool yang sangat berguna dalam perancangan lexical analyzer, yaitu bagian dari kompilator yang mengelompokan karakter-karakter ke dalam sebuah token, yang berupa unit terkecil seperti nama, variabel, dan keyword.
FSA dipakai untuk penganalisa leksikal dan dipakai juga dalam text editor, pemrosesan teks, dan program file-searching
Spesifikasi dari sebuah bahasa pemrograman meliputi, hal-hal :
1. Himpunan simbol-simbol (alpabet) yang bisa dipakai untuk membentuk program yang benar
2. Himpunan program yang benar secara sintaktik
3. Makna dari program tersebut
Teori Bahasa Formal
Karena bahasa adalah sebuah himpunan dari string, maka untuk mendefinisikan suatu bahasa bisa dilakukan dengan menuliskan semua string yang menjadi anggotanya. Bagaimana kita bisa melakukannya jika jumlah string yang menjadi anggota bahasa tersebut banyak sekali atau bahkan tidak berhingga ? Pada Teori Bahasa Formal, hal ini dilakukan dengan mendefinisikan tata bahasanya. Tata Bahasa G = (T,N,S,P), di mana
- T adalah himpunan berhingga simbol-simbol terminal
- N adalah himpunan berhinggasimbol-simbol non terminal
- S adalah simbol awal, S ∈ N
- P adalah himpunan berhingga aturan produksi yang setiap elemennya berbentuk α → β, α, β ∈ (T ∪ N)+, α harus berisi minimal 1 simbol non terminal.
Sentential form adalah semua string yang dapat diturunkan dari simbol awal S dengan menggunakan aturan produksi P. Kalimat (sentence) adalah sentential form yang tidak mengandung simbol non terminal. Bahasa yang dihasilkan dari G dinotasikan dengan L(G), yaitu himpunan kalimat yang dapat diturunkan dari S dengan menggunakan P.
Teori Automata
Berasal dari bahasa Yunani automatos, yang berarti sesuatu yang bekerja secara otomatis (mesin). Dalam tulisan ini akan dipergunakan 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 di tulisan ini, 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. 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 :
- 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.
Dalam tulisan ini, pembahasan akan ditekankan pada fungsi pertama dari automata. Untuk mengenali string-string dari suatu bahasa, akan dimodelkan sebuah automaton yang memiliki komponen sebagai berikut :
- pita masukan, yang menyimpan string masukan yang akan dikenali;
- kepala pita (tape head), untuk membaca/menulis ke pita masukan;
- 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;
- pengingat (memory), untuk tempat penyimpanan dan pemrosesan sementara Automaton pengenal, setelah membaca string masukan dan melakukan langkah langkah 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. Contoh mesin automata :
- Sebuah string input diterima bila mencapai state akhir/ final state yang digambarkan dengan lingkaran ganda.
- Pada gambar diatas, mesin mendapat string input berikut :
– ada : diterima
– adu : diterima
– add : ditolak
- Mesin diatas memiliki 6 state {qo, q1, q2, q3, q4, q5}.
- State awal : q0, State akhir : {q3, q4}.
- Himpunan simbol input : {a,d,u}.
Konsep Bahasa dan Otomata
• Simbol adalah suatu entitas abstrak yang tidak bisa didefinisikan secara formal
• Huruf dan digit adalah contoh dari simbol yang sering di pakai
• String adalah suatu deretan berhingga dari simbol-simbol, contoh : ‘a’, ‘b’, ‘c’ adalah simbol dan ‘abc’ adalah sebuah string.
• String kosong dinyatakan dengan ε di definisikan panjangnya = 0 atau |ε|= 0
• Bahasa adalah himpunan string-string dari simbol-simbol untuk suatu alpabet yang memiliki makna.
• Ada istilah bahasa kosong, yaitu bahasa yang tidak terdiri dari string-string, contoh himpunan kosong Ø
• Otomata adalah suatu bentuk yang memiliki fungsi-fungsi dari komputer digital, menerima input menghasilkan output, bisa memiliki penyimpanan sementara, dan mampu membuat keputusan dalam mentransformasikan input ke output
• Otomata merupakan suatu sistem yang terdiri atas sejumlah berhingga (state), dimana state menyatakan informasi mengenai input yang lalu dan dapat dianggap sebagai memori mesin.
• Input pada mesin otomata dianggap sebagai bahasa yang harus dikenali oleh mesin. Selanjutnya mesin otomata membuat keputusan atau keluaran yang mengindikasikan apakah input itu diterima atau tidak
Langganan:
Postingan (Atom)