Nama : Doni Faisal Tanjung

Nim : 111421075

Ekstensi Kom A

2. Tulislah ekspresi regular untuk setiap bahasa-bahasa berikut yang menerima (simbol

input adalah 0 dan 1).

a. Himpunan semua string yang paling banyak memuat sebuah ‘00’dan paling

banyak memuat sebuah ‘11’.

Jawab :

(00 11)+

b. Himpunan semua string yang tidak memuat ‘101’ sebagai bubstring-nya.

Jawab :

(010)*(11)*101

3. Deskripsikan dalam bahasa Indonesia himpunan string yang dinyatakan dalam

ekspresi regular berikut : (11+0)*(00+1)*

Jawab :

Himpunan yang diterima adalah string yang memiliki input q0 dan berakhir di q1

dengan mengalami perulangan.

4. Bentuk finite state automata dari ekspresi regular berikut : 10(0+11)0*1

Jawab :

q1 q0 q2 1,0 0

0,1

1

5. Tentukan ekspresi regular untuk diagram transisi pada gambar 5.34 :

Gambar 5.34 Diagram transisi FSA

Jawab:

ER : 0*+(11*(01)*00)*

6. Tentukan ekspresi regular untuk bahasa yang menerima semua string yang memuat

simbol b dalam jumlah genap. (Σ={a,b}).

7. Buatlah finite state automata dari ekspresi regular c*(a bc)*.

Penyelesaian :

Buatlah finite state automata yang menerima bahasa yang memuat semua string yang

mempunyai ‘0101’ sebagai sub string-nya.( Σ={0,1})

q0 a

c

q1

q0

b,c

q0

1

q1

q2

1

0

0 1

0

Tentukan ekspresi regular untuk bahasa yang diterima oleh NFA berikut.

Q ={q0, q1, q2, q3, q4}

Σ ={0,1}

S = q0

F ={q2, q3, q4}

Fungsi transisi dari NFA tersebut:

δ

0 1

q0 {q1, q4} {q3}

q1 {q1} { q0, q2 }

q2 Ө Ө

q3 Ө {q4}

q4 Ө Ө

Penyelesaian :

ER : 00*1+0+1+11

Tentukan ekspresi regular untuk bahasa yang diterima oleh NFA berikut ini.

Q ={q0,q1,q2}

q4 q0

q2

qf 1 1

0

0 q1

1

0

q3

q2

Σ ={0,1}

S =q0

F ={q0}

Fungsi transisi dari NFA tersebut adalah sebagai berikut.

δ

1 2

q0 { q1 } Ө

q1 Ө { q0, q2 }

q2 { q0 } Ө

Penyelesaian :

ER: (01)*(010)*

Gambarkan NFA dengan transisi ε yang menerima ekspresi regular: 1*

Penyelesaian :

q0 q2 0 1

1

0

q1

q0 ε

1

q1