Làm cách nào để xác định xem ngôn ngữ có phải là ngữ cảnh miễn phí hay không?

1

Bạn cần một ngữ pháp cho ngôn ngữ để xác định xem đó có phải là ngữ cảnh không. Ngữ pháp là ngữ cảnh miễn phí nếu tất cả các sản phẩm của nó có dạng "(không phải là thiết bị đầu cuối) -> chuỗi các thiết bị đầu cuối và không phải thiết bị đầu cuối".

Nguồn

2010-08-18 08:15:54 falagar

+0

Có cảm ơn. Sau đó 0^n 1^n là ngữ cảnh miễn phí. vậy Bổ sung của {(0^n1^n)^m | m, n> 0} là Ngữ cảnh miễn phí hay không. – user423733

+0

Cần phải chỉ ra rằng chỉ vì bạn có thể đưa ra ngữ pháp không ngữ cảnh cho một ngôn ngữ không có nghĩa là không có ngữ cảnh tự do ngữ cảnh cho ngôn ngữ đó. Trong ngắn hạn, bạn chỉ có thể sử dụng xây dựng một ngữ pháp để cho thấy rằng một ngôn ngữ không có ngữ cảnh, không phải để cho thấy rằng nó không phải là. – sepp2k

22

Trước tiên, bạn nên cố gắng xây dựng một context-free grammar tạo thành ngôn ngữ theo chủ đề. Ngữ pháp không có ngữ cảnh nếu các cạnh bên trái của tất cả các sản phẩm chứa chính xác một biểu tượng không phải là thiết bị đầu cuối. Theo định nghĩa, nếu có, thì ngôn ngữ không có ngữ cảnh.

Cấu trúc tương đương sẽ là pushdown automaton. Nó giống như DFA, nhưng với một ngăn xếp có sẵn. Nó có thể dễ dàng hơn để xây dựng hơn một ngữ pháp.

Tuy nhiên, nếu bạn không xây dựng được ngữ pháp hoặc ô tô, điều đó không có nghĩa là ngôn ngữ không có ngữ cảnh; có lẽ, đó chỉ là bạn, những người không thể xây dựng một ngữ pháp đủ khôn lanh (ví dụ, tôi đã từng dành khoảng 7 giờ để xây dựng một ngữ pháp cho một ngôn ngữ khó khăn).

Nếu bạn bắt đầu nghi ngờ nếu ngôn ngữ không có ngữ cảnh, bạn nên sử dụng cái gọi là "pumping lemma for context-free languages". Nó mô tả một thuộc tính của tất cả ngôn ngữ không có ngữ cảnh và nếu ngôn ngữ của bạn vi phạm, thì chắc chắn nó không có ngữ cảnh (xem usage notes tại Wikipedia).

Bổ đề này là hệ quả của Ogden's lemma. Vì vậy, Ogden là mạnh hơn, và nếu bạn không áp dụng bổ đề bơm, bạn có thể thử Ogden (nó được sử dụng theo cùng một cách).

Nguồn

2010-08-18 08:20:16

+2

Tất cả điều này là tốt, nhưng bạn nhận ra rằng không ai trong số này hoàn toàn xác định một câu trả lời, phải không? Điều gì xảy ra nếu bạn không thể tìm thấy ngữ pháp không có ngữ cảnh, và bổ đề của Ogden không mâu thuẫn với bất kỳ tài sản nào đã biết của ngôn ngữ của bạn? Bạn vẫn còn bị mắc kẹt với vấn đề. (Mà tôi tin là khó, vì vậy câu trả lời của bạn có lẽ là tốt như nó được, chỉ cần chỉ ra rằng nó không phải là đầy đủ.) – ShreevatsaR

+1

@ShreevatsaR, chính xác. Nó có thể xảy ra rằng không ai trong số các công trình trên. Nhưng tôi thực sự không biết phải làm gì trong trường hợp đó. –

2

Sửa

Như đã đề cập trong các ý kiến để chứng minh một ngôn ngữ là không-CFG, tôi tin là sử dụng Bổ đề một ogdens. Việc giải thích sai vốn có trong câu trả lời trước đây của tôi là để được miễn trừ :) Giữ lại câu trả lời trước đó cho người bảo hiểm.

Cũ câu trả lời

Bằng cách nhìn vào ngữ pháp và các quy tắc sử dụng! Như đã thấy từ hình ảnh (phân cấp wikipedia chomsky). Chỉ các ngôn ngữ thông thường là không có ngữ cảnh. Ngụ ý bất cứ điều gì sử dụng những thứ có dạng A-> aB hoặc A-> Ba một mình không phải là ngữ cảnh tự do.

alt text

Sửa A-> AB và A-> định nghĩa Ba có nghĩa là để bày tỏ trái và ngữ pháp đệ quy phải và không được hiểu theo nghĩa đen.

Nguồn

2010-08-18 08:21:44 questzen

+1

Về mặt kỹ thuật, các ngôn ngữ thông thường không có ngữ cảnh, nhưng tôi đồng ý rằng thuật ngữ "không có ngữ cảnh" thường được sử dụng để có nghĩa là "không có ngữ cảnh, nhưng không thường xuyên" - tức là các nhãn trong biểu đồ được áp dụng cho các vùng nhỏ nhất họ đang ở, thay vì các vòng kết nối nhỏ nhất mà họ đang ở. – reinierpost

+3

"Chỉ những ngôn ngữ thông thường là không có ngữ cảnh". Gì? Tôi nghĩ rằng bạn đang đọc sơ đồ sai đường xung quanh. Các ngôn ngữ thông thường là một tập con của các ngôn ngữ không có ngữ cảnh và do đó chúng chắc chắn không có ngữ cảnh. Tuy nhiên, hầu hết các ngôn ngữ nhạy cảm theo ngữ cảnh là * không * không có bối cảnh làm cho các ngôn ngữ nhạy cảm theo ngữ cảnh trở thành một phần lớn các ngôn ngữ không có ngữ cảnh. – sepp2k

+0

Sepp2k, tôi có nghĩa là những người về quyền lực biểu cảm. Ví dụ, sức mạnh biểu cảm của ngữ cảnh tự do ngôn ngữ cao hơn nhiều so với ngôn ngữ thông thường. Ngữ pháp thông thường ** sẽ không ** có cùng sức mạnh biểu cảm. Tuy nhiên, một CSL có thể mang tính biểu cảm hơn CFG. Vì vậy, một CSL chắc chắn là một ứng cử viên cho CFG nhưng RG thì không. – questzen

Làm cách nào để xác định xem ngôn ngữ có phải là ngữ cảnh miễn phí hay không?

Trả lời

Các vấn đề liên quan