NFA. Teori Bahasa dan Automata. Viska Mutiawani - Informatika FMIPA Unsyiah

NFA Teori Bahasa dan Automata

Viska Mutiawani - Informatika FMIPA Unsyiah

1

NFA • NFA: Nondeterministic Finite Automata – Atau Automata Hingga NonDeterministik (AHND) – Salah satu bentuk dari Finite Automata

• NFA memiliki kemampuan untuk berada pada beberapa state pada waktu yang sama • Transisi dari suatu state terhadap suatu simbol input dapat berpindah ke beberapa state Viska Mutiawani - Informatika FMIPA Unsyiah

2

NFA • Bermula dari state awal • Output “terima” jika pemilihan transisi berdasarkan input berakhir di state akhir • Secara intuisi: NFA selalu “menebak yang benar”


3

Nondeterministic Finite Automaton

(NFA)

Alphabet = {a}

a

q0

q1 a

q2

a

q3 Viska Mutiawani - Informatika FMIPA Unsyiah

4

Alphabet = {a}

Ada dua pilihan

a

q0

q1 a

q2

Tidak ada transisi

a

q3

Tidak ada transisi


5

Pilihan pertama a a

a

q0

q1 a

q2

a


6

Pilihan pertama a a

a

q0

q1 a

q2

a


7

First Choice a a Semua input berhasil dihabiskan

a

q0

q1 a

q2

“terima”

a


8

Pilihan kedua a a

a

q0

q1 a

q2

a


9

Pilihan kedua a a Tidak semua input berhasil dihabiskan

a

q0

a

q1 a

q2

Automaton Halt/berhenti

q3

“tolak”


10

Suatu NFA menerima input string: Jika ada suatu proses komputasi pada NFA yang menerima string tersebut

Maksudnya: semua input string berhasil diproses dan automaton berada di state penerima


11

aa

diterima oleh NFA di bawah:

“terima” a

q0

q1

a

q2

a

q0

a

q3 Ini komputasi yang menerima aa

q1 a

q2

a

q3

“tolak”

Komputasi ini diabaikan


12

Contoh penolakan a

a

q0

q1 a

q2

a


13

Pilihan pertama a “tolak”

a

q0

q1 a

q2

a


14

Pilihan kedua a

a

q0

q1 a

q2

a


15

Pilihan kedua a

a

q0

q1 a

q2

a

q3

“tolak”


16

Contoh penolakan lainnya a a a

a

q0

q1 a

q2

a


17

Pilihan pertama a a a

a

q0

q1 a

q2

a


18

Pilihan pertama a a a Tidak semua input berhasil dihabiskan

a

q0

q1 a

a

q2

“tolak”

Automaton halt/berhenti


19

Pilihan kedua a a a

a

q0

q1 a

q2

a


20

Pilihan kedua a a a Tidak semua input berhasil dihabiskan

a

q0

q1 a

q2

Automaton halt/berhenti

a

q3

“tolak”


21

Suatu NFA menolak input string: Jika tidak ada suatu proses komputasi pada NFA yang menerima string tersebut. Untuk setiap proses komputasi: • Semua input berhasil dihabiskan namun automaton berada bukan pada state penerima ATAU • Belum semua input berhasil dihabiskan Viska Mutiawani - Informatika FMIPA Unsyiah

22

a ditolak oleh NFA di bawah

“tolak” a

q0

q1 a

q2

a

q0

a

q3

“tolak”

q1 a

q2

a

q3

Semua komputasi yang mungkin berakhir dengan penolakan Viska Mutiawani - Informatika FMIPA Unsyiah

23

aaa ditolak oleh NFA di bawah

“tolak” a

q0

q1

a

q2

a

q0

a

q3

q1 a

q2

a

q3

“tolak”

Semua komputasi yang mungkin berakhir dengan penolakan Viska Mutiawani - Informatika FMIPA Unsyiah

24

Bahasa yang diterima:

a

q0

q1 a

L  {aa} q2

a


25

Transisi Lambda

q0 a

q1 

q2 a


q3

26

a a

q0 a

q1 

q2 a


q3

27

a a

q0 a

q1 

q2 a


q3

28

Kepala input tape head tidak bergerak

a a

q0 a

q1 

q2 a

q3

Automaton berpindah state Viska Mutiawani - Informatika FMIPA Unsyiah

29

Semua input berhasil dihabiskan

a a

“terima”

q0 a

q1 

q2 a

q3

