Mesin Moore

• FSA (Finite State Automata) yang telah dipelajari adalah FSA yang hanya dapat menerima atau menolak string yang di inputkan
• String “aaabb” diterima atau tidak
• FSA seperti itu disebut ACCEPTER
• String aa dan ba diterima oleh FSA tersebut, sedangkan string yang lain ditolak
• FSA (Finite State Automata) yang mempunyai keputusan sebagai output, Automata ini disebut TRANSDUCER
• Salah satu contoh FSA yang termasuk Transducer atau FSA yang mempunyai output adalah Mesin MOORE
• Pada Mesin Moore outputnya berasosiasi dengan state, atau tertulis pada setiap state
• Sehingga Jumlah State sama dengan jumlah Output
• Salah satu contoh penerapan mesin Moore adalah mesin untuk memperoleh sisa pembagian atau n MOD

Kesimpulan!

Mesin Moore adalah finite-state machine yang outptnya berasosiasi dengan state, atau tertulis pada setiap state, sehingga jumlah state sama dengan jumlah output. Selain itu Mesin Moore tidak memiliki final state.

Definisi formal mesin Moore adalah pasangan 6 tupel M={Q,Σ, δ, S, Δ, λ}

Q : Himpunan State
Σ : Himpunan Input
δ : Fungsi Transisi
S : Simbol State Awal
Δ : Himpunan Output
λ : Fungsi Output untuk setiap state

Contoh Soal:

Mesin Moore untuk menentukan n mod 7 dengan inputan berupa biner !

Jawab:

Karna sisa hasil bagi 7 ada 6 maka outputnya adalah {0,1,2,3,4,5,6,}

M={Q,Σ, δ, S, Δ, λ}

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

Σ = {0,1}

S = {q0}

Δ = {0,1,2,3,4,5,6,}

λ = λ(q0) =0 | λ(q1) =1 | λ(q2) =2 | λ(q3) = 3 | λq4) =4 | λ(q5) =5 |λ(q6) = 6 | 

δ =

Sehingga di dapatkan diagram FSA sebagai berikut :

Sekarang kita coba masukan input  10-15 dan 2, lalu du konversikan ke binary seperti gambar berikut ini :

Kemudian kita uji dengan multiple run maka akan menghasilkan seperti gambar berikut ini:

Terimakasih telah berkunjung ke blog saya.

pengantar bahasa dan otomata

UTS Pengantar Bahasa dan Otomata

UTS PENGANTAR BAHASA DAN OTOMATA

Dosen Agus Suharto

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

·       Gambar di atas disebut diagram state M.

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

·       State awal(Initial) yaitu q0.

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

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

Deskripsi :

M   ={Q, Σ, S, F}

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

Σ   = {0,1}

S    ={q0}

F   = { q 2 }           

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

Hasil test step by state Run diagram M

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

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

       

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

·       Gambar di atas disebut diagram state M.

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

·       State awal(Initial) yaitu q0.

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

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

Deskripsi :

    G = {V, T, P, S}

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

    T =  {0,1}

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

    S =  {S}

Hasil test step by state Run diagram M

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