Alfabet: himpunan terbatas dari sejumlah simbol
Contoh: alfabet latin , {a, b, c, …, z}
alfabet Yunani, {α, β, γ, …, ω}
alfabet biner, {0, 1}
alfabet Hyrogliph, {𓆲, 𓀀 𓀁 𓀂 𓀃 𓀄 𓀅 𓀆 𓀇 𓀈 𓀉 𓀊 𓀋 𓀌 … }
Hanacaraka {ꦲ, ꦤ, ꦕ, ꦫ, ꦏ, …}
String: barisan yang disusun oleh simbol-simbol alfabet.
a1a2a3…an, ai ∈ A ( A adalah alfabet)
Nama lain untuk string adalah kalimat atau word
Jika A adalah alfabet, maka An menyatakan himpunan semua
string dengan panjang n yang dibentuk dari himpunan A.
A adalah himpunan semua rangkaian simbol dari himpunan A
yang terdiri dari 0 simbol (string kosong), satu simbol, dua
simbol, dst.
A = A0 ∪ A1 ∪ A A* = A ∪ A ∪ A2 ∪ …
Contoh: Misalkan A = {0, 1}, maka
A0 = {ε}
A1 = {0, 1}
A2 = {11, 01, 10, 11}
A3 = {000, 001, 010, 011, 100, 101, 110, 111}
Bahasa (pada alfabet A) adalah himpunan bagian dari A*.
Contoh: Misalkan A = {a, b, c}, maka berikut ini adalah
contoh-contoh bahasa pada alfabet A:
L1 = {a, aaa, bc, ac, abc, cab}
L2 = {aba, aabaa}
L3 = {ε}
L4 = {aicbi | i ≥ 1}
Tata bahasa (grammar) adalah aturan yang digunakan
untuk membangkitkan atau mengenali kalimat di dalam
suatu bahasa.
Contoh tata bahasa Inggris:
→
→
→
→
→
→
→ the
→ a
→ little
→ boy
→ dog
→ runs
→ bites
→ quickly
—-
Contoh tata bahasa Inggris:
→
→
→
→
→
→
→ the
→ a
→ little
→ boy
→ dog
→ runs
→ bites
→ quickly
—-
Contoh pembangkitan kalimat:
→
→
→the
→ the < verb phrase>
→ the little < verb phrase>
→ the little boy < verb phrase>
→ the little boy
→ the little boy runs
→ the little boy runs quickly
—-
Unsur-unsur tata bahasa:
1. Himpunan berhingga terminal, T
2. Himpunan berhingga non terminal, N
3. Himpunan berhingga aturan produksi, P
4. Simbol awal, S ∈ N
Dilambangkan dengan G = (T, N, P, S)
Contoh: tata bahasa G = (T, N, P, S), dengan T = {a, b}, N = {S, A, B},
P = {S→ABa, A → BB, B →ab, AB → b}. Simbol awal adalah S.
String abababa diturunkan sebagai berikut:
S ⇒ ABa
⇒ Aaba
⇒ BBaba
⇒ Bababa
⇒ abababa
—-
Kelas tata bahasa dan kelas bahasa
Noam Chomsky menklasifikasikan tata bahasa ke dalam
beberapa kelas:
1. Kelas tata bahasa regular (regular grammar) atau tata
bahasa tipe 3.
Aturan produksinya berbentuk:
A → a
A → aB (atau A → Ba)
Bahasanya dinamakan bahasa regular (regular language)
Mesin yang mengenalinya adalah Finite State Automaton (FSA)
—-
Bahasa bebas konteks (context-free grammar) atau tata
bahasa tipe 2.
Aturan produksinya berbentuk:
A → α
α adalah string yang dibentuk dari simbol terminal dan/atau simbol non terminal.
Bahasanya dinamakan bahasa bebas-konteks (context-free language) atau CFL.
Mesin yang mengenali bahasanya dinamakan Push Down Automaton (PDA).
Tata bahasa tipe 3 termasuk di dalam tata bahasa tipe 2.
—-
Kelas tata bahasa peka-konteks (context-sensitive) atau tata
bahasa tipe 1.
Aturan produksinya berbentuk:
α → β
Panjang β selalu lebih besar atau sama dengan panjang α.
Bahasanya Bahasanya dinamakan dinamakan bahasa peka-konteks konteks (context context- sensitive language) atau CSL.
Mesin yang mengenali bahasanya dinamakan Linear Bounded
Automaton (LBA)
Tata bahasa tipe 3 dan tipe 2 termasuk di dalam tata bahasa
tipe 1
—-
Tata bahasa tanpa pembatasan (unrestricted grammar) atau
tata abhasa tipe 0.
Aturan produksinya tidak mempunya batasan, seperti pada
tata bahasa tipe 3, 2, dam 1.
Bahasa yang dispesifikasikan dispesifikasikan oleh tata bahasa ini disebut disebut
bahasa tanpa-pembatasan (unrestricted language).
Mesin yang mengenali bahasa ini adalah Mesin Turing
(TuringMachine)
—-
Tipe Kelas Tata Bahasa Mesin Pengenal Bahasa
3 Regular Grammar Finite State Automaton (FSA)
2 Context-Free Grammar (CFG) Push Down Automaton (PDA)
1 Context-Sensitive Grammar (CSG) Linear Bounded Automaton
0 Unrestricted Grammar Turing Machine