String aa diterima Viska Mutiawani - Informatika FMIPA Unsyiah

30

Contoh penolakan a a a

q0 a

q1 

q2 a


q3

31

a a a

q0 a

q1 

q2 a


q3

32

Kepala tape tidak bergerak

a a a

q0 a

q1 

q2 a


q3

33

Belum semua input berhasil dihabiskan

a a a Automaton halt/berhenti “tolak”

q0 a

q1 

q2 a

q3

String aaa ditolak Viska Mutiawani - Informatika FMIPA Unsyiah

34

Bahasa yang diterima:

q0 a

q1 

L  {aa}

q2 a


q3

35

Contoh lain NFA

q0

a

b

q1

q2



q3

 Viska Mutiawani - Informatika FMIPA Unsyiah

36

a b

q0

a

b

q1

q2



q3


37

a b

q0

a

b

q1

q2



q3


38

a b

“terima”

q0

a

b

q1

q2



q3


39

String yang lain

a b a b

q0

a

b

q1

q2



q3


40

a b a b

q0

a

b

q1

q2



q3


41

a b a b

q0

a

b

q1

q2



q3


42

a b a b

q0

a

b

q1

q2



q3


43

a b a b

q0

a

b

q1

q2



q3


44

a b a b

q0

a

b

q1

q2



q3


45

a b a b

“terima”

q0

a

b

q1

q2



q3


46

Bahasa yang diterima

L  ab, abab, ababab, ... 

 ab

q0

a

b

q1

q2



q3


47

Contoh lain NFA

0 q0

1

q1

0, 1 q2


48

Bahasa yang diterima

L(M ) = {λ, 10, 1010, 101010, ...} = {10} *

0 q0

1

q1

0, 1 q2

(redundant state)


49

Perhatikan: •Simbol  tidak pernah muncul pada input tape •Automata sederhana:

M1 q0

M2

L( M1 ) = {}

L( M 2 ) = {λ}

q0


50

•NFA lebih menarik karena kita dapat mengekspresikan bahasa lebih sederhana dibanding DFA

NFA

q0

DFA

M1 a

q2

q1

a q0

L( M 1 ) = {a}


a

M2

a

q1

L( M 2 ) = {a} 51

Definisi Formal dari NFA M  Q, ,  , q0 , F  Q: : : q0 : F:

Set/kumpulan state q0 , q1, q2  Alfabet input, contoh a, b    Fungsi transisi State awal Set/kumpulan state penerima Viska Mutiawani - Informatika FMIPA Unsyiah

52

Fungsi transisi  Fungsi transisi DFA:  : Q    Q Fungsi transisi NFA:  : Q  (  {})  (Q) x

q

x

q1 q1

x

State hasil dengan satu transisi terhadap simbol x

 q, x   q1 , q2 , , qk 

qk Viska Mutiawani - Informatika FMIPA Unsyiah

53

 q0 , 1  q1 0 q0

1

q1

0, 1 q 2


54

 (q1,0)  {q0 , q2 } 0 q0

1

q1

0, 1 q 2


55

 (q0 ,  )  {q2 } 0 q0

1

q1

0, 1 q 2


56

 (q2 ,1)   0 q0

1

q1

0, 1 q 2


57

Bisakah anda membuat tabel transisi untuk NFA? 0

1

λ

q0

{}

{q1}

{q2}

q1

{q0, q2}

{q2}

{}

q2

{}

{}

{}


58

Fungsi transisi diperluas 

*

Sama saja dengan  namun berlaku pada string

 q0 , a   q1 *

q5

q4

a a q0

a

b

q1



q2




q3 59

 q0 , aa   q4 , q5  *

q5

q4

a a q0

a

b

q1



q2




q3 60

 q0 , ab   q2 , q3 , q0  *

q5

q4

a a q0

a

b

q1



q2




q3 61

Kasus khusus:

Untuk setiap state q

q   q,   *


62

Secara umum

q j   qi , w Bermakna ada jalan dari qi *

menuju

q j dengan label w

w

qi

qj

w   1 2  k

qi

1

2 Viska Mutiawani - Informatika FMIPA Unsyiah

k

qj 63

Bahasa dari NFA M Bahasa yang diterima oleh

M

adalah:

LM   w1 , w2 ,...wn  *

dimana  ( q0 , wm )  {qi ,..., qk ,  , q j } dan terdapat

qk  F

(state penerima)


64

*

wm  LM 

 (q0 , wm ) qi

wm

qk

q0 w m wm

qk  F

qj


65

