02-teori-bahasa.pptx
DESCRIPTION
aaaaaaaaaaaaaaaTRANSCRIPT
Bahasa
Alfabet
Tata Bahasa
Semantik
Himpunan terhingga dari token-token
Himpunan aturan yang
berlaku
Himpunan aturan yang didefinisikan
Token, Alfabet, dan String
Himpunan terhingga dari token-token
Deretan elemen yang berasal dari anggota alfabet
Huruf, angka, simbol
Panjang String
• Panjang string : banyaknya token yang membentuk string.
• Dinotasikan dengan cardinal number.
• Contoh : string “otomata” memiliki panjang string 7.
Bahasa & Tata Bahasa
• Terminal dan Nonterminal
• Aturan Produksi
• Kelas – kelas Tata Bahasa
• Bentuk Sentenensial dan Jenis Bahasa
Terminal & Nonterminal
• Terminal : setiap anggota dari alfabet.
• Nonterminal : himpunan string yang bukan elemen alfabet.
Aturan Produksi &Tata Bahasa
Bentuk umum :
x y
• x, y = string dalam himpunan terminal dan nonterminal
• x ≠
2 Sifat Penting Tata Bahasa
1. Simbol Terminal dan Simbol Nonterminal adalah disjoint .
2. Setiap aturan produksi harus memuat paling sedikit satu simbol nonterminal pada anggota bagian kiri.
Tata Bahasa terdiri dari 4 Tupel
G = (N, , P, S)
• N : himpunan simbol nonterminal
• : himpunan simbol terminal (alfabet)
• P : himpunan aturan produksi
• S : simbol awal anggota dari N
Kelas Tata Bahasa
Kelas Grammar Language Otomaton
Tipe-0 UnrestrictedTuring-
recognizable
Turing Machine
(TM)
Tipe-1Context-
sensitive
Context-
sensitive
Linear-bounded
(LBA)
Tipe-2 Context-Free Context Free Pushdown
Tipe-3 Regular Regular Finite
Langkah Penurunan
• Aturan produksi x → y
• Pada string wxz,
langkah penurunan wxz wyz
• Satu atau lebih langkah penurunan diberi simbol +
Ketentuan Penurunan
1. Penurunan memerlukan simbol nonterminal awal.
2. Penurunan dapat berhenti ketika tercapai suatu string yang hanya memuat simbol terminal
Grammar dan Bahasa
Diberikan suatu grammar:
G = {N, , P, S}
Maka Language dari grammar tersebut:
L(G) = {x | x *, dan S +x}
Context-Sensitive Grammar
Aturan produksi:
x → y
Dengan x, y (N )*
Syarat:
1. x memuat paling sedikit satu anggota N.
2. |x| ≤ |y| artinya y tidak boleh empty.
Contoh Context-Sensitive Grammar
G1 = ({S, B, C}, {a, b, c}, P, S)
P :
1. S → aSBC
2. S → abC
3. CB → BC
4. bB → bb
5. bC → bc
6. cC → cc
string yang dihasilkan oleh grammar :
aabbcc
Context-Free Grammar
Aturan produksi:
X → y
Dengan x N, y (N )* :: y dapat berupa empty (himpunan kosong).
Setiap CFG dengan aturan produksi x → bukan merupakan Context-Sensitive
Grammar
Contoh CFG
G2 = ({E, T, F}, {+, *, (, ), d}, P, E)
P :
1. E → E + T
2. E → T
3. T → T*F
4. T → F
5. F → (E)
6. F → d
string yang dihasilkan oleh grammar :
d + d
Contoh Regular Grammar
Aturan Produksi :
1. S → dB
2. S → +A
3. S → -A
4. S → G
5. A → dB
6. A → G
7. B → dB
8. B → H
9. B → d
10. G → dH
11. H → dH
12. H → d
string yang dihasilkan oleh grammar : ddddd
Penggabungan Bahasa(Concatenating Language)
Operasi penggabungan string (concatenation) dapat digunakan untuk
menggabungkan dua bahasa.
Definisi – 1
• Concatenation dua bahasa A dan B,
yang dinotasikan dengan AB, adalah
bahasa yang terdiri dari semua string
dalam bentuk ab,
• dengan a A, dan b b
Definisi – 2
• Union (gabungan) dua bahasa A dan
B, yang dinotasikan dengan A B,
adalah bahasa yang terdiri dari semua
anggota A atau anggota B.