Context-free language

A formal language generated by a context-free grammar and recognizable by a pushdown automaton. Its productions replace one nonterminal regardless of the surrounding symbols.

Context-free grammar: A grammar whose productions replace a single nonterminal with a string of terminals and nonterminals. A context-free language is generated by at least one such grammar.
Stack (abstract data type): A data structure that adds and removes items at one end, following last-in, first-out order. A pushdown automaton uses this memory to track nested structure.
Dyck language: The language of properly balanced strings of matching parentheses, often with several bracket types. Nested matching is the archetypal structure recognized by a stack.
Regular language: A formal language recognizable by a finite automaton or generated by a regular expression. Every regular language is context-free, but regular languages cannot require unbounded nested matching.
Context-free production: A rewrite rule with one nonterminal on the left and a string of grammar symbols on the right. These rules define which strings the grammar can generate.
Nondeterministic pushdown automaton: A pushdown automaton that may choose among multiple transitions for the same input and state. Nondeterministic stack machines characterize all context-free languages.
Balanced parentheses: Strings of opening and closing parentheses in which every prefix has at least as many openings as closings. This simple language demonstrates unbounded nesting within a context-free language.
Context-sensitive language: A formal language generated by a context-sensitive grammar, equivalently recognized by a linear-bounded automaton. This larger class can express dependencies such as equal counts of three symbol blocks.
Derivation (formal languages): A sequence of grammar-rule applications that transforms a start symbol into a string. A terminal string belongs to the language when the grammar can derive it.
Deterministic context-free language: A context-free language recognizable by a deterministic pushdown automaton. It is a strict subclass with especially useful parsing properties.

Linked from 7 pages