Tugas 2 : Teori Bahasa Automata Nondeterministic Finite Automata (NFA)

Nama : Muh Handry Wahyudi

NIM : 55 201 08297

KLS : TI.1.V

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}