F  q0 ,q5 

q5

q4

a a a

q0

b

q1

q2



q3





 q0 , aa   q4 , q5 *



aa  L(M )

F Viska Mutiawani - Informatika FMIPA Unsyiah

66

F  q0 ,q5 

q5

q4

a a a

q0

b

q1

q2



q3





 q0 , ab   q2 , q3 , q0 *



ab  LM 

F Viska Mutiawani - Informatika FMIPA Unsyiah

67

F  q0 ,q5 

q5

q4

a a q0

a

b

q1

q2



q3





 q0 , abaa   q4 , q5 *



aaba  L(M ) F


68

F  q0 ,q5 

q5

q4

a a q0

a

b

q1

q2



q3



aba  LM 

 q0 , aba   q1  *

F Viska Mutiawani - Informatika FMIPA Unsyiah

69

q5

q4

a a q0

a

b

q1

q2



q3

 LM   ab*  ab* {aa} Viska Mutiawani - Informatika FMIPA Unsyiah

70

NFA menerima Bahasa Regular

Viska Mutiawani - Informatika FMIPA 71 Unsyiah

Ekuivalensi Mesin Otomata Definisi: Mesin M1 dikatakan ekuivalen dengan mesin M 2 jika

L M1   L M 2 


72

Contoh mesin yang ekuivalen

M1

NFA

0

LM1   {10} *

q0

1

M2

DFA

LM 2   {10} *

q1

0,1

0 q0

1


q1 0

1

q2 73

Teorema: Bahasa diterima oleh NFA



Bahasa Regular Bahasa yang diterima oleh DFA

NFA dan DFA memiliki kekuatan komputasi yang sama, dan menerima set bahasa yang sama Viska Mutiawani - Informatika FMIPA Unsyiah

74

Set equality A = B dapat dibuktikan dengan A subset B dan A superset dari B

Pembuktian:

Kita tunjukkan:

Bahasa diterima oleh NFA



Bahasa Regular

AND Bahasa diterima oleh NFA

 Viska Mutiawani - Informatika FMIPA Unsyiah

Bahasa Regular

75

Pembuktian tahap 1 Bahasa diterima oleh NFA



Bahasa Regular

Setiap DFA secara otomatis juga merupakan NFA

L

Setiap bahasa yang diterima oleh DFA Pastilah juga diterima oleh NFA Viska Mutiawani - Informatika FMIPA Unsyiah

76

Pembuktian tahap 2 Bahasa diterima oleh NFA



Bahasa Regular

Setiap NFA dapat dikonversi ke bentuk DFA yang ekuivalen

L

Setiap bahasa yang diterima oleh NFA Pastilah juga diterima oleh DFA Viska Mutiawani - Informatika FMIPA Unsyiah

77

Konversi NFA ke DFA NFA

a

M q0

a



q1

q2

b DFA

M

q0  Viska Mutiawani - Informatika FMIPA Unsyiah

78

NFA

 * (q0 , a )  {q1 , q2 } a

M q0

a



q1

q2

b DFA

M

q0 

a

q1, q2 


79

NFA

 * ( q0 , b )   a

M q0

a

Set kosong



q1

q2

b DFA

M a

q0 

q1, q2 

b



State jebakan


80

NFA

 * (q1 , a )  {q1 , q2 }  * ( q2 , a )  

a

M q0

a



q1

union

q2

q1, q2 

b DFA

a

M a

q0 

q1, q2 

b




81

*

NFA

 (q1 , b)  {q0 }  * ( q2 , b)  {q0 }

a

M q0

a



q1

union

q2

q0 

b DFA

a

b

M

a

q0 

q1, q2 

b




82

NFA

a

M q0

a



q1

q2

b DFA

a

b

M

a

q0 

q1, q2 

b



a, b


trap state 83

Akhir konstruksi NFA

a

M q0

a



q1

q2

q1  F

b DFA

a

b

M

a

q0 

q1, q2 

b



q1, q2  F 

a, b


84

Prosedur konversi NFA ke DFA Input: suatu NFA

M

Output: suatu DFA M yang ekuivalen sehingga L M   L(M )


85

Jika NFA memiliki state

q0 , q1, q2 ,...

Maka DFA memiliki state yang berasal dari power set

, q0 , q1 , q0 , q1 , q1 , q2 , q3 , ....


86

Langkah-langkah konversi langkah

1. State awal NFA: q0  q0 ,    q0 ,  *

state awal DFA: q0 , 


