Tata bahasa (grammer) bisa didefinisikan secara formal sebagai kumpulan dari himpunan-himpunan variable, simbol-simbol terminal, simbol awal, yang dibatasi oleh aturan-aturan produksi.
Pada tahun 1959 seorang ahli bernama Noam Chomsky melakukan penggolongan tingkatan bahasa menjadi empat, yang disebut dengan Hirarki Chomsky. Penggolongan tersebut bisa dilihat pada table berikut :
1. Regular/Tipe 3
Finitie State Automata (FSA) meliput Deterministic finite Automata (DFA) & Non-deterministic Finite Automata (NFA). α adalah simbol variable, β maksimal memiliki sebuah simbol variable yang bila ada terletak posisi paling kanan.
2. Bebas Konteks/Context Free/Tipe 2
Push Down Automata (PDA). α berupa simbol variable
3. Context Sensitive/Tipe 1
Linier Bounded Automata |α| <_ |β|
4. Unrestricted/Phase Structure/Natural Language/Tipe 0
Mesin Turing, tidak ada batasan
Kita bisa melihat penggolongan diatas berdasarkan pembatasan yang dilakukan pada aturan produksinya. Aturan produksi merupakan pusat dari tata bahasa, yang menspesifikasikan bagaimana suatu tata bahasa melakukan transpormasi suatu string ke bentuk lainnya, dan melalui aturan produksi tersebut didefinisikan suatu bahasa yang berhubungan dengan tata bahasa tersebut. Disini semua aturan produksi dinyatakan dalam bentuk "α->β" (bisa dibaca: α menghasilkan β, atau dibaca α menurunkan β), dimana α menyatakan simbol-simbol pada ruas kiri aturan produksi (sebelah kiri tanda '->') dan β menyatakan simbol-simbol pada ruas kanan aturan produksi (sebelah kanan tanda '->', dan bisa disebut juga sebagai hasil produksi). Simbol-simbol tersebut bisa berupa simbol terminal atau simbol nonterminal/variable. Simbol variable/nonterminal adalah simbol yang masih diturunkan, sedangkan simbol terminal sudah tidak bisa diturunkan lagi. Simbol terminal biasanya dinyatakan dengan huruf kecil, misal 'a','b','c'. Simbol nonterminal/variable biasanya dinyatakan huruf besar, 'A','B','C'.
