Alfabet : Kumpulan dari objek-objek yang disebut dengan symbol.
Contoh : ∑ 1 = { a,b,c,….,z}
∑ 2 = {c,f}
Bahasa : Kumpulan symbol-simbol yang ditulis secara berurutan.
Tata bahasa (Grammar) : Sekumpulan dari himpunan variabel-variabel, simbol-simbol terminal, simbol non-terminal, symbol awal yang dibatasi oleh aturan-aturan produksi. Tahun 1956 -1959 Noam Chomsky melakukan penggolongan tingkatan dalam bahasa, yaitu menjadi 4 class yang disebut dengan hirarki
Chomsky. Tahun 1959 Backus memperkenalkan notasi formal baru untuk sintaks bahasa yang lebih spesifik.
Peter Nour (1960) merevisi metode dari sintaks yang sekarang dikenal dengan BNF (Backus Nour Form)
Contoh tata bahasa sederhana :
B | b|i| ; END | - A | B |…..| Z
+ | - | = ^ | * | / |
Begin
A : 1
B : A + 1
End.
Aturan Produksi
Jika (α , β ) adalah produksi, disingkat α → β dan mengacu produksi α → β dimana:
Α adalah sisi kiri produksi
B adalah sisi kanan produksi, atau hasil produksi
Simbol-simbol dalam aturan produksi dapat berupa simbol terminal maupun non terminal.
Simbol terminal sudah tidak dapat diturunkan lagi.
Simbol non-terminal dapat diturunkan lagi sampai menjadi simbol terminal.
Simbol terminal biasanya ditulis dalam huruf kecil, sedangkan simbol non-terminal biasanya ditulis dalam huruf besar.
Contoh simbol terminal : a,b,c,d,e, dan seterusnya.
Contoh simbol non-terminal : A,B,C,D,E, dan seterusnya.Tatabahasa G = {{S,A} , {a,b}, S , P } dengan aturan produksi P adalah
S → Ab
A → aAb
A → ε
maka dapat dihasilkan suatu string
S ⇒ Ab ⇒b
S ⇒ Ab ⇒ aAbb ⇒ abb
S ⇒ Ab ⇒ aAbb ⇒ aaAbbb ⇒ aaAbbb
Bahasa yang dihasilkan dari tatabahasa tersebut adalah
L(G) = { b , abb, aabbb , aaabbbb , aaaabbbbb, ... }
atau dapat pula dituliskan
L(G) = {an bn+1 | n ≥ 0 }
Materi dapat didownload disini.
atau
Tidak ada komentar:
Posting Komentar