Quiz 6 Teori Bahasa Otomata 2023-1 Ekspresi Reguler

Tata Bahasa Regular (FSA) bisa kita konstruksikan dengan :

• Ekspresi Regular dan Aturan Produksi

• Pohon Penurunan

• Graph berarah

• Graph tak berarah

• Matrik

Sebuah otomata berhingga menspesifikasikan sebuah bahasa sebagai himpunan semua untai yang menggerakkannya dari state awal ke

• salah satu dari state yang diterimanya (himpunan state akhir).

• state awal

• proses awal

• proses tengah

• proses akhir

Dalam batasan Aturan Produksi untuk Bahasa Regular:

α→β (dibaca α menghasilkan β)

α adalah sebuah simbol variabel.

β maksimal memiliki sebuah simbol variabel yang terletak di

• paling kanan bila ada.

• di awal

• di tengah

• di konsep bahasa

• di model bahasa

Dalam batasan Aturan Produksi untuk Bahasa Regular (lanjutan):

•α atau β bisa berupa simbol terminal atau non-terminal/variabel.

•Simbol variabel/non-terminal adalah simbol yang masih bisa diturunkan. Biasanya dinyatakan dengan:

• huruf besar, misal: A, B, C.

• huruf kecil, misal: a, b, c.

• gabungan huruf besar dan kecil

• angka desimal

• simbol abjad yunani seperti: α atau β

Dalam batasan Aturan Produksi untuk Bahasa Regular (lanjutan):

•Simbol terminal sudah tidak bisa diturunkan lagi. Simbol terminal biasanya dinyatakan dengan

• huruf kecil. Misal: a, b, c.

• huruf Besar Misal: A, B, C.

• huruf gabungan. Misal: a, B, c.

• Simbol huruf yunani seperti: α atau β

•Suatu tata bahasa (grammar) didefinisikan dengan 4 tupel (G={V, T, P, S}) dimana:

→V=

• himpunan simbol variabel/non terminal.

• himpunan simbol terminal.

• kumpulan aturan produksi

• simbol awal

• konstanra

Dalam mengkontruksi aturan produksi tata bahasa regular dari suatu finite state automata, perlu kita ingat yang menjadi perhatian kita adalah state-state yang bisa menuju ke

• state akhir.

• state awal

• state tengah

• state baru

• state random

•Misalnya kita tentukan simbol awal adalah S, kita identikan simbol S dengan state awal q₀. dari q₀ mendapat input a menjadi q₁.

•E Kita identikkan dengan q₁

•Bisa kita tuliskan sebagai aturan produksi:

• S→aE

• S→AE

• S→ae

• S→q1q2

• S→q2q1

Perhatikan gambar di atas:

•Bisa kita lihat hasil pada gambar tersebut akan berkorelasi S dengan q₀, B dengan q₁, dan C dengan q₂.

•Kita lihat S→b, maka kita buat state akhir adalah:

• q₃.

• q1.

• q2.

• q0

• q2 dan q3

•Jika kita identikan q₂ sebagai A dan q₃ sebagai B.

–dari q₂ mendapat input a tetap ke q₂,

–dari q₃ mendapat input b tetap ke q₃, bisa kita tuliskan:

• A → aA

  B → bB

• A → AA

  B → BB

• A → aa

  B → bb

• A → aA1

  B → bB2

• A → aA2

  B → bB1