Teori Bahasa & Automata

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

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, q5, q6}

Σ  = {0,1}

S = {q0}

F = {q5}

δ = Transition Function

δ	0	1
q0	q2	q1
q1	q0	q3
q2	q3	q2
q3	q4	q5
q4	q3	q6
q5	q5	q6
q6	q5	q4

Kemudian kita akan mengetes input menggunakan aplikasi JFLAP. Berikut contoh data yang akan dimasukkan beserta hasilnya :

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:

1. huruf kecil awal alfabet, misalnya : a, b, c
2. simbol operator, misalnya : +, −, dan ×
3. simbol tanda baca, misalnya : ( ) ,, dan ;
4. string yang tercetak tebal, misalnya : if, then dan else

• Simbol-Simbol Non Terminal:

1. huruf besar awal alfabet, misal: A, B, C
2. huruf S sebagai sebagai simbol awal
3. 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 = {S -> aS | A -> bA | S -> bA | B -> aC | C -> aB | S -> bE | B -> bA | A -> aB | E -> bD | D -> λ | E -> aD | C -> bD}

Langkah selanjutnya adalah menguji dengan inputan sebagai berikut :

Sekian laporan dari saya. Terima kasih