Apa itu bahasa dan bagaimana bahasa itu dapat didefinisikan? Pada level analisis sintaks, bahasa adalah kalimat yang dibuat dan dapat digunakan untuk berkomunikasi. Meskipun demikian, tidak semua urutan kata-kata dapat dikategorikan sebagai kalimat. Sebagai contoh, perhatikan kalimat–kalimat berikut ini, ada beberapa kalimat yang gramatikal dan ada yang tidak.
a. Fahmi berhasil mencapai puncak pohon itu.
b. Dalam beberapa hari terakhir, hujan mengguyur Kota Bandung tanpa henti.
c. Fahmi mencapai berhasil puncak pohon itu.
d. Dalam hari terakhir beberapa, hujan Kota Bandung mengguyur tanpa henti.
Dari contoh-contoh kalimat di atas, jelas sekali bahwa kalimat a dan b termasuk kalimat yang gramatikal, sedangkan dua kalimat lainnya, yaitu kalimat c dan d tidak termasuk kalimat yang gramatikal.
Suatu kalimat dikatakan gramatikal atau tidak tentu saja tidak dapat hanya dilakukan dengan sense, tapi tentu saja ada aturan-aturan yang berlaku untuk menentukannya. Pendekatan Chomsky untuk masalah ini dengan menggeser dari penekanan pada bahasa yang untuk semua tujuan praktis kepada penekanan pada tata bahasa atau aturan yang dapat menghasilkan bahasa.
Contoh :
Asumsikan bahwa kosa kata dibatasi sepasang huruf {a, b}. Kalimat-kalimat yang dapat dibentuk dari sepasang huruf ini antaranya adalah :
abba, abaaba, baabaabaab dan lain-lain.
Aturan untuk membentuk deretan huruf tersebut adalah :
S -> aa S -> aSa
S -> bb S -> bSb
Bagaimana aturan-aturan ini digunakan dalam membentuk sebuah kalimat? Langkah pertama tulislah S yang digunakan sebagai symbol inisiasi. Kemudian ganti S dengan salah satu dari 4 alternatif perluasan, misalnya S => aSa. Jika bentuk baru masih mengandung S, ganti kembali dengan salah satu dari 4 alternatif perluasan sampai tidak dapat diperluas lagi, atau dengan kata lain tidak mengandung S lagi.
Salah satu contoh urutan turunan sebuah kalimat berdasarkan aturan di atas adalah :
(1) S
(2) bSb
(3) baSab
(4) baaSaab
(5) baabSbaab
(6) baabaabaab
Langkah selanjutnya, kita akan memformalisasikan sebuah tata bahasa dan kemudian menjelaskan bagaimana pengetahuan dapat digunakan dalam mendefinisikan sebuah bahasa.
Definisi :
Sebuah grammer, G, dapat didefinisikan dalam bentuk sebuah himpunan yang terdiri dari 4 elemen (quadruple), dimana setiap elemen bersifat terbatas. G = (N, V, P, S0), dimana :
a. N adalah sebuah himpunan nonterminal
b. V adalah sebuah himpunan simbol terminal yang digunakan untuk mendefinisikan kalimat sebenarnya
c. P adalah himpunan aturan gramatikal, dan
d. S0 adalah nonterminal tunggal yang digunakan sebagai simbol inisiasi.
Sebagai contoh :
N = {S}
V = {a,b}
P = {S -> aa, S -> aSa, S -> bb, S -> bSb}
S0 = S
Himpunan N dan V tidak boleh overlap, dimana anggota-anggota himpunannya tidak boleh sama atau dengan kata lain : N U V = Q, dimana Q merupakan sebuah himpunan kosong.
Nonterminal dapat ditulis ulang atau diganti dan dapat muncul di sisi kiri maupun sisi kanan aturan, sedangkan terminal tidak dapat ditulis ulang atau diganti dan hanya dapat muncul di sisi kanan aturan.
Kumpulan aturan yang berhubungan dengan sebuah nonterminal dapat digabungkan penulisannya, misalnya ada sekumpulan aturan : X -> a1, X -> a2, dan X -> a3, dapat dituliskan sebagai : X -> a1 | a2 | a3.
Atau secara umum dapat ditulis dengan bentuk : X -> a1 | a2 | ... | an.
