Mesin Pengenal Bahasa
Untuk setiap kelas bahasa Chomsky, terdapat sebuah mesin pengenal bahasa. Masing-masing mesin tersebut adalah :
Kelas Bahasa Mesin Pengenal Bahasa
Unrestricted Grammar (UG) Mesin Turing (Turing Machine), TM
Context Sensitive Grammar (CSG) Linear Bounded Automata, LBA
Context Free Gammar (CFG) Pushdown Automata, PDA
Regular Grammar, RG Finite State Automata, FSA
Untuk setiap kelas bahasa Chomsky, terdapat sebuah mesin pengenal bahasa. Masing-masing mesin tersebut adalah :
Kelas Bahasa | Mesin Pengenal Bahasa |
Unrestricted Grammar (UG) | Mesin Turing (Turing Machine), TM |
Context Sensitive Grammar (CSG) | Linear Bounded Automata, LBA |
Context Free Gammar (CFG) | Pushdown Automata, PDA |
Regular Grammar, RG | Finite State Automata, FSA |
Finite State Automata (FSA)
Finite State Automata dinyatakan oleh pasangan 5 tuple, yaitu :
M=(Q , Σ , δ , S , F )
Q = himpunan state
Σ = himpunan simbol input
δ = fungsi transisi δ : Q × Σ
S = state awal / initial state , S ∈ Q
F = state akhir, F ⊆ Q
Contoh diagram transisinya :
Definisi :
M = (Q , Σ , δ , S , F)
Q = {q0, q1, q2, q3, q4}
Σ = {0,1}
S = {q0}
F = {q4}
δ = Transition Function
Finite State Automata dinyatakan oleh pasangan 5 tuple, yaitu :
M=(Q , Σ , δ , S , F )
Q = himpunan state
Σ = himpunan simbol input
δ = fungsi transisi δ : Q × Σ
S = state awal / initial state , S ∈ Q
F = state akhir, F ⊆ Q
Contoh diagram transisinya :
Definisi :
M = (Q , Σ , δ , S , F)
Q = {q0, q1, q2, q3, q4}
Q = {q0, q1, q2, q3, q4}
Σ = {0,1}
S = {q0}
F = {q4}
δ = Transition Function
GRAMMAR DAN BAHASA
Penjelasan umum :
Dalam pembicaraan tata bahasa, anggota alfabet dinamakan simbol terminal atau token. Kalimat adalah deretan hingga simbo-simbol terminal. Bahasa adalah himpunan kalimat-kalimat. Anggota bahasa bisa tak hingga kalimat.
- Simbol-Simbol Terminal:
- huruf kecil awal alfabet, misalnya : a, b, c
- simbol operator, misalnya : +, −, dan ×
- simbol tanda baca, misalnya : ( ) ,, dan ;
- string yang tercetak tebal, misalnya : if, then dan else
- Simbol-Simbol Non Terminal:
- huruf besar awal alfabet, misal: A, B, C
- huruf S sebagai sebagai simbol awal
- String yang tercetak miring, misalnya : expr dan stmt,
Finite State Automata Tata Bahasa (grammer) didefinisikan dengan empat tupel
G = (V, T, P, S) dimana :
V = Himpunan simbol variabel / non terminal
T = Himpunan simbol terminal
P = Kumpulan aturan produksi
S = Simbol awal
Berikut contoh diagramnya :
Definisi :
V = {S,A,B,C,D,E}
T = {a,b}
S = {S}
P =
Langkah selanjutnya adalah menguji dengan inputan sebagai berikut :
Sekian dan terima kasih.
Penjelasan umum :
Dalam pembicaraan tata bahasa, anggota alfabet dinamakan simbol terminal atau token. Kalimat adalah deretan hingga simbo-simbol terminal. Bahasa adalah himpunan kalimat-kalimat. Anggota bahasa bisa tak hingga kalimat.
- Simbol-Simbol Terminal:
- huruf kecil awal alfabet, misalnya : a, b, c
- simbol operator, misalnya : +, −, dan ×
- simbol tanda baca, misalnya : ( ) ,, dan ;
- string yang tercetak tebal, misalnya : if, then dan else
- Simbol-Simbol Non Terminal:
- huruf besar awal alfabet, misal: A, B, C
- huruf S sebagai sebagai simbol awal
- String yang tercetak miring, misalnya : expr dan stmt,
Finite State Automata Tata Bahasa (grammer) didefinisikan dengan empat tupel
G = (V, T, P, S) dimana :
V = Himpunan simbol variabel / non terminal
T = Himpunan simbol terminal
P = Kumpulan aturan produksi
S = Simbol awal
Berikut contoh diagramnya :
Definisi :
V = {S,A,B,C,D,E}
V = {S,A,B,C,D,E}
T = {a,b}
S = {S}
P =
Langkah selanjutnya adalah menguji dengan inputan sebagai berikut :
Sekian dan terima kasih.