Ngôn ngữ phi ngữ cảnh là một loại ngôn ngữ chính thức có thể được mô tả bằng ngữ pháp phi ngữ cảnh. Trong lĩnh vực lý thuyết độ phức tạp tính toán, ngôn ngữ phi ngữ cảnh đóng vai trò quan trọng trong việc hiểu được độ phức tạp của các vấn đề và giới hạn của tính toán. Để hiểu đầy đủ khái niệm ngôn ngữ phi ngữ cảnh, điều cần thiết là phải khám phá định nghĩa của nó và các thành phần của ngữ pháp phi ngữ cảnh.
Ngôn ngữ phi ngữ cảnh được định nghĩa là một tập hợp các chuỗi có thể được tạo bởi ngữ pháp phi ngữ cảnh. Một ngữ pháp phi ngữ cảnh bao gồm bốn thành phần: một tập hợp các ký hiệu không đầu cuối, một tập hợp các ký hiệu đầu cuối, một tập hợp các quy tắc sản xuất và một ký hiệu bắt đầu.
Các ký hiệu không đầu cuối đại diện cho các thực thể trừu tượng có thể được mở rộng thêm hoặc thay thế bằng các ký hiệu khác. Các ký hiệu này thường được biểu thị bằng chữ in hoa. Ví dụ: trong ngữ pháp phi ngữ cảnh cho các biểu thức số học, chúng ta có thể có các ký hiệu không đầu cuối như E (biểu thị một biểu thức), T (biểu thị một thuật ngữ) và F (biểu thị một thừa số).
Mặt khác, các ký hiệu đầu cuối là các đơn vị cơ bản của ngôn ngữ. Các ký hiệu này không thể mở rộng thêm và thường được biểu thị bằng chữ thường hoặc các ký tự khác. Trong ngữ cảnh của các biểu thức số học, các ký hiệu đầu cuối có thể bao gồm các số (ví dụ: 0, 1, 2) và các toán tử số học (ví dụ: +, -, *, /).
Các quy tắc sản xuất xác định cách các ký hiệu không đầu cuối có thể được mở rộng hoặc thay thế bằng các ký hiệu khác. Mỗi quy tắc sản xuất bao gồm một ký hiệu không đầu cuối ở bên trái và một chuỗi ký hiệu (cả không đầu cuối và đầu cuối) ở bên phải. Các quy tắc này chỉ định các phép biến đổi hoặc dẫn xuất có thể được áp dụng để tạo các chuỗi hợp lệ trong ngôn ngữ. Ví dụ: trong ngữ pháp phi ngữ cảnh cho các biểu thức số học, chúng ta có thể có các quy tắc sản xuất như E -> E + T (chỉ ra rằng một biểu thức có thể được mở rộng bằng cách thêm một thuật ngữ) hoặc T -> F (chỉ ra rằng một thuật ngữ có thể được được thay thế bởi một thừa số).
Ký hiệu bắt đầu đại diện cho ký hiệu không đầu cuối ban đầu mà từ đó việc tạo các chuỗi hợp lệ bắt đầu. Nó thường được ký hiệu là S. Trong ngữ cảnh của các biểu thức số học, ký hiệu bắt đầu có thể là E, cho biết rằng việc tạo các biểu thức hợp lệ bắt đầu từ một biểu thức.
Để minh họa khái niệm về một ngôn ngữ phi ngữ cảnh và các thành phần của nó, hãy xem xét một ngữ pháp phi ngữ cảnh đơn giản cho một ngôn ngữ tạo ra các dấu ngoặc đơn cân bằng. Ngữ pháp bao gồm các thành phần sau:
Ký hiệu không đầu cuối: S (ký hiệu bắt đầu)
Ký hiệu đầu cuối: (, )
Quy tắc sản xuất: S -> (S) | SS | ε (trong đó ε đại diện cho chuỗi rỗng)
Trong ngữ pháp này, ký hiệu không đầu cuối S đại diện cho một chuỗi các dấu ngoặc đơn cân đối. Quy tắc sản xuất xác định rằng S có thể được mở rộng bằng cách đặt một chữ S khác trong dấu ngoặc đơn ((S)), nối hai chữ S (SS) hoặc tạo chuỗi trống (ε).
Sử dụng ngữ pháp này, chúng tôi có thể tạo các chuỗi hợp lệ bằng ngôn ngữ của dấu ngoặc đơn cân đối. Ví dụ, bắt đầu với ký hiệu bắt đầu là S, chúng ta có thể áp dụng các quy tắc sản xuất để lấy được chuỗi ((())). Chuỗi này đại diện cho một chuỗi các dấu ngoặc đơn cân bằng.
Ngôn ngữ phi ngữ cảnh được định nghĩa là một tập hợp các chuỗi có thể được tạo bởi ngữ pháp phi ngữ cảnh. Các thành phần của ngữ pháp phi ngữ cảnh bao gồm các ký hiệu không đầu cuối, ký hiệu đầu cuối, quy tắc sản xuất và ký hiệu bắt đầu. Các ký hiệu không đầu cuối đại diện cho các thực thể trừu tượng có thể được mở rộng hoặc thay thế, trong khi các ký hiệu đầu cuối là các đơn vị cơ bản của ngôn ngữ. Các quy tắc sản xuất chỉ định các phép biến đổi hoặc dẫn xuất có thể có và ký hiệu bắt đầu đại diện cho ký hiệu không đầu cuối ban đầu để tạo các chuỗi hợp lệ.
Các câu hỏi và câu trả lời gần đây khác liên quan đến Ngôn ngữ nhạy cảm với ngữ cảnh:
- Ngôn ngữ này mạnh hơn ngôn ngữ khác có nghĩa là gì?
- Có phải dạng chuẩn ngữ pháp của Chomsky luôn có thể quyết định được không?
- Hiện tại có phương pháp nào để nhận dạng Loại 0 không? Chúng ta có mong đợi máy tính lượng tử sẽ biến nó thành khả thi không?
- Trong ví dụ về ngôn ngữ D, tại sao thuộc tính bơm không giữ cho chuỗi S = 0^P 1^P 0^P 1^P?
- Hai trường hợp cần xem xét khi chia một chuỗi để áp dụng bổ đề bơm là gì?
- Trong ví dụ về ngôn ngữ B, tại sao thuộc tính bơm không giữ cho chuỗi a^Pb^Pc^P?
- Các điều kiện cần phải được thỏa mãn để tài sản bơm được giữ là gì?
- Làm cách nào để sử dụng Bổ đề bơm cho CFL để chứng minh rằng một ngôn ngữ không phải là ngữ cảnh?
- Các điều kiện phải được thỏa mãn để một ngôn ngữ được coi là phi ngữ cảnh theo bổ đề bơm cho các ngôn ngữ phi ngữ cảnh là gì?
- Giải thích khái niệm đệ quy trong ngữ cảnh ngữ pháp phi ngữ cảnh và cách nó cho phép tạo ra các chuỗi dài.
Xem thêm câu hỏi và câu trả lời trong Ngữ cảnh nhạy cảm