WorksheetsQuiz 12 Teori Bahasa dan Otomata 2021-1
Total questions: 10
Worksheet time: 5mins
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
Perhatikan Gambar di atas, gambar tersebut merupakan contoh Penerapan Ekspresi Reguler untuk:
FSA menerima bilangan integer tak bertanda
FSA menerima bilangan bulat
FSA menerima bilangan integer positif
FSA menerima bilangan integer negatif
FSA menerima bilangan desimal dan alfa numerik
Manakah yang merupakan Urutan prioritas operator tertinggi dalam ekspresi regular?
Operator star (*)
Operator dot (concatenation)(.)
Concatenation bersifat asosiatif sehingga 012 dapat dikelompokkan (01)2.
Operator (+) atau (υ)/ (union) yang bersifat asosiatif.
Contoh, ekspresi 01*+1 dikelompokkan menjadi (0(1*))+1.
Operator pengurangan (-)
Operator Modulue (%)
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
•Pohon penurunan (derivation tree/parse tree) berguna untuk menggambarkan bagaimana memperoleh suatu string (untai) dengan cara menurunkan simbol-simbol terminal. Setiap simbol variabel akan diturunkan menjadi ....
terminal, sampai tidak ada yang belum tergantikan.
daun, sampai tidak ada yang belum tergantikan.
pohonl, sampai tidak ada yang belum tergantikan.
graph, sampai tidak ada yang belum tergantikan.
vertex, sampai tidak ada yang belum tergantikan.
Perhatikan gambar di atas, gambar di atas merupakan Pohon Penurunan untuk untai .....
‘aabbb’
‘aaabb’
'BABA'
‘ababa’
'AABB'
Produksi Useless :
Produksi yang memuat simbol variabel yang tidak memiliki penurunan yang akan menghasilkan terminal-terminal seluruhnya, produksi ini tidak berguna karena bila diturunkan:
tidak akan pernah selesai (masih ada simbol variabel yang tersisa)
akan selesai ( walaupun masih ada simbol variabel yang tersisa)
tidak mudahi (karena masih ada simbol variabel yang tersisa)
mudah untuk diselesaikan (walaupun masih ada simbol variabel yang tersisa)
pasti akan pernah selesai (walaupun masih ada simbol variabel yang tersisa)
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
Penghilangan Produksi Unit :
S → B => S → Aa | a
S → C => S → cCD
Sehingga menjadi :
S → a | aA | Aa | cCD
A → aB
B → Aa | a
C → cCD
D → ddd
Penghilangan Produksi ε :
A → ε dihilangkan, sehingga :
B → bA => B → b
B → ε dihilangkan, shg :
S → aB => S → aB | a
S → aaB => S → aaB | aa
Sehingga Menjadi :
S → aB | a | aaB | aa
B → b
S → aB | a | aaB | aa
B → b
S → aB | a | aaB
B → b
S → aB | a
B → b
Perhatikan Gambar di Atas:
Gambar tersebut merupakan bagan untuk:
Penyederhaan CFG
Simulasi CFG
Penambahan CFG
Pengurangan CFG
Taha-Tapap CFG
