UTS Bahasa Automata

TUGAS UAS MEMBUAT 2 MESIN ABSTRAK

  

1) Grammar

• Definisi Grammar

Tata Bahasa (grammar) bisa didefinisikan secara formal sebagai kumpulan dari himpunan-himpunan variabel. Simbol-symbol terminal, symbol 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.

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 symbol-symbol 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.

•  4 tuple 

Secara formal Grammar dinyatakan dengan 4-tuple yaitu: V, T, P, dan S.

Dimana : 

V = Himpunan Variable (Ditandai dengan huruf besar)

T = Himpunan terminal (Ditandai dengan huruf kecil)

P = Himpunan Produksi

S = State awal

Lalu kita akan membuat uji coba Grammar sebagai berikut.

1. Pertama tama kita membuka aplikasi JFAP dan kita pilih Grammar.

2. Lalu Kita masukan himpunan produksinya.dan pilih convert right linear grammar to FA,

3. lalu kita pilih show all dan kita atur sedemikian rupa menjadi seperti berikut.

Setelah melakukan Uji coba Grammar, berikut konversi mesin abstrak diatas menjadi 4 tuple yaitu :

V = { A,B,C,D,E,F}

T = {a,b,y,p,z,λ}

P = {A→aB, A→bB, B→aC, B→bC, C→aD, C→bD, D→aE, D→bE, E→aF, E→bF, C→λ, A-→z,E→y, F→aA, F→bA, F→p}

S = A

uji input menggunakan 5 uji input di multiple CYK parse sebagai berikut.

Berikut yang saya gambar dalam uas.

2) Finite State Automata

• Definisi FSA (Finite State Automata)

Finite State Automata adalah model matematika yang dapat menerima input dan mengeluarkan output yang memiliki state yang berpindah dari satu state ke state yang lainnya berdasarkan input dan fungsi transisi. Finite state automata tidak memiliki tempat penyimpanan/memory, hanya bisa mengingat state terkini.

selanjutnya kita membuka jflap dan memilih finite Automaton (finite state automata).

• Tuple FSA (Finite State Automata)

Secara formal FSA dinyatakan dengan 5-tuple atau M =(Q, Σ, δ, q0, F):

1. Q = himpunan state/kedudukan

2. Σ = abjad, himpunan simbol input

3. δ = transition function

4. q0 ∈ Q = start state/initial state

5. F ⊆ Q = final states

Kita dapat menggambarkan dengan menulis M1 =(Q, Σ, δ, q0, F), dimana:

1. Q = {q1, q2, q3, q4,q5,q6}

2. Σ = {a,b,p,y,z,λ}

3. δ dapat digambarkan sebagai berikut.

4. q0 adalah start state

5. F = {q6}

Selanjutnya, Kita akan uji coba FSA tersebut dengan step by step sebagai berikut:

1. kode input "bbbay" diterima dikarenakan dia berhenti di final state yaitu q6.

2. kode input "ababap" diterima dikarenakan dia berhenti di final state yaitu q6.

3.kode input "bbbaaaz" diterima dikarenakan dia berhenti di final state yaitu q6.

4. kode input "abbbbb" ditolak dikarenakan dia berhenti di state lain dari final state yaitu q0.

5. berikut uji inputnya dengan multiple run,

berikut kertas ujian uas nya

Sekian Dari Saya bila masih banyak kekurangan bisa komentar dibawah dengan senang hati saya menerima saran dan kritik yang membangun karena saya pun masih perlu banyak belajar, Terima kasih :)