Chomsky hiyerarşisi

Biçimsel dil kuramı, bilgisayar bilimi ve dilbilimde Chomsky hiyerarşisi, biçimsel diller arasındaki ast-üst ilişkisini tanımlar. Biçimsel dilbilgisi (gramer) bir dilin alfabesinden seçilmiş harflerden oluşan sözcüklerin veya sözcükler seçilerek oluşturulmuş cümlelerin, dilin sözdizimine göre doğru olup olmadığını belirler. Dilbilimci Noam Chomsky, artan karmaşıklıkta 4 farklı biçimsel dilbilgisi sınıfının bulunduğunu kuramsal olarak açıklamıştır. Buna göre üst sınıflar, alt sınıfların özelliklerini taşıyan cümleler oluşturabilir.

Hiyerarşi

Aşağıdaki tablo, Chomsky'nin dört dilbilgisi türünün her birini, ürettiği dil sınıfını, onu tanıyan otomat türünü ve kurallarının sahip olması gereken biçimi özetlemektedir. Sınıflar, üretim kurallarına getirilen kısıtlamalarla tanımlanır.

Dilbilgisi	Diller	Tanıyan otomat	Üretim kuralları (kısıtlamalar)^[a]	Örnekler^[1]^[2]
Tip-3	Düzenli	Sonlu durum makinesi	$A\rightarrow {\text{a}}$ $A\rightarrow {\text{a}}B$ (sağdan düzenli) veya $A\rightarrow {\text{a}}$ $A\rightarrow B{\text{a}}$ (soldan düzenli)	$L=\{a^{n}\mid n>0\}$
Tip-2	Bağlamdan bağımsız	Belirlenimsiz yığıtlı otomat	$A\rightarrow \alpha$	$L=\{a^{n}b^{n}\mid n>0\}$
Tip-1	Bağlama duyarlı	Doğrusal sınırlı belirlenimsiz Turing makinesi	$\alpha A\beta \rightarrow \alpha \gamma \beta$	$L=\{a^{n}b^{n}c^{n}\mid n>0\}$
Tip-0	Özyinelemeli sayılabilir	Turing makinesi	$\gamma \rightarrow \alpha$ ( $\gamma$ boş olamaz)	$L=\{w\mid w$ sonlanan bir Turing makinesini tanımlar $\}$

↑
Sembollerin anlamı:
- ${\text{a}}$ = terminal
- $A$ , $B$ = terminal olmayan
- $\alpha$ , $\beta$ , $\gamma$ = terminallerden ve/veya terminal olmayanlardan oluşan dize

Kaynakça

↑ Geuvers, H.; Rot, J. (2016). "Applications, Chomsky hierarchy, and Recap" (PDF). Regular Languages. 19 Kasım 2018 tarihinde kaynağından arşivlendi (PDF).
↑ Sudkamp, Thomas A. (1997) [1988]. Languages and machines: An Introduction to the Theory of Computer Science. Reading, Massachusetts, USA: Addison Wesley Longman. s. 310. ISBN 978-0-201-82136-9.

Chomsky, Noam (1956). "Three models for the description of language" (PDF). IRE Transactions on Information Theory. 2 (3). ss. 113-124. doi:10.1109/TIT.1956.1056813. 7 Mart 2016 tarihinde kaynağından arşivlendi (PDF).

Chomsky, Noam (1959). "On certain formal properties of grammars" (PDF). Information and Control. 2 (2). ss. 137-167. doi:10.1016/S0019-9958(59)90362-6 .

Chomsky, Noam; Schützenberger, Marcel P. (1963). "The algebraic theory of context free languages". Braffort, P.; Hirschberg, D. (Ed.). Computer Programming and Formal Systems (PDF). Amsterdam: North Holland. ss. 118-161. 13 Haziran 2011 tarihinde kaynağından arşivlendi (PDF).

[1] Sembollerin anlamı:
${\text{a}}$ = terminal

$A$ , $B$ = terminal olmayan

$\alpha$ , $\beta$ , $\gamma$ = terminallerden ve/veya terminal olmayanlardan oluşan dize

[mwZw] ${\text{a}}$ = terminal

[mwcw] $A$ , $B$ = terminal olmayan

[mwhw] $\alpha$ , $\beta$ , $\gamma$ = terminallerden ve/veya terminal olmayanlardan oluşan dize

[2] Geuvers, H.; Rot, J. (2016). "Applications, Chomsky hierarchy, and Recap" (PDF). Regular Languages. 19 Kasım 2018 tarihinde kaynağından arşivlendi (PDF).

[3] Sudkamp, Thomas A. (1997) [1988]. Languages and machines: An Introduction to the Theory of Computer Science. Reading, Massachusetts, USA: Addison Wesley Longman. s. 310. ISBN 978-0-201-82136-9.

[a]

[1]

[2]