Ujian Akhir Semester 5 Teori Bahasa & Automata

MEMBUAT 2 MESIN ABSTRAK = FSA & MOORE

1. (FSA) Finite State Automata

        

       Finite Automata adalah model matematika sistem dengan masukan dan keluaran diskrit. Finite State Automata adalah model matematika yang dapat menerima inputan dan mengeluarkan output. Memiliki state berhingga banyaknya dan dapat berpindah dari satu ke yang lainnya sesuai dengan inputan dan fungsi transisi.

FSA dinyatakan dengan 5 buah tupel :

Keterangan :

1. Q     = Kumpulan State

2. δ      = Transisi Fungsi

3. Σ      = Simbol Input

4. S/q₀ = Start

5. F      = Final State

Mesin FSA memiliki 5 tupel :

M =(Q, Σ, δ, S, F)

1. Q = {q0,q1, q2}

2. Σ  = { 1, 0 }

3. S = q0

4. F = {q2}

5. δ  =

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

Diuji Dengan Inputan berikut =

1. 10010
2. 10100
3. 100010
4. 010111
5. 10110

Hasil Inputan =

2. MESIN MOORE

  

  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. Mesin Moore ditetapkan ke dalam 6 tuple yaitu sebagai berikut :

M    =   { Q, ∑, δ, S, Δ, λ }
Q    =   Himpunan State
∑    =   Himpunan Input
δ    =   Fungsi Transisi
S    =   Simbol State Awal
Δ    =   Himpunan Output
λ    =   Fungsi Output untuk Setiap State

M  : { Q, ∑, δ, S, Δ, λ }

Q  : { q0, q1, q2, q3, q4,q5}

∑  : { 0, 1 }

S  : { q0 }

Δ  : { 0,1,2,3,4,5 }

λ  : { q0=0 | q1=1 | q2=2 | q3=3 | q4=4  | q5=5 }

δ  : 

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

Masukkan input :

1.    9 mod 6 = 1001

Urutan State = q0, q1, q2, q3

State Terakhir = q3, (q3) = 3

9 mod 6 = 3

2.      15 mod 6 = 1111

Urutan State = q0,q1,q3,q1,q3

State Terakhir = q3, (q3) = 3

15 mod 6 = 3

3.      17 mod 6 = 10001

Urutan State = q0,q1,q2,q4,q2,q5

State Terakhir = q5, (q5) =5

17 mod 6 = 5

4.      8 mod 6 = 1000

Urutan State = q0,q1,q2,q4,q2

State Terakhir = q2, (q2) = 2

8 mod 6 = 2

5.      23 mod 6 = 10111

Urutan State = q0,q1,q2,q5,q5,q5

State Terakhir = q5, (q5) = 5
23 mod 6 = 5

Lalu tes di multiple run seperti berikut :

JAWABAN DI LEMBAR JAWAB