Chomsky Phân loại ngữ pháp

Theo Noam Chomosky, có bốn loại ngữ pháp - Loại 0, Loại 1, Loại 2 và Loại 3. Bảng sau đây cho thấy chúng khác nhau như thế nào -

Loại ngữ pháp	Ngữ pháp được chấp nhận	Ngôn ngữ được chấp nhận	Automaton
Loại 0	Ngữ pháp không hạn chế	Ngôn ngữ liệt kê đệ quy	Máy turing
Loại 1	Ngữ pháp nhạy cảm theo ngữ cảnh	Ngôn ngữ nhạy cảm với ngữ cảnh	Automaton giới hạn tuyến tính
Loại 2	Ngữ pháp không theo ngữ cảnh	Ngôn ngữ không có ngữ cảnh	Tự động đẩy xuống
Loại 3	Ngữ pháp thông thường	Ngôn ngữ thông thường	Automaton trạng thái hữu hạn

Hãy xem hình minh họa sau đây. Nó cho thấy phạm vi của từng loại ngữ pháp -

Loại - 3 Ngữ pháp

Type-3 grammarstạo ra các ngôn ngữ thông thường. Ngữ pháp loại 3 phải có một dấu không đầu cuối ở phía bên trái và phía bên tay phải bao gồm một dấu đầu cuối hoặc dấu đầu cuối đơn theo sau là một dấu không đầu cuối.

Các sản phẩm phải ở dạng X → a or X → aY

Ở đâu X, Y ∈ N (Không có thiết bị đầu cuối)

và a ∈ T (Thiết bị đầu cuối)

Quy luật S → ε được phép nếu S không xuất hiện ở bên phải của bất kỳ quy tắc nào.

Thí dụ

X → ε 
X → a | aY
Y → b

Loại - 2 Ngữ pháp

Type-2 grammars tạo ngôn ngữ không có ngữ cảnh.

Các sản phẩm phải ở dạng A → γ

Ở đâu A ∈ N (Không có thiết bị đầu cuối)

và γ ∈ (T ∪ N)* (Chuỗi thiết bị đầu cuối và không thiết bị đầu cuối).

Những ngôn ngữ do các ngữ pháp này tạo ra được nhận dạng bởi một tự động đẩy xuống không xác định.

Thí dụ

S → X a 
X → a 
X → aX 
X → abc 
X → ε

Loại - 1 Ngữ pháp

Type-1 grammarstạo ngôn ngữ nhạy cảm theo ngữ cảnh. Các sản phẩm phải ở dạng

α A β → α γ β

Ở đâu A ∈ N (Không có thiết bị đầu cuối)

và α, β, γ ∈ (T ∪ N)* (Chuỗi thiết bị đầu cuối và không thiết bị đầu cuối)

Các dây α và β có thể trống, nhưng γ không được để trống.

Quy luật S → εđược phép nếu S không xuất hiện ở phía bên phải của bất kỳ quy tắc nào. Các ngôn ngữ được tạo ra bởi những ngữ pháp này được nhận dạng bởi một tự động giới hạn tuyến tính.

Thí dụ

AB → AbBc 
A → bcA 
B → b

Loại - 0 Ngữ pháp

Type-0 grammarstạo ra các ngôn ngữ liệt kê đệ quy. Các sản phẩm không có hạn chế. Chúng là bất kỳ ngữ pháp cấu trúc giai đoạn nào bao gồm tất cả các ngữ pháp chính thức.

Chúng tạo ra các ngôn ngữ được máy Turing nhận dạng.

Các sản phẩm có thể ở dạng α → β Ở đâu α là một chuỗi các thiết bị đầu cuối và danh nghĩa có ít nhất một đầu cuối không và α không được rỗng. β là một chuỗi các thiết bị đầu cuối và không thiết bị đầu cuối.

Thí dụ

S → ACaB 
Bc → acB 
CB → DB 
aD → Db