Sebuah otomata berhingga menspesifikasikan sebuah bahasa sebagai himpunan semua untai yang menggerakkannya dari state awal ke

Dalam batasan Aturan Produksi untuk Bahasa Regular:

α→β (dibaca α menghasilkan β)

α adalah sebuah simbol variabel.

β maksimal memiliki sebuah simbol variabel yang terletak di

Dalam batasan Aturan Produksi untuk Bahasa Regular (lanjutan):

•α atau β bisa berupa simbol terminal atau non-terminal/variabel.

•Simbol variabel/non-terminal adalah simbol yang masih bisa diturunkan. Biasanya dinyatakan dengan:

Dalam batasan Aturan Produksi untuk Bahasa Regular (lanjutan):

•Simbol terminal sudah tidak bisa diturunkan lagi. Simbol terminal biasanya dinyatakan dengan

•Suatu tata bahasa (grammar) didefinisikan dengan 4 tupel (G={V, T, P, S}) dimana:

→V=

Dalam mengkontruksi aturan produksi tata bahasa regular dari suatu finite state automata, perlu kita ingat yang menjadi perhatian kita adalah state-state yang bisa menuju ke

•Misalnya kita tentukan simbol awal adalah S, kita identikan simbol S dengan state awal q₀. dari q₀ mendapat input a menjadi q₁.

•E Kita identikkan dengan q₁

•Bisa kita tuliskan sebagai aturan produksi:

Perhatikan gambar di atas:

•Bisa kita lihat hasil pada gambar tersebut akan berkorelasi S dengan q₀, B dengan q₁, dan C dengan q₂.

•Kita lihat S→b, maka kita buat state akhir adalah:

•Jika kita identikan q₂ sebagai A dan q₃ sebagai B.

–dari q₂ mendapat input a tetap ke q₂,

–dari q₃ mendapat input b tetap ke q₃, bisa kita tuliskan: