Chomsky Hiyerarşisi ( Chomsky Hierarchy )

Yazan : Şadi Evren ŞEKER

Bilgisayar bilimlerinin özellikle dil alanında yapılan çalışmalarında muntazam dilleri (formal languages) tasnif etmek için kullanılan bir yapıdır. Literatürde Chomsky–Schützenberger hiyerarşisi olarak da geçmektedir.

Bilindiği üzere ( muntazam diller (formal langauges) veya CFG yazısından da okunabileceği üzere) muntazam dillerin dört özelliği bulunur. Bunlar özellikle içerikten bağımsız dillerin (context free languages) da temelini oluşturmuştur.

• sonlular (terminals)
• devamlılar (nonterminals)
• üretim kuralları ( devamlıların değerlerini belirleyen geçiş kuralları)
• Başlangıç devamlısı

Örneğin aşağıdaki içerikten bağımsız dilbilgisini (context free grammer) ele alalım

S → AB

A → Aa | ε

B → b

Yukarıdaki bu CFG tanımındaki sonlular (terminals) {a,b,ε } ,  devamlılar (nonterminals) { S,A,B } olarak tanımlanır. üretim kuralı olarak (production rules) S,A,B’nin açılımlarını gösteren ve → sembolü ile belirtilen satırlar bulunmaktadır. Son olarak başlangıç devamlısı (nonterminal) değeri olarak S kabul edilmiştir. Başlangıç devamlısı böyle bir kural bulunmamasına karşılık genelde S harfi (start kelimesinden gelmektedir) ile gösterilmekte ve ilk satırda bulunmaktadır.

Yukarıdaki bu CFG şayet düzenli ifadeye (regular expression) çevrilirse a^*b şeklinde yazılabilir. Aslında burada anlatılan değer aⁿb şeklinde de gösterilebilen istenildiği kadar a değeri alan (hiç almaya da bilir) ve sonra mutlaka b ile biten dildir.

Chomsky yukarıdaki şekilde tanımlanan muntazam diller (formal languages) için bir sınıflandırmaya gitmiş ve 4 seviye belirlemiştir.

• Type-0 ( tip 0) Sınırlandırılmamış diller (unrestricted grammers)
• Type-1 ( tip 1) İçerik duyarlı diller (context-sensitive grammers)
• Type-2 ( tip 2) İçerikten bağımsız diller (context free languages)
• Type-3 ( tip 3) Düzenli diller (regular grammers)

şeklinde 4 seviye isimlendirilmiştir.Bu seviyelerde iler gidildikçe (seviye arttıkça) dili bağlayan kurallarda sıkılaşmakta ve dil daha kolay işlenebilir ve daha belirgin (deterministic) bir hal almaktadır.

Tip-0 dilleri bastiçe turing makinesi (turing machine) tarafından çalıştırılabilen ve bir şekilde bitecek olan dillerdir (hesaplanabilir diller (computable languages). Örneğin özyineli sayılabilir diller (recusive enumerable languages) bu seviyeden kabul edilir.

Tip-1 dilleri için içerk duyarlı diller örnek gösterilebilir. Basitçe αAβ → αγβ şeklindeki gösterime sahip bir dildir. Buradaki A devamlı (nonterminal) ve α,γ,β birer sonlu (terminal) terimdir. Bu sonlulardan α ve β boş harf (yani ε veya bazı kaynaklarda λ) olabilir ancak γ mutlak bir değere sahip olmalıdır (yani boş olamaz) Ayrıca bu tipte

S → ε

şeklinde bir kurala da izin verilmektedir. Burada S devamlısının sağ tarafta olmaması gerekmektedir. Bu diller doğrusal bağlı otomatlar (linear bounded automaton) ile gösterilebilir. Doğrusal bağlı otomatlar, turing makinelerinin özel bir halidir ve Turing makinesinde bulunan bantın sabit uzunlukta olduğu (çalışmanın sabit zaman sonra sona ereceği) kabul edilir.

Tip-2  diller ise CFG ile ifade edilebilen içerikten bağımsız dillerdir (context free languages). Bu dillerin özelliği A → γ şeklinde gösterilmeleridir. Buradaki γ değeri sonlular (terminals) ve devamlılar (nonterminals) olabilmektedir. Bu diller aşağı sürüklemeli otomatlar (push down automata PDA) tarafından kabul edilen dillerdir ve hemen hemen bütün programlama dillerinin temelini oluşturmaktadırlar. (programlama dillerinin neredeyse tamamı bu seviye kurallarına uymaktadırlar)

Tip-3 diller ise düzeli ifadeler (regular expressions) ile ifade edilebilen (veya üretilebilen veya parçalanabilen (parse) ) dillerdir. Bu dillerin farkı

A → α ve

A → αB

şeklindeki kurallar ile göterilebilmeleridir.

Yukarıdaki bu tanımları bir tabloda toplamak gerekirse:

Seviye	Dil Örneği	Otomat Uygulaması	Kuralları
Type-0	Recursively enumerable	Turing machine	α → β
Type-1	Context-sensitive	Linear-bounded non-deterministic Turing machine	αAβ → αγβ
Type-2	Context-free	Non-deterministic pushdown automaton	A → γ
Type-3	Regular	Finite state automaton	A → α ve A → αB

Yukarıdaki seviyeler bütün dilleri kapsamak için yeterli değildir ayrıca yukarıda gösterilen seviyelere giren yukarıdaki tablo dışında diller de bulunmaktadır.