NEW
Font size
WorksheetsTugas TBO
Total questions: 11
Worksheet time: 6mins
Dalam Penerapan Ekspresi Reguler: Sebuah bahasa dinyatakan regular jika:.......
terdapat finite state automata (FSA) yang dapat menerimanya
tidak terdapat finite state automata (FSA) yang dapat menerimanya
sebagian terdapat finite state automata (FSA) yang dapat menerimanya
terdapat finite state automata (FSA) yang tidak dapat menerimanya
finite state automata (FSA) yang dapat menerimanya dapat digunakan secara umum
Manakah berikut ini yang bukan merupakan penulisan Notasi Ekspresi Reguler?
(*) yaitu karakter asterisk, berarti bisa tidak muncul, bisa juga muncul berhingga kali (0-n).
(˖) pada posisi superscript / diatas berarti minimal muncul satu kali (1-n).
(+) atau (ᴗ) berarti union/atau.
(.) titik, berarti konkatenasi. Biasanya titik bisa dihilangkan. Misalnya: ab bermakna sama seperti a.b.
(%) Prosen, berarti berarti pembagian modulus. Misalnya 5%2 bermakna 5 dibagi dengan 2 hasilnya 2 dengan sisa hasil pembagian 1
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 β
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 berikut:
Bisa dilihat hasil pada gambar tersebut akan berkorelasi S dengan q₀, B dengan q₁, dan C dengan q₂.
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
Dalam Hirarki Chomsky Bahasa Reguler/Type 3 mesin Otomata : Finite State Otomata (FSA) memiliki batasan aturan produksi:
ß memiliki maksimal sebuah simbol variabel yang bisa ada terletak di posisi paling kanan
α memiliki maksimal sebuah simbol variabel yang bisa ada terletak di posisi paling kanan
ß memiliki maksimal sebuah simbol variabel yang bisa ada terletak di posisi paling kiri
α memiliki maksimal sebuah simbol variabel yang bisa ada terletak di posisi paling kiri
Tidak ada batasan
Untuk Produksi:
S → AB
A → abB | aCa | ε
B → bA | BB | ε
C → ε
Variabel yang nullable A, B, C. Dari S → AB, maka S juga
nullable. Kita lakukan penggantian :
A → aCa => A → aa
B → bA => B → bA | b
B → BB => B → BB | B
A → abB => A → abB | ab
S → AB => S → AB | A | B | ε
C → ε, B → ε, A → ε dihapus
Perhatikan : untuk penggantian S → AB kita tetap mempertahankan produksi S → ε, karena S merupakan .....
simbol awal
simbol akhir
simbol terminal
tidak bisa diproduksi lagi
terlalu rumit
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
S→ AB | a
A → a
Aturan S→ AB tidak berarti karena B
tidak memiliki penurunan
memiliki penurunan
tidak bisa diremehkan
tidak memiliki induk
tidak seimbang
