Top Banner
GRAMMAR REGULAR AHD, AHN & EKSPRESI REGULAR Adriani Yulida Kusuma
26

Grammar Regular Ahd, Ahn & Ekspresi Regular

Jun 27, 2015

Download

Documents

Welcome message from author
This document is posted to help you gain knowledge. Please leave a comment to let me know what you think about it! Share it to your friends and learn new things together.
Transcript
Page 1: Grammar Regular Ahd, Ahn & Ekspresi Regular

GRAMMAR REGULAR AHD, AHN &

EKSPRESI REGULARAdriani Yulida Kusuma

Page 2: Grammar Regular Ahd, Ahn & Ekspresi Regular

Klasifikasi Chomsky

Berdasarkan komposisi bentuk ruas kiri dan ruas kanan produksinya ( ), Noam Chomsky mengklasifikasikan 4 tipe grammar :

• Grammar tipe ke-0 : Unrestricted Grammar (UG) , (VTVN)*, > 0• Grammar tipe ke-1 : Context Sensitive Grammar (CSG) , (VTVN)*, 0 < • Grammar tipe ke-2 : Context Free Grammar (CFG) VN, (VTVN)*• Grammar tipe ke-3 : Regular Grammar (RG) VN, {VT, VTVN} atau VN, {VT, VNVT}

Page 3: Grammar Regular Ahd, Ahn & Ekspresi Regular

Contoh GRAMMAR REGULAR

3. G dengan P = {S aS, S aB, B bC, C aC, C a}.

Page 4: Grammar Regular Ahd, Ahn & Ekspresi Regular

AUTOMATA HINGGA DETERMINISTIK (AHD)

Page 5: Grammar Regular Ahd, Ahn & Ekspresi Regular

Automata Hingga Nondeterministik (AHN)

Page 6: Grammar Regular Ahd, Ahn & Ekspresi Regular

AHN dengan transisi hampa

Page 7: Grammar Regular Ahd, Ahn & Ekspresi Regular

BAHASA REGULAR

Page 8: Grammar Regular Ahd, Ahn & Ekspresi Regular

EKSPRESI REGULAR

L1: a^+ karena nilai n & m lebih dari jd tidak himpunan kosongL2: a^* karena nilai 0 termasuk ke dalam nilai n&m sehinnga terdapat himpunan kosong

Page 9: Grammar Regular Ahd, Ahn & Ekspresi Regular
Page 10: Grammar Regular Ahd, Ahn & Ekspresi Regular
Page 11: Grammar Regular Ahd, Ahn & Ekspresi Regular

EKIVALENSI AHD, AHN dan GR

Page 12: Grammar Regular Ahd, Ahn & Ekspresi Regular

AHN AHD

Page 13: Grammar Regular Ahd, Ahn & Ekspresi Regular

Contoh AHN AHD

JAWAB:

Page 14: Grammar Regular Ahd, Ahn & Ekspresi Regular

AHN AHD

Page 15: Grammar Regular Ahd, Ahn & Ekspresi Regular

AHN AHD

Page 16: Grammar Regular Ahd, Ahn & Ekspresi Regular

Contoh AHN AHDBuatlah AHD yang equivalen dengan AHN berikut :

Jawab :1. S(AHN) = S(AHD) = A2. V(AHN) = V(AHD) = {0,1}3. Copykan tabel AHN

4. Simbol - dianggap sebagai elemen baru, kemudian petakan berdasarkan fungsi M(AHN).5 karena tidak ada pengulangan makan lanjutkan ke langkah berikutnya.6. Z(AHD) = Z(AHN) = {B} karena tidak ada lagi elemen baru yang mengandung elemen Z(AHN).

Page 17: Grammar Regular Ahd, Ahn & Ekspresi Regular

• dan hasilnya adalah :

Page 18: Grammar Regular Ahd, Ahn & Ekspresi Regular

AHD GR

Page 19: Grammar Regular Ahd, Ahn & Ekspresi Regular
Page 20: Grammar Regular Ahd, Ahn & Ekspresi Regular

Contoh AHD GRDiketahui AHD dengan Z={B,-}, dan fungsi transisi M seperti gambar disamping. Tentukan bentuk gramar regular dari AHD tersebut!

Jawab:M(A,0) = B A0 M(A,1) = - A1M(B,0) = B B0 M(B,1) = B B1M(- ,0) = - - 0 M(- ,1) = - - 1

GR yang dihasilkan adalah:Q= {A0, A0B, A1, A1-, B0, B1, - 0, - 1}

Stata KAHD F

Input

0 1

A B -

B B B

- - -

Page 21: Grammar Regular Ahd, Ahn & Ekspresi Regular

GR AHN

Page 22: Grammar Regular Ahd, Ahn & Ekspresi Regular
Page 23: Grammar Regular Ahd, Ahn & Ekspresi Regular

ER AHN-

Page 24: Grammar Regular Ahd, Ahn & Ekspresi Regular

ER AHN-

Page 25: Grammar Regular Ahd, Ahn & Ekspresi Regular

ER AHN-

Page 26: Grammar Regular Ahd, Ahn & Ekspresi Regular