Context-Free Grammar

A Context-Free Grammar is a formal grammar that is based on production rules whose left-hand side consist of a single non-terminal symbol (and whose Right-Hand Side is a possibly empty string of terminals and/or nonterminals ??).

• AKA: Context Free Grammar, CFG.
• Context:
  • It can be defined as a 5-Tuple: (Grammar, Formal Alphabet, Non-Terminal Symbol Set, Terminal Symbol Set, Non-Terminal Symbol)
  • It can produce a Context-Free Language.
  • It can range from being a Determinisitic CFG to being a Probabilistic CFG.
  • It can range from being a Non-Lexicalized CFG to being a Lexicalized CFG.
  • It can (often) be used to model a Natural Language Syntax (but not Swiss-German).
• Example(s):
  • [S → aSb | ε], generates the Language {a^nb^n,n>=0}.
  • a Context-Free Phrase-Structure Grammar.
  • …
• Counter-Example(s):
  • a Context-Sensitive Grammar.
• See: Parsing, Link Grammar, Tree Adjoining Grammar, Chomsky Hierarchy, Earley Parser.

---

---

References

2016

• (Wikipedia, 2016) ⇒ http://wikipedia.org/wiki/context-free_grammar Retrieved:2016-4-9.
  • In formal language theory, a context-free grammar (CFG)

    is a formal grammar in which every production rule is of the form [math]\displaystyle{ A\ \to\ \alpha }[/math] where [math]\displaystyle{ A }[/math] is a single nonterminal symbol, and [math]\displaystyle{ \alpha }[/math] is a string of terminals and/or nonterminals ([math]\displaystyle{ \alpha }[/math] can be empty). A formal grammar is considered "context free" when its production rules can be applied regardless of the context of a nonterminal. No matter which symbols surround it, the single nonterminal on the left hand side can always be replaced by the right hand side. This is what distinguishes it from a context-sensitive grammar.

    Such a grammar has long lists of words, and also rules on what types of words can be added in what order.

    Higher rules combine several lower rules to make a sentence. Such sentences will be grammatically correct, but may not have any meaning.

    Each rule has its own symbol, which can be replaced with symbols representing lower rules, which can be replaced with words.

    This can also be done in reverse to check if a sentence is grammatically correct.

     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 a newer application, they are used in an essential part of the Extensible Markup Language (XML) called the Document Type Definition.

    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.

2009

• http://www.antlr.org/doc/glossary.html
  • QUOTE: A grammar where recognition of a particular construct does not depend on whether it is in a particular syntactic context.

• http://www.cse.unsw.edu.au/~billw/nlpdict.html#contextfreegram
  • QUOTE: A context-free grammar is defined to be a 5-tuple (P, A, N, T, S) with components as follows:
    • P A set of grammar rules or productions, that is, items of the form X → a, where X is a member of the set N, that is, a non-terminal symbol, and a is a string over the alphabet A.

      An example would be the rule NP → ART ADJ N which signifies that a Noun Phrase can be an ARTicle followed by an ADJective followed by a Noun, or N → horse, which signifies that horse is a Noun.

  • NP, ART, ADJ, and N are all non-terminal symbols, and horse is a terminal symbol.
    • A the alphabet of the grammar, equal to the disjoint union of N and T
    • N the set of non-terminal symbols (i.e. grammatical or phrasal categories)
    • T the set of terminal symbols (i.e. words of the language that the grammar defines)
    • S a distinguished non-terminal, normally interpreted as representing a full sentence (or program, in the case of a programming language grammar)

1957

• (Chomsky, 1957) ⇒ Noam Chomsky. (1957). “Syntactic Structures." Mouton de Gruyter.

---