TEORI BAHASA AUTOMATA

TEORI BAHASA

Teori bahasa membicarakan bahasa formal (formal language), terutama untuk kepentinga 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’ disebut ‘bahasa’ saja.

AUTOMATA

Automata adalah mesin abstrak yang dapat mngenali (recognize), menerima (accept), atau membangkitkan (generate) sebuah kalimat dalam bahasa tertentu.

Untuk memodelkan hardware dari komputer diperkenalkan otomata. Otomata adalah fungsi-fungsi dari komputer digital. Menerima input, mengh asilkan output, bisa memiliki penyimpanan sementara dan mampu membuat keputusan dalam mentransformasikan input ke output.

Sebuah bahasa formal adalah suatu abstraksi terdiri dari himpunan simbol-simbol dan aturan-aturan yang mana simbol-simbol tersebut bisa dikombinaasikan ke dalam entitas yang disebut kalimat.

Meskipun bahasa formal yang dipelajari disini lebih sederhana daripada bahasa lebih sederhana daripada bahasa pemrograman, meraka mempunyai banyak hal yang penting. Kita bisa mempelajari banyak tentang bahasa pemrograman dari bahasa formal.

Otomata merupakan suatu sistem yang terdiri atas sejumlah berhingga state, dimana state menyatakan informasi mengenai input yan lalu dandapaty dianggap sebagai memory mesin.

Input pada mesin otomata dianggap sebagai bahasa yang harus dikenali oleh mesin. Selanjutnya, mesin otomata membuat bkeputusan yang mengindikasikan apakah input itu diterima atau tidak.

BEBERAPA PENGERTIAN DASAR

Simbol adalah sebuah entitas abstrak (seperti halnya pengertian titik dalam geometri). Sebuah huruf atau sebuah angka adalah contoh simbol. Pada umumnya kita menggunakan huruf kecil (lower case)atau angka untuk melambngkan simbol, dan huruf kecil diakhir alphabet khususnya w,x,y,z untuk melambangkan untai (String).

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. Dinyatakan dengan simbol Ɛ (atau ˄) sehingga | Ɛ|=0. String hampa dipandang sebagai simbol hampa karena keduanya tersusun dari nol buah simbol.

Alphabet adalah himpunan hingga (finite set) simbol-simbol. Pada umumnya kita menggunakan lower case untuk melambangkan simbol, dan huruf  kecil diakhir alphabet khususnya w, x, y dan z untuk melambangkan untai (String).

OPERASI DASAR STRING

Diberikan dua String : x=abc , dan y=123;

PREFIX 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).

PROPERPREFIK STRING w adalah String yang dihasilkan dari String w dengan menghilangkan satuatau 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 SUFIX) STRING w adalah String yang dihasilkan dari String w dengan menghilangkan satuatau lebih simbol-simbol paling depan dari String w tersebut. Contoh : bc, c dan Ɛ adalah semua PROPERPOSTFIX(x).

SUBSTRING STRING w adalah  String yang dihasilkan dari String w dengan menghilangkan nol  atau lebih simbolpaling depan dan/atau simbol-simbol paling belakang dari String w tersebut. Contoh : abc, ab, bc, a, b, c dan Ɛ adalah semua SUBSTRING (x).

PROPER SUBSTRING STRING w adalah  String yang dihasilkan dari String w dengan menghilangkan satu atau lebih simbol paling depan dan/atau simbol-simbol paling belakang dari String w tersebut. Contoh : ab, bc, a, b, c dan Ɛ adalah semua PROPERSUBSTRING (x).

SUBSEQUENCE STRING w adalah  String yang dihasilkan dari String w dengan menghilangkan nol  atau lebihsimbol-simbol dari String w tersebut. Contoh : abc, ab, bc, ac, a, b, c dan Ɛ adalah semua SUBSEQUENCE (x).

