TEORI BAHASA AUTOMATA
TUGAS 1
FSA
NAMA : ARDIN
KLS : T1.15
NIM : 55 201 08041
DIAGRAM
M = ( Q, ∑, δ, S, F )
Q = { A, B, C, D, E }
∑ = { a, b, c, d, e, f }
S = A
F = { A, C, D }
Tabel Transisi
δ | a | b | c | d | e | f |
A | C | B | 0 | 0 | 0 | 0 |
B | E | 0 | D | E | 0 | 0 |
C | 0 | 0 | D | E | D | E |
D | 0 | 0 | 0 | 0 | 0 | 0 |
E | 0 | 0 | 0 | 0 | 0 | 0 |
Inputan yang diterima
- bc, a, ac, ae
- δ (A, bc) => δ (B, c) => D (Diterima)
- δ (A, a) => C (Diterima)
- δ (A, ac) => δ (C, c) => D (Diterima)
- δ (A, ae) => δ (C, e) => D (Diterima)
Inputan yang ditolak
- b, ad, af, ba, bd
- δ (A, b) => B (Ditolak)
- δ (A, ad) => δ (C, d) => E (Ditolak)
- δ (A, af) => δ (C, f) => E (Ditolak)
- δ (A, ba) => δ (B, a) => E (Ditolak)
- δ (A, bd) => δ (B, d) => E (Ditolak)
Q = { q0,q1,q2,q3,q4 }
∑ = { a,b,c }
S = q0
F = { q4 }
Tabel Transisi
δ | a | b | c |
q0 q1 q2 q3 q4 | {q0,q1} {q1,q4} {q2} {q3} 0 | {q0,q2} {q1} {q2.q4} {q3} 0 | {q0,q3} {q1} {q2} {q3,q4} 0 |
Inputan yang diterima
1. aabb
M (q0,aabb) ⇒ M(q0,abb) ∪ M(q1,abb) ⇒ {M(q0,bb) ∪ M(q1,bb)} ∪ M(q1,bb)
⇒ {{M(q0,b) ∪ M(q2,b)} ∪ M(q1,b)} ∪ M(q1,b)
⇒ {{{q0,q2} ∪ {q2,q4}} ∪ {q1}} ∪ {q1} = {q0,q1,q2,q4}
2. cbc
M (q0,cbc) ⇒ M (q0,bc) ∪ M (q3,bc) ⇒ {M(q0,c) ∪ M(q2,c)} ∪ M(q3,c)
⇒ {{q0,q3} ∪ {q2}} ∪ {q3,q4} = {q0,q2,q3,q4}
3. abaa
M (q0,abaa) ⇒ M(q0,baa) ∪ M(q1,baa) ⇒ {M(q0,aa) ∪ M(q2,aa)} ∪ M(q1,aa)
⇒ {{M(q0,a) ∪ M(q1,a)} ∪ M(q2,a)} ∪ {M(q1,a) ∪ M(q4,a)}
⇒ {{q0,q1} ∪ {q1,q4} ∪ {q2}} ∪ {q1,q4} = {q0,q1,q2,q4}
4. bbab
M (q0,babb) ⇒ M(q0,abb) ∪ M(q2,abb) ⇒ {M(q0,bb) ∪ M(q1,bb)} ∪ M(q2,bb)
⇒ {{M(q0,b) ∪ M(q2,b)} ∪ M(q1,b)} ∪ {M(q2,b) ∪ M(q4,b)}
⇒ {{q0,q2} ∪ {q2,q4} ∪ {q1}} ∪ {q2,q4} = {q0,q1,q2,q4}
5. cabc
M (q0,cabc) ⇒ M(q0,abc) ∪ M(q3,abc) ⇒ {M(q0,bc) ∪ M(q1,bc)} ∪ M(q3,bc)
⇒ {{M(q0,c) ∪ M(q2,c)} ∪ M(q1,c)} ∪ M(q3,c)}
⇒ {{q0,q3} ∪ {q2} ∪ {q1} ∪ {q3,q4}} = {q0,q1,q2,q3,q4}
Inputan yang Tidak diterima
1. abc
M (q0,abc) ⇒ M(q0,bc) ∪ M(q1,bc) ⇒ {M(q0,c) ∪ M(q2,c)} ∪ M(q1,c)
⇒ {{q0,q3} ∪ {q2}} ∪ {q1} = {q0,q1,q2,q3}
2. cab
M (q0,cab) ⇒ M(q0,ab) ∪ M(q3,ab) ⇒ {M(q0,b) ∪ M(q1,b)} ∪ M(q3,b)
⇒ {{q0,q2} ∪ {q1}} ∪ {q3} = {q0,q1,q2,q3}
3. cba
M (q0,cba) ⇒ M(q0,ba) ∪ M(q3,ba) ⇒ {M(q0,a) ∪ M(q2,a)} ∪ M(q3,a)
⇒ {{q0,q1} ∪ {q2} ∪ {q3}} = {q0,q1,q2,q3}
4. bac
M (q0,bac) ⇒ M(q0,ac) ∪ M(q2,ac) ⇒ {M(q0,c) ∪ M(q1,c)} ∪ M(q2,c)
⇒ {{q0,q3} ∪ {q1}} ∪ {q2} = {q0,q1,q2,q3}
5. aab
M (q0,aab) ⇒ M(q0,ab) ∪ M(q1,ab) ⇒ {M(q0,b) ∪ M(q1,b)} ∪ {M(q1,b) ∪ M(q4,b)}
⇒ {{q0,q2} ∪ {q1}} ∪ {q1} = {q0,q1,q2}