87

 q0 ,    q0  *

NFA

a

M q0

a



q1

q2

b DFA

M

q0 


88

langkah

2. Untuk setiap state DFA

{qi , q j ,...,qm}

komputasikan pada NFA

 * qi , a    * q j , a  ...

Union

 {qk , ql,..., qn }

  * qm , a  tambah transisi ke DFA

 {qi , q j ,..., qm }, a   {qk , ql,..., qn } Viska Mutiawani - Informatika FMIPA Unsyiah

89

Example NFA

 * ( q0 , a )  {q1, q2 } a M  q2 q0 a q1 b

DFA

M

q0 

a

q1, q2 

 q0 , a   q1, q2  Viska Mutiawani - Informatika FMIPA Unsyiah

90

langkah

3. Ulangi langkah 2 untuk setiap state pada DFA dan semua simbol dalam alfabet hingga tidak ada lagi state yang bisa ditambahkan ke DFA


91

NFA

a

M q0

a



q1

q2

b DFA

a

b

M

a

q0 

q1, q2 

b



a, b


92

langkah

4. Untuk setiap state pada DFA {qi , q j ,..., qm } jikaq j merupakan state penerima pada NFA maka, {qi , q j ,..., qm } merupakan state penerima pada DFA


93

NFA

a

M q0

a



q1

q1  F

q2

b DFA

a

b

M

a

q0 

q1, q2 

b



q1, q2  F 

a, b


94

Lemma: Jika kita berhasil mengkonversi NFA M ke DFA M  maka kedua otomata tersebut ekuivalen L M  L M 

 





Proof: Kita akan tunjukkan:

L M   L M   dan

L M   L M   Viska Mutiawani - Informatika FMIPA Unsyiah

95

Pertama sekali tunjukkan:

L M   L M  Kita buktikan dengan cara:

w L(M )

w  L(M )


96

NFA Kita pertimbangkan:

w L(M ) w

q0

qf

simbol

w   1 2  k q0

1

2


k

qf 97

simbol

qi

i

qj

Merupakan ringkasan dari sub-path

simbol

qi





i




qj

98

w L(M )

Kita tunjukkan jika

w   1 2  k NFA

M:

q0

1

k

2

qf

maka

DFA

1

M:

{q0 , }

state label

2

w  L(M ) Viska Mutiawani - Informatika FMIPA Unsyiah

k

{q f ,} state label 99

Secara lebih umum, kita tunjukkan bahwa pada

v  a1a2  an

(string apapun) NFA

M:

M

q0

a1

qi

a2

qj

ql

an

qm

maka

DFA

a1

M: {q0 , }

a2

{qi ,} {q j ,} Viska Mutiawani - Informatika FMIPA Unsyiah

an

{ql ,} {qm ,} 100

Pembuktian secara induksi

NFA

DFA

v  a1

|v | 1

Dasar induksi:

M: M:

q0

|v|

a1

qi

a1 {q0 , }

{qi ,}

Adalah benar sewaktu pengkonversian menjadi Viska Mutiawani - Informatika FMIPA Unsyiah

M 101

1 | v | k v  a1a2  ak

Hipotesis induksi:

Anggap seperti di bawah NFA

DFA

M:

M:

a1

q0

a1 {q0 , }

qi

a2

qj

a2 {qi ,} {q j ,}


qc

ak

qd

ak {qc ,} {qd ,} 102

| v | k  1 v  a1a2  ak ak 1  vak 1  

Langkah induksi:

v Maka terbukti benar dengan adanya konstruksi NFA

M:

q0

a1

qi

a2

qj

qc

ak

M qd

ak 1

qe

v DFA

a1

M: {q0 , }

ak

a2 {qi ,} {q j ,}

v


ak 1

{qc ,} {qd ,}

{qe ,} 103

Oleh karena itu jika

w L(M ) w   1 2  k

NFA

M:

q0

1

k

2

qf

maka

DFA

M:

1

{q0 , }

2

w  L(M ) Viska Mutiawani - Informatika FMIPA Unsyiah

k

{q f ,} 104

Kita telah tunjukkan:

L M   L M  

Dengan cara yang sama, kita juga dapat buktikan:

L M   L M  

Maka:

LM   LM  Akhir pembuktian Viska Mutiawani - Informatika FMIPA Unsyiah

105

Jadi apa kesimpulan akhirnya?


106

NFA. Teori Bahasa dan Automata. Viska Mutiawani - Informatika FMIPA Unsyiah

Recommend Documents