Xem mã nguồn của Hệ thống phân cấp Chomsky

[[Tập tin:Chomsky-hierarchy.svg|thế=Tập hợp các phân loại được mô tả trong hệ thống phân cấp Chomsky.|nhỏ|Tập hợp các phân loại được mô tả trong hệ thống phân cấp Chomsky.]]
Trong các lĩnh vực lý thuyết [[ngôn ngữ hình thức]], [[khoa học máy tính]] và [[ngôn ngữ học]], '''hệ thống phân cấp Chomsky''' là một [[hệ thống phân cấp]] các lớp [[ngữ pháp hình thức]] hay văn phạm hình thức. Ngữ pháp hình thức mô tả cách tạo chuỗi từ bảng chữ cái của ngôn ngữ có giá trị theo cú pháp của ngôn ngữ đó. Nhà ngôn ngữ học [[Noam Chomsky]] đã đưa ra giả thuyết rằng có bốn lớp văn phạm hình thức khác nhau có thể sinh ra các ngôn ngữ ngày càng phức tạp hơn. Mỗi lớp cũng có thể hoàn toàn sinh ra ngôn ngữ của tất cả các lớp thấp hơn, bao gồm cả tập hợp.

== Lịch sử ==
Ý tưởng chung về một hệ thống phân cấp ngữ pháp lần đầu tiên được [[Noam Chomsky]] mô tả trong bài viết "Ba mô hình cho việc mô tả ngôn ngữ" trong quá trình chính thức hóa ngữ pháp chuyển đổi – tạo sinh (''transformational-generative grammar''''',''' TGG).{{sfn|Chomsky|1956}} Nhà toán học [[Marcel-Paul Schützenberger]] cũng đã đóng vai trò trong sự phát triển của lý thuyết ngôn ngữ hình thức; bài báo "Lý thuyết đại số của ngôn ngữ phi ngữ cảnh"{{Sfn|Chomsky|Schützenberger|1963}} mô tả hệ thống phân cấp hiện đại, bao gồm cả văn phạm phi ngữ cảnh.<ref name="Allott">{{cite book|url=https://www.researchgate.net/publication/351812216|title=A Companion to Chomsky|last1=Allott|first1=Nicholas|last2=Lohndal|first2=Terje|last3=Rey|first3=Georges|date=27 April 2021|isbn=9781119598701|pages=1–17|chapter=Synoptic Introduction|doi=10.1002/9781119598732.ch1|s2cid=241301126}}</ref>

Một cách độc lập, bên cạnh các nhà ngôn ngữ học, các nhà toán học cũng đang phát triển các mô hình tính toán (thông qua [[Automat]]). Phân tích một câu trong một ngôn ngữ tương tự như tính toán, và các văn phạm do Chomsky mô tả được chứng minh vừa giống vừa tương đương về sức mạnh tính toán với nhiều mô hình máy khác nhau.<ref>{{cite book|url=https://books.google.com/books?id=8lKyxS8_CNoC|title=Automata and computability|last=Kozen|first=Dexter C.|publisher=Springer|year=2007|isbn=978-0-387-94907-9|series=Undergraduate Texts in Computer Science|pages=3–4}}</ref>

== Hệ thống phân cấp ==
{| class="wikitable sortable"
!Văn phạm
!Ngôn ngữ
!Nhận diện automat
!Quy tắc sinh
(ràng buộc){{efn|1=Giải thích biểu tượng:
* <math>\text{a}</math> = Ký hiệu kết thúc
* <math>A</math>, <math>B</math> = Ký hiệu không kết thúc
* <math>\alpha</math>, <math>\beta</math>, <math>\gamma</math> = Chuỗi ký hiệu kết thúc và/hoặc không kết thúc}}
!Ví dụ<ref>{{cite web|url=https://www.cs.ru.nl/~herman/onderwijs/2016TnA/lecture7.pdf|title=Applications, Chomsky hierarchy, and Recap|last1=Geuvers|first1=H.|last2=Rot|first2=J.|date=2016|work=Regular Languages|archive-url=https://web.archive.org/web/20181119092124/http://www.cs.ru.nl/~herman/onderwijs/2016TnA/lecture7.pdf|archive-date=2018-11-19|url-status=live}}</ref><ref>{{cite book|title=Languages and machines: An Introduction to the Theory of Computer Science|last=Sudkamp|first=Thomas A.|date=1997|publisher=Addison Wesley Longman|isbn=978-0-201-82136-9|publication-place=Reading, Massachusetts, USA|page=310|orig-year=1988}}</ref>
|-
|Loại 3
|[[Ngôn ngữ chính quy|Chính quy]]
|[[Máy trạng thái hữu hạn]]
|<math>A \rightarrow \text{a}</math>, <math>A \rightarrow \text{a}B</math> (chính quy phải)

hoặc

<math>A \rightarrow \text{a}</math>, <math>A \rightarrow B\text{a}</math> (chính quy trái)

|<math>L = \{a^n|n > 0\}</math>
|-
|Loại 2
|[[Ngôn ngữ phi ngữ cảnh|Phi ngữ cảnh]]
|[[Máy tự động đẩy xuống]] không xác định
|<math>A \rightarrow \alpha</math>
|<math>L = \{a^nb^n|n > 0\}</math>
|-
|Loại 1
|[[Ngôn ngữ cảm ngữ cảnh|Cảm ngữ cảnh]]
|[[Máy tự động tuyến tính giới hạn|Máy Turing không xác định giới hạn tuyến tính]]
|<math>\alpha A \beta \rightarrow \alpha \gamma \beta</math>
|<math>L = \{a^nb^nc^n|n > 0\}</math>
|-
|Loại 0
|[[Ngôn ngữ ngữ cấu|Ngữ cấu]]
|[[Máy Turing]]
|<math>\gamma \rightarrow \alpha</math> (<math>\gamma</math> không được rỗng)
|<math>L = \{w|w</math> mô tả một máy Turing kết thúc<math>\}</math>
|}
{{noteslist}}Mỗi ngôn ngữ chính quy đều là ngôn ngữ phi ngữ cảnh, mỗi ngôn ngữ phi ngữ cảnh đều là ngôn ngữ cảm ngữ cảnh, mỗi ngôn ngữ cảm ngữ cảnh đều là ngôn ngữ ngữ cấu (ngôn ngữ tổng quát, ngôn ngữ không hạn chế) và mỗi ngôn ngữ ngữ cấu đều có thể đếm đệ quy. Tất cả đều là các bao hàm chính xác, có nghĩa là tồn tại các ngôn ngữ có thể đếm đệ quy mà không phải ngôn ngữ cảm ngữ cảnh, các ngôn ngữ cảm ngữ cảnh mà không phải là ngôn ngữ phi ngữ cảnh, và các ngôn ngữ phi ngữ cảnh mà không phải là ngôn ngữ chính quy.<ref>{{cite book|title=Handbook of Mathematical Psychology|last=Chomsky|first=Noam|publisher=John Wiley and Sons, Inc.|year=1963|editor1-last=Luce|editor1-first=R. Duncan|volume=II|pages=323–418|chapter=Chapter 12: Formal Properties of Grammars|editor2-last=Bush|editor2-first=Robert R.|editor3-last=Galanter|editor3-first=Eugene}}</ref>

=== Văn phạm chính quy ===
{{Xem thêm|Văn phạm chính quy}}Văn phạm <math>G = \langle \Sigma, \Delta, S, P \rangle</math> mà các quy tắc sinh của nó có dạng <math>A \rightarrow \text{a}</math>, <math>A \rightarrow \text{a}B</math> (hay tuyến tính phải, chính quy phải) hoặc <math>A \rightarrow \text{a}</math>, <math>A \rightarrow B\text{a}</math> (hay tuyến tính trái, chính quy trái), trong đó: <math>A, B \in \Delta</math> và <math>\alpha \in \Sigma</math> thì được gọi là văn phạm chính quy hoặc văn phạm loại 3.

=== Văn phạm phi ngữ cảnh ===
{{Xem thêm|Văn phạm phi ngữ cảnh}}
Văn phạm <math>G = \langle \Sigma, \Delta, S, P \rangle</math> mà các quy tắc sinh của nó có dạng <math>A \rightarrow \alpha</math>, trong đó: <math>A \in \Delta</math> và <math>\alpha \in ( \Sigma \cup \Delta ) ^ *</math> thì được gọi là văn phạm phi ngữ cảnh hoặc văn phạm loại 2.

=== Văn phạm cảm ngữ cảnh ===
{{Xem thêm|Văn phạm cảm ngữ cảnh}}
Văn phạm <math>G = \langle \Sigma, \Delta, S, P \rangle</math> mà các quy tắc sinh của nó có dạng <math>\alpha A \beta \rightarrow \alpha \gamma \beta</math>, trong đó: <math>A \in \Delta</math>; <math>\alpha, \gamma, \beta \in ( \Sigma \cup \Delta ) ^ *</math> và <math>\gamma \neq \epsilon</math> thì được gọi là văn phạm ngữ cảnh hoặc văn phạm loại 1.

=== Văn phạm ngữ cấu ===
{{Xem thêm|Văn phạm ngữ cấu}}
Văn phạm <math>G = \langle \Sigma, \Delta, S, P \rangle</math> mà các quy tắc sinh có dạng <math>\gamma \rightarrow \alpha</math>, trong đó <math>\alpha, \gamma \in ( \Sigma \cup \Delta ) ^ *</math> và <math>\gamma \neq \epsilon</math> thì được gọi là văn phạm ngữ cấu hoặc văn phạm loại 0.

== Chú thích ==

=== Tham khảo ===
{{Tham khảo|30em}}

=== Tài liệu ===
{{refbegin}}
*{{cite journal|last=Chomsky|first=Noam|author-link=Noam Chomsky|date=1956|title=Three models for the description of language|url=https://chomsky.info/wp-content/uploads/195609-.pdf|journal=IRE Transactions on Information Theory|volume=2|issue=3|pages=113–124|doi=10.1109/TIT.1956.1056813|archive-url=https://web.archive.org/web/20160307035549/https://chomsky.info/wp-content/uploads/195609-.pdf|archive-date=2016-03-07|s2cid=19519474|url-status=live}}
*{{cite journal|last=Chomsky|first=Noam|author-link=Noam Chomsky|date=1959|title=On certain formal properties of grammars|url=https://www.sciencedirect.com/science/article/pii/S0019995859903626/pdf?md5=9d466f851651bd592afa5ee561b7a0b0&pid=1-s2.0-S0019995859903626-main.pdf|journal=Information and Control|volume=2|issue=2|pages=137–167|doi=10.1016/S0019-9958(59)90362-6|via=|doi-access=free}}
*{{cite book|url=http://www-igm.univ-mlv.fr/~berstel/Mps/Travaux/A/1963-7ChomskyAlgebraic.pdf|title=Computer Programming and Formal Systems|last1=Chomsky|first1=Noam|last2=Schützenberger|first2=Marcel P.|date=1963|publisher=North Holland|isbn=|editor1-last=Braffort|editor1-first=P.|location=Amsterdam|pages=118–161|chapter=The algebraic theory of context free languages|author-link1=Noam Chomsky|editor2-last=Hirschberg|editor2-first=D.|archive-url=https://web.archive.org/web/20110613164145/http://www-igm.univ-mlv.fr/~berstel/Mps/Travaux/A/1963-7ChomskyAlgebraic.pdf|archive-date=2011-06-13|url-status=live}}
{{refend}}{{Sơ khai}}

[[Thể loại:Noam Chomsky]]
[[Thể loại:Ngôn ngữ học]]
[[Thể loại:Thuật ngữ ngôn ngữ học]]