Grammar and FSA

GRAMMAR

Grammar adalah bentuk mesin abstrak yang dapat diterima (accept) untuk membangkitkan suatu kalimat otomata berdasarkan suatu kalimat berdasarkan suatu aturan tertentu.

Tata Bahasa (grammar) didefinisikan dengan empat (4) tupel

G = ({V, T, P, S}) dimana :
V = Himpunan simbol variabel / non terminal
T = Himpunan simbol terminal
P = Kumpulan aturan produksi
S = Simbol  awal

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

T = { x, y }

P = { S → λ, A → λ, B → λ, C → λ, S → xA, A →yB, B → xC, C→ yS, S → yC, A →xS, B →

         yA, C→ xB, D → λ, D → yA, D → xB }

S = S (start)

Convert Right Linier Grammar to FA

FSA

Finite State Automata (FSA)

Finite State Automata (FSA) adalah mesin abstrak berupa sistem model matematika dengan masukan dan keluaran diskrit yang dapat mengenali bahasa paling sederhana (bahasa reguler) dan dapat diimplementasikan secara nyata.

Bahasa yang paling sederhana adalah bahasa reguler (tipe 3). Mesin yang bisa mengenalinya adalah Finite Automata. Finite Automata adalah mesin komputasi. Pada bahasan ini mesin komputasi yang dimaksud adalah mesin abstrak bukan mesin fisik, namun memadai untuk diimplementasikan secara nyata.

DEFINISI SECARA FORMAL

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

1. Q = himpunan state/kedudukan

2. Σ = abjad, himpunan simbol input

3. δ = transition function

4. q₀ ∈ Q = start state

5. F ⊆

Q = set of accept (or final) states

v  Gambar di atas disebut diagram keadaan M1

v  Ia memiliki enam status, berlabel q0,q1, q2, q3, q4 dan q5

v  Status awal, q2, ditunjukkan oleh panah yang menunjuknya entah dari mana

v  Status terima, q5, adalah negara dengan lingkaran ganda

v  Panah yang berpindah dari satu kondisi ke kondisi lain disebut transisi

Kita dapat menggambarkan secara formal dengan menulis M1 = (Q, Σ, δ, q0, F)), di mana:

1. Q=  {q0, q1, q2, q3, q4, q5}
2. Σ = {x, y, λ}
3. δ digambarkan sebagai :

4. q2 adalah kondisi awal, dan
5. F = {q5}

Multiple Run

 Lembar Jawaban

Fine State Automata

Finite State Automata (FSA)

Finite State Automata (FSA) adalah mesin abstrak berupa sistem model matematika dengan masukan dan keluaran diskrit yang dapat mengenali bahasa paling sederhana (bahasa reguler) dan dapat diimplementasikan secara nyata.

Bahasa yang paling sederhana adalah bahasa reguler (tipe 3). Mesin yang bisa mengenalinya adalah Finite Automata. Finite Automata adalah mesin komputasi. Pada bahasan ini mesin komputasi yang dimaksud adalah mesin abstrak bukan mesin fisik, namun memadai untuk diimplementasikan secara nyata.

DEFINISI SECARA FORMAL

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

1. Q = himpunan state/kedudukan

2. Σ = abjad, himpunan simbol input

3. δ = transition function

4. q₀ ∈ Q = start state

5. F ⊆ Q = set of accept (or final) states

DEFINISI SECARA FORMAL

v  Gambar di atas disebut diagram keadaan M1

v  Ia memiliki empat status, berlabel q0,q1, q2, dan q3

v  Status awal, q0, ditunjukkan oleh panah yang menunjuknya entah dari mana

v  Status terima, q0, adalah negara dengan lingkaran ganda

v  Panah yang berpindah dari satu kondisi ke kondisi lain disebut transisi

Contoh fsa

Kita dapat menggambarkan secara formal dengan menulis M1 = (Q, Σ, δ, q0, F)), di mana:

1. Q=  {q0,q₁, q₂, q₃}
2. Σ = {0, 1}
3. δ digambarkan sebagai :
4. q0 adalah kondisi awal, dan
5. F = {q0}

	0	1
Q0	Q2	Q1
Q1	Q3	Q0
Q2	Q0	Q3
Q3	Q1	Q2

-          Uji Input Step With Closure

1101

Ditolak

-          Uji Input Step By Step

0101

Diterima

-          Uji Input Fast Run

1001

Diterima

-          Uji Input Multiple Run

1110

Direject