Context-free grammar

Uncommon card · No. 154330

In formal language theory, a context-free grammar (CFG) is a formal grammar whose production rules can be applied to a nonterminal symbol regardless of its context. In particular, in a context-free grammar, each production rule is of the form A → α {\displaystyle A\ \to \ \alpha } with A {\displaystyle A} a single nonterminal symbol, and α {\displaystyle \alpha } a string of terminals and/or nonterminals ( α {\displaystyle \alpha } can be empty). Regardless of which symbols surround it, the single nonterminal A {\displaystyle A} on the left hand side can always be replaced by α {\displaystyle \alpha } on the right hand side. This distinguishes it from a context-sensitive grammar, which can have...

Read on Wikipedia · Image Jochen Burghardt, CC BY-SA 4.0