grammar regular ahd, ahn & ekspresi regular

GRAMMAR REGULAR AHD, AHN &

EKSPRESI REGULARAdriani Yulida Kusuma

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}

Contoh GRAMMAR REGULAR

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

AUTOMATA HINGGA DETERMINISTIK (AHD)

Automata Hingga Nondeterministik (AHN)

AHN dengan transisi hampa

BAHASA 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

EKIVALENSI AHD, AHN dan GR

AHN AHD

Contoh AHN AHD

JAWAB:

AHN AHD

AHN AHD

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).

• dan hasilnya adalah :

AHD GR

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

- - -

GR AHN

ER AHN-

ER AHN-

ER AHN-