Bahasa dan Automata

UTS Pengantar Bahasa dan Otomata

(HARIYANTO RESTUDIAN/161021450166/ERESHA/05TPLE003)

UTS PENGANTAR BAHASA DAN OTOMATA

Dosen Agus Suharto

 Assallamuallaikum wr.wb

Kali ini saya akan memaparkan beberaapa tugas Pengantar Bahasa dan Otomata yang meliputi (FSA) Finite State Automata dan Grammar Automata.

Finite State Automata

Finite State Automata / State Otomata berhingga, selanjutnya kita sebut sebagai FSA, bukanlah mesin fisik tetapi suatu model matematika dari suatu sistem yang menerima input dan output diskrit.

Finite State Automata merupakan mesin otomata dari bahasa regular. Suatu Finite State Automata memiliki state yang banyaknya berhingga, dan dapat berpindah-pindah dari suatu state ke state lain.

Secara formal finite state automata dinyatakan oleh 5 tupel atau M=(Q, Σ, δ, S, F), di mana :

Q   = himpunan state / kedudukan

Σ   = himpunan simbol input / masukan / abjad

δ    = fungsi transisi

S   = state awal / kedudukan awal (initial state)

F   = himpunan state akhir

Sebagai contoh, kita memiliki sebuah otomata seperti pada gambar di bawah ini.

Contoh gambar 1

·         Ia memiliki lima state, berlabel q0, q1, q2,q3 dan q4.

·         State awal(Initial) yaitu q0, ditunjukkan oleh panah yang menunjuknya entah dari mana.

·         Panah yang berpindah dari satu kondisi ke kondisi lain disebut transisi (a dan b).

·         State terima(Final) q4, dengan lingkaran ganda.

Deskripsi :

M   ={Q, Σ, S, F}

Q   = {q0, q1, q2, q3,q4}

Σ   = {a,b}

S    ={q0}

F   = { q 4 }    

Δ	a	B
q0	q1	0
q1	q2	0
q2	0	q1,q3
q3	q4	0
q4	q1	0

Hasil test step by state Run

Berikut hasil running awal yang saya input. Disini saya inputkan aabb dan hasilnya Accept.

Berikut hasil running kedua yang saya input. Disini saya inputkan aaba dan hasilnya Accept.

Berikut hasil running ketiga yang saya input. Disini saya inputkan aababa dan hasilnya Accept.

Berikut hasil running keemepat yang saya input. Disini saya inputkan aababa dan hasilnya Reject.

Berikut hasil running kelima yang saya input. Disini saya inputkan aabab dan hasilnya Reject.

Grammar automata

Tata  bahasa  (grammar)  bisa  didefinisikan  secara  formal  sebagai  kumpulan  dari himpunan-himpunan variabel, simbol-simbol terminal, simbol awal, yang dibatasi oleh aturan-aturan produksi. Pada tahun 1959, seorang ahli bernama Noam Chomsky melakukan penggolongan tingkatan bahasa menjadi empat, yang disebut dengan hirarki Chomsky. Penggolongan tersebut bisa dilihat pada tabel berikut

Bahasa	Mesin Otomata	Batasan Aturan Produksi
Regular	Finite  State  Automata  (FSA)meliputi Deterministic Finite Automata (DFA) & Non Deterministic Finite Automata (NFA)	α adalah sebuah     symbol variabel. β maksimal memiliki sebuah simbol variabel yang bila ada terletak di posisi paling kanan
Bebas Konteks / Context Free	Push Down Automata (PDA)	α    berupa    sebuah    simbol variable
Context Sensitive	Linier Bounded Automata	|α| ≤ |β|
Unrestricted / Phase Structure / Natural Language	Mesin Turing	Tidak ada batasan

Secara umum tata bahasa dirumuskan sebagai :

α → β, yang berarti α menghasilkan β atau α menurunkan β.

Di mana α menyatakan simbol-simbol pada ruas kiri aturan produksi (sebelah kiri tanda ‘→’) dan β menyatakan simbol-simbol pada ruas kanan aturan produksi (sebelah kanan tanda ‘→’)

Simbol variabel / non terminal adalah simbol yang masih bisa diturunkan dan ditandai dengan huruf besar seperti A, B, C, dst.

Simbol terminal adalah simbol yang sudah tidak bisa diturunkan dan ditandai dengan huruf kecil seperti a, b, c, dst

Secara formal Grammar dinyatakan oleh 4 tupel atau G = (V, T, P, S) di mana :

    V = Hingga set simbol non-terminal terbatas

    T = Set terbatas simbol terminal

    P = Himpunan aturan produksi yang tidak kosong

    S = Mulai simbol

Contoh gambar 1

·         Ia memiliki enam state, berlabel q0, q1, q2,q3,q4 dan q5.

·         State awal(Initial) yaitu q0, ditunjukkan oleh panah yang menunjuknya entah dari mana.

·         Panah yang berpindah dari satu kondisi ke kondisi lain disebut transisi (1 dan 0).

·         State terima(Final) q5, dengan lingkaran ganda.

Deskripsi :

    G = {V, T, P, S}

    V = {S, A, B, C}

    T =  {0,1}

    P = {S →1S, S→1A,  A→0B, C→1D,  D→1E, E→1S, B→1D, B→0C, A→0B, E→e}

    S =  {S}

Hasil test step by state Run

Berikut hasil running awal yang saya input. Disini saya inputkan 110111 dan hasilnya Accept.

Berikut hasil running yang kedua. Saya inputkan 11011 dan hasilnya, Accept.

 Berikut hasil running yang ketiga. Saya inputkan 11001 dan hasilnya, Reject.

Berikut hasil running yang keempat. Saya inputkan 110011 dan hasilnya, Accept.

Berikut hasil running yang kelima. Saya inputkan 1101 dan hasilnya, Accept.

Sekian Terima Kasih..

semoga bermanfaat dan sekiranya ada yang salah mohon dikoreksi