PROPER SUBSEQUENCE STRING w adalah  String yang dihasilkan dari String w dengan menghilangkan satuatau lebih simbol-simbol dari String w tersebut. Contoh : ab, bc, ac, a, b, c dan Ɛ adalah semua SUBSEQUENCE (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 menhilangkan HEAD tersebut. Contoh : bc adalah TAIL(x).

CONCATENATION adalah penyambungan dua buah String. Contoh : concate(xy) = xy = abc123.

ALTERNATION adalah pilihan satu diantara dua buah String. Operatornya adalah |. Contoh : alternate(xy) = x | y = abc atau 123.

KLEENE CLOSURE : x* = Ɛ | x | xx | xxx| … = Ɛ | x | x2 | x3| …

x* : menyatakan himpunan seluruh untai yang meliputi seluruh alphabet, termasuk untai kosong (Ɛ).

POSITIVE CLOSURE : x+ = x | xx | xxx |… = x | x2 | x3 | …

x+ : menyatakan himpunan seluruh untai meliputi seluruh alphabet, tidak termasuk untai kosong (Ɛ).

KONSEP DASAR

Dalam  pembicaraan Grammar, anggota alphabet dinamakan simbol terminal atau token.

Kalimat adalah deretan hinggga simbol-simbol terminal.

Bahasa adalah himpunan kalimat-kalimat. Anggota bahasa bisa hingga bisa tak hingga kalimat.

Simbol berikut adalah simbol terminal :

-huruf kecil awal alphabet, misal a, b, c

- simbol operator, misal +, -, dan x

-simbol tanda baca, misal (,), dan ;

-string  yang tercetak tebal, misal if, then, else

Simbol berikut adalah simbol non terminal :

-huruf besar awal alphabet, misal A, B, C

-huruf S sebagai simbol awal

-string yang tercetak miring, misal expr dan stmt

Huruf besar akhir alphabet melambangkan simbol terminal atau non terminal. Misal X, Y, Z

Huruf kecil akhir alphabet melambangkan String yang tersusun atas simbol-simbol terminal, misal x, y, z

Huruf yunani melambangkan String yang tersusun atas simbol-simbol terminal atau non terminal atau campuran keduanya, misal α, β, γ

Sebuah produksi dilambangkan sebagai  α → β artinya dalam sebuah derivasi dapat dilakukan penggantian simbol α dengan simbol β

Dalam produksi berbentuk α → β.  α disebut ruas kiri sedangkan  β  disebut ruas kanan.

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 terssusun atas simbol-simbol terminal. Jelaslah bahwa kalimat adalah kasus khusus dari sentensial.

Pengertian terminal berasal dari kata terminate (berakhir), maksudnya derivasi berakhir jika sentensial yang dihasilkan adalah sebuah kalimat (tersusun atas simbol terminal).

Pengertian non terminal berasal dari kata not terminate (tidak/belum berhenti), derivasi tidak/belum berakhir jika sentensial yang dihasilkan mengandung simbol non terminal.

GRAMMAR DAN KLASIFIKASI CHOMSKY

Grammar G didefinisikan sebagai pasangan 4 Tuple : VT, VN, S , Q dan dituliskan sebagai G (VT, VN, S, Q), dimana :

VT           : himpunan simbol terminal (atau himpunan token-token, atau alphabet)

VN           : himpunan simbol-simbol non termnal

S ϵ VN    : simbol awal (atau simbol start)

Q             : himpunan produksi

Berdasarkan komposisi bentuk ruas kiri dan kanan produksinya (α → β), Noam Chomsky mengklasifikasikan 4 tipe grammar :

1. Grammar tipe-0 : UNRESTRICTED GRAMMAR (UG)

Ciri : α, β ϵ (VT | VN)*, | α | > 0

2. Grammar tipe-1 : CONTEXT SENSITIVE GRAMMAR (CSG)

Ciri : α, β ϵ (VT | VN)*, 0 < | α | ≤ | β |

3. Grammar tipe-2 : CONTEXT FREE GRAMMAR (CFG)

Ciri : α ϵ VN , β ϵ (VT | VN)*

4. Grammar tipe-3 : REGULLAR GRAMMAR (RG)

Ciri : α ϵ VN , β ϵ {VT , VT VN} atau α ϵ VN , β ϵ {VT , VN VT }

Mengingat ketentuan simbol-simbol  maka ciri RG sering ditulis sebagai :

α ϵ VN , β ϵ {a , bC}  atau α ϵ VN , β ϵ {a , Bc}

Contoh analisa penentuan type grammar

1. Grammar G1 dengan Q1 = {S→aB, B→bB, B→b}.

2. Grammar G2 dengan Q2 = {S→Ba, B→bB, B→b}.

Jawab :

1. Grammar G1 dengan Q1 = {S→aB, B→bB, B→b}. Ruas kiri semua produksinya terdiri dari sebuah VN maka G1 kemungkinan type CFG atau RG.

Selanjutnya karena semua ruas kanannya terdiri dari sebuah VT atau String VT VN maka G1 adalah RG

2. Grammar G2 dengan Q2 = {S→Ba, B→bB, B→b}.  Ruas kiri semua produksinya terdiri dari sebuah VN maka G2 kemungkinan type CFG atau RG.

Selanjutnya karena semua ruas kanannya mengandung String VT VN (yaitu bB) dan juga String VN VT (Ba) maka G3 bukan RG, dengan kata lain G3 adalah CFG