Definisi Finite State Automata (FSA)  Pengertian 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.

Pengertian FSA
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.

Contoh Sistem dengan state berhingga :
Sistem elevator
Mesin penjual minuman kaleng (vending machine)
Pengatur lampu lalu lintas
Sirkit switching di komputer dan telekomunikasi
Lexical Analyzer
Neuron Nets

Definisi Formal FSA

FSA didefinisikan sebagai pasangan 5 tupel M = {Q, Σ, δ, S, F}.

Q = Himpunan State/ Kedudukan
Σ = Himpunan Simbol Input
δ = Transition Function
S = Start State
F = Final State

Contoh format penulisannya:

Rumus : M = {Q, Σ, δ, S, F}

Q = {Q0, Q1, Q2, Q3, Q4 }
Σ = {0, 1}
S = {Q0}
F=  {Q3}
δ = Transition Function

Setelah kita membuat FSA, langkah selanjutnya uji inputnya menggunakan JFLAP. 

Berikut contoh uji input yang akan kita masukan :

11110	= Accept
11101	= Reject
11011	= Accept
10111	= Reject
01111	= Reject
10110	= Accept

 Hasilnya akan seperti berikut ini :

GRAMMAR DAN BAHASA

Konsep Dasar

1. Dalam pembicaraan grammar, anggota alfabet dinamakan simbol terminal atau token.
2. Kalimat adalah deretan hingga simbol-simbol terminal.
3. Bahasa adalah himpunan kalimat-kalimat. Anggota bahasa bisa tak hingga kalimat.
4. Simbol-simbol berikut adalah simbol terminal :

• huruf kecil awal alfabet, misalnya : a, b, c
• simbol operator, misalnya : +, −, dan ×
•  simbol tanda baca, misalnya : (, ), dan ;
• string yang tercetak tebal, misalnya : if, then, dan else.

       5. Simbol-simbol berikut adalah simbol non terminal :

• huruf besar awal alfabet, misalnya : A, B, C
• huruf S sebagai simbol awal
• string yang tercetak miring, misalnya : expr dan stmt.

      6. Huruf besar akhir alfabet melambangkan simbol terminal atau non terminal, misalnya : X, Y, Z.
      7. Huruf kecil akhir alfabet melambangkan string yang tersusun atas simbol-simbol terminal, misalnya : x, y, z.

Grammar dan Klasifikasi Chomsky

Grammar G didefinisikan sebagai pasangan 4 tupel  G = {V, T, P, S)}

Contoh format Penuliasnnya :

Rumusnya G = {V, T, P ,S}

V = {S, A, B, C, D}
T = {0,1,2,3}
S = {S}
P = {S→0,S→1B,S→2C,A→2C,A→1,B→1D,B→1A,C→3,D→B}

Setelah kita membuat grammer kita uji dengan input sebagai berikut :

11123 = ACCEPT

11231 = REJECT

12311 = REJECT

11121 = REJECT

11210 = REJECT

31121 = REJECT

11111 = ACCEPT

Sekian dan Terimakasih