UTS Pengantar Bahasa dan Otomata

UTS Pengantar Bahasa dan Otomata

(SUDANA NASRUDIN/161021450197/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

•  Ia memiliki empat 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 (1 dan 0). 
• State terima(Final) q3, dengan lingkaran ganda.

Deskripsi : 
M   ={Q, Σ, S, F}
Q   = {q0, q1, q2, q3}
Σ   = {0,1}
S    ={q0}
F   = { q 3 }
    

δ	0	1
q0	q4	q0, q1
q1	q2	q3
q2	0	q3
q3	q2	0
q4	0	q2, q3

Hasil test step by state Run

Berikut hasil running awal yang saya input.

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 variabel
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

• Ia memiliki empat 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 →0S, S→0C, S →1A, A→0B, C→0C, B→1D, B→1E, D→0B, D→0E, D→0S, D→0A,E→λ}

S =  {S}

Hasil test step by state Run diagram M

Berikut hasil running awal yang saya input.