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