Context-free grammars
Published:
A context-free grammar (CFG) is a term used in formal language theory to describe a certain type of formal grammar. A context free grammar is a set of production rules that describe all possible strings in a given formal language. Production rules are simple replacements.
In context free grammars, all rules are one to one, one to many, or one to none. These rules can be applied regardless of context. The left hand side of the production rule is also always a nonterminal symbol. This means that the symbol does not appear in the resulting formal language.
Rules can also be applied in reverse to check if a string is grammatically correct according to the grammar.
Languages generated by context-free grammars are known as context-free languages (CFL). Different context-free grammars can generate the same context-free language. It is important to distinguish properties of the language (intrinsic properties) from properties of a particular grammar (extrinsic properties). The language equality question (do two given context-free grammars generate the same language?) is undecidable.
Context-free grammars arise in linguistics where they are used to describe the structure of sentences and words in natural language, and they were in fact invented by the linguist Noam Chomsky for this purpose, but have not really lived up to their original expectation. By contrast, in computer science, as the use of recursively defined concepts increased, they were used more and more. In an early application, grammars are used to describe the structure of programming languages.
In linguistics, some authors use the term phrase structure grammar to refer to context-free grammars, whereby phrase structure grammars are distinct from dependency grammars. In computer science, a popular notation for context-free grammars is Backus-Naur Form, or BNF.
See also
Artificial Intelligence, Computer Complexity, Turing Machines, Automata theory, Theory of computation
Papers
- Chomsky, Noam (Sep 1956), Three models for the description of language, Information Theory, IEEE Transactions 2 (3): 113–124.
- Norvell, Theodore. A Short Introduction to Regular Expressions and Context-Free Grammars.
- Shieber, Stuart (1985), Evidence against the context-freeness of natural language, Linguistics and Philosophy 8 (3): 333-343.