Ujian Akhir Semester 5 - Teori Bahasa & Otamata

Membuat Mesin Abstrak = FSA & Grammer

1. FSA ( Finite State Automata )

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

Finite automata dinyatakan oleh 5 tupel,yaitu :

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

Q = himpunan state
Σ = himpunan simbol input
δ = fungsi transisi δ : Q × Σ
S = state awal / initial state , S ∈ Q
F = state akhir, F ⊆ Q

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

1. Q = (q0, q1, q2, q3)

2.  Σ = ( 1,0 )

3. S = q0

4. F = q3

5. δ

 

 

Uji Input :

1. 1101

2. 1011

3. 1001

4. 1110

5. 0111

Hasil Test Run Sebagai Berikut:

2. Grammer

Grammar adalah bentuk abstrak yang di terima (accept ) untuk membangkitkan suatu kalimat otomata bedasarkan suatu aturan tertentu.Grammar di definisikan dengan 4 tupel yaitu :

 G = { V,T,P,S }

Keterangan :

V : Himpunan Simbol Variabel
T : Himpunan Simbol Terminal
P : Kumpulan Aturan Produksi
S : Simbol Awal

Production :

Convert To FA :

Tata bahasa grammer didefinisikan dengan (4) empat tupel :

G = ({ V, T, P, S }) yaitu :

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

T : { a,b,c,d,0 }

P : { S-aB, B-bC, D-cA, A-aC, B-dA, D-dC, S-aD, C=0 }

S : {S}

Hasil Test Run :

JAWABAN DI KERTAS 

NAMA : YAYI DITA UTAMA

NIM     : 171021400377