Biçimsel Dil Kuramı
 

Biçimsel dil kuramı, teorik bilişimin temel dallarından biridir. Bir biçimsel dil, abece denilen belli bir küme Σ üzerinde kurulan katarlardan oluşur. Biçimsel dilleri tanımlamak için ifadeler, gramerler, ya da tanımlanan dile ait olan katarları kabul eden otomatlar kullanılır. Bunun yüzünden otomat kuramı ile ilişkisi çok önemlidir.
Biçimsel diller, Chomsky sınıflandırmasına göre 4 sınıfa ayırılır:

Tip 3 Düzenli diller
Tip 2 Bağlamdan bağımsız diller
Tip 1 Bağlama duyarlı diller
Tip 0 Özyinelemeli sayılabilir diller

Her sınıf, daha küçük sayılı sınıfların bir alt kümesidir. Tip 0 en genel sınıftır, Turing makina ve bilgisayar programıyla sayılanan her dilli kapsar.
Bu sınıflandırma (hiyerarşi), dillerin katarlarını türetten gramer ya da kabul eden makinaların hesaplama gücüne göre yapılmıştır.

Kaynak : Wikipedia