Teori Bahasa dan Automata - Finite Automata

Sistem Finite State:
- Deterministic Finite Automata (DFA)
- Non-Deterministic Finite Automata (NFA)
- Push-Down Automata (PDA)
- Turing Machine
- Linear Bounded Automata

DFA
- Tiap inputan akan mengarah ke satu tujuan yang pasti, antara ke state lain atau ke diri sendiri
contoh = Diketahui Transition Diagram:

Untuk menuju Final state (Q1), Jalur yang dapat ditempuh adalah:
1. Q0 diberi input 0 ke Q1
2. Q0 diberi inputan 1 ke Q2, Q2 diberi input 1 ke Q1

Definisi formal:

Dimana dari Transition Diagram diatas, definisi formalnya menjadi:
Q = {Q0,Q1,Q2}
sigma = {0,1}
F = {Q1}

Fungsi Transisi dapat dibuat melalui Tabel Transisi:

            |       Input
   State  |   0      |      1
______ |_____|______
  ->Q0     |    Q1   |   Q2
    *Q1     |    Q1   |   Q1
     Q2     |    Q2  |   Q1

-> untuk Start State
* untuk Final State

Input yang Benar (berdasarkan transisi diagram):
- 00
- 1001
- 111

Input yang Salah:
- 001
- 100

Syarat String diterima sebagai bahasa dalan Finite State Automata (FSA)
1. Input String habis terbaca, DAN
2. State berpindah dari start state dan berhenti pada final state

Penelusuran String yang diterima (berdasarkan transition diagram)
Misalkan string "001"

NFA

- Tiap input dapat mengarah ke lebih dari satu state berbeda

Contoh: Tabel Transisi NFA

Definisi formal: ( {Q0,Q1,Q2,Q3,Q4}, {0,1},    , Q0, {Q2, Q4} )

Tabel Transisi
            |       Input
   State  |   0      |      1
______ |_____|______
  ->Q0     | {Q0,Q3} |   {Q0,Q1}
     Q1      |            |   Q2
    *Q2     |    Q2    |   Q2
     Q3     |     Q4   |
    *Q4     |      Q4  |  Q4

Konversi NFA ke DFA Ekuivalen

Transition Diagram DFA Ekivalen:

Jawaban dari Latihan Soal RE
1. (0+1)* 01
2. abb (a+b)*
3. (0+1)* 001 (0+1)*
4. (aa + ab + ba + bb)* b
5. ((01 (0+1)*) + ((0+1)* 01))
6. (0+1)* 1 (00+01+10+11)
7. ((a+b+c)* a (a+b+c)* b (a+b+c)*) +((a+b+c)* b (a+b+c)* a (a+b+c)*)