Context-free grammar là gì?

Văn phạm phi ngữ cảnh (context-free grammar) là văn phạm (grammar) mà luật sinh (production rule) có dạng N → (N ∪ T)*. Tức là vế trái của luật sinh chỉ chứa một ký hiệu không kết thúc (nonterminal) và vế phải là tùy ý.

Ví dụ một số văn phạm phi ngữ cảnh (context-free grammar) như:

• Văn phạm ({A}, {a, b, c}, P, A), P : A → aA, A → abc.
• Văn phạm ({S, F}, {0, 1}, P, S), P: S → 00S | 11F, F → 00F | ε
• Văn phạm ({S, a, b}, {a, b}, P, S), P: S → aSa, S → bSb, S → ε