FSA

Finite state automata

Finite state automata 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.
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 State Automata dinyatakan oleh pasangan 5 tuple, 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

CONTOH SOAL

 

1. setiap kelompok buatlah FSA tersebut dalam bentuk formal yang terdiri dari 5 buah tuple.

 jawaban :

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

Q = himpunan state/kedudukan { q1, q2, q3, q4 }
Σ = abjad,himpunan simbol input { 0,1 }
δ = fungsi transisi
S = { q1 }
F = { q4 }

 

2. tentukan string berikut apakah diterima atau tidak
  • 1101
  • 0101
  • 1001
  • 1110
  • 0001
 jawab : 



link ppt

https://drive.google.com/open?id=1yDTyXpV_IxQXKMuEz0an8AHzA2U3994_

Komentar

Posting Komentar

Postingan populer dari blog ini

Ujian Akhir Semester 5 - Teori Bahasa & Otamata

Gambar
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 t...
Baca selengkapnya

Grammar

Gambar
                                                                             GRAMMAR 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 Berikut di bawah adalah mesin abstrak Grammar yang kami buat : Production Convert to FA Penjelasan dari bentuk formal dari 4 tupel yang di atas V  : ( A,B,C,D,E )                         T  :  ( ab,cd,ef,gh,ij,kl,mn,op,qz )                   ...
Baca selengkapnya

UTS OTOMATA

Gambar
NAMA                    : YAYI DITA UTAMA NIM                         : 171021400377 KELAS                    : 05TPLP002 MATA KULIAH   : TEORI BAHASA & OTOMATA GRAMMAR Grammar memliki 4 tupel yaitu   G : ( V,T,P,S ) V : Himpunan simbol variabel T : Himpunan simbol terminal/Input P : Kumpulan aturan produksi S : Simbol awal 1.      MESIN ABSTRAK PRODUCTION PENJELASAN V : ( S,A,B,C ) T : ( A,B ) P : ( S-aA, S-bB, S-aC, A-bA, A-B, B-aB, B-a, C-0 S : Simbol Awal { S } 2  .      FSA Finite State Automata adalah mesin abstrak berupa sistem model matematika yang dapat menerima input dan mengeluarkan output yang memiliki state hinnga banyaknya,dan dapat berpindah dari s...
Baca selengkapnya