Hirarki Chomsky

• Secara umum tata bahasa dirumuskan sebagai berikut: a -> b yang berarti a menghasilkan b atau a menurunkan b.
• Simbol variabel / non teminal adalah simbol yang masih bisa diturunkan dan ditandai dengan huruf besar seperti A, B, C, dst.
• Simbol terminal adalah simbol yang sudah tidak bisa diturunkan dan ditandai dengan huruf kecil seperti a, b, c, d, dst.

Contoh Aturan Produksi

• T -> a

        dibaca "T menghasilkan a"

• E -> T | T + E

        dibaca "E Menghasilkan T" atau

                   "E Menghasilkan T dan E"

    Simbol | menyatakan 'atau', digunakan untuk mempersingkat penulisan aturan produksi yang mempunyai ruas kiri yang sama.

Tipe 0 / Unrestricted / Natural Language

Aturan:

• Simbol pada ruas sebelah kiri harus minimal ada sebuah simbol variabel
• Tidak ada batasan pada aturan produksinya.
• Misal: Abc -> De (Diterima)

                    ABC -> b (diterima)

                    abc -> GHI (ditolak)

Tipe 1/ Conteks Sensitive

Aturan:

• Simbol pada ruas sebelah kiri harus minimal ada sebuah simbol variabel
• Panjang string pada ruas kiri  ≤ panjang string pada ruas kanan

         |a| ≤ |b|

        Misal:

        Ab -> DeF (diterima)

        CD -> eF (diterima)

        exception:S -> ε (diterima)

        ABC -> DE (ditolak)

Tipe 2 / Bebas Konteks / Context Free

Aturan:

• Simbol pada sebelah kiri harus berupa sebuah simbol variabel

            B -> CDeFG (diterima)

            D -> BcDe (diterima)

            a -> b (ditolak)

Tipe 3 / Reguler Grammer

Aturan:

• Simbol pada sebelah kiri harus berupa sebuah simbol variabel
• Simbol pada sebelah kanan maksimal hanya memiliki sebuah simbol varibel dan bila ada terletak diposisi paling kanan

    A -> e (diterima)

    A -> fgh (diterima)

    A -> eH (diterima)

    C -> D (diterima)

    A -> Bc (ditolak)