A formal grammar specifies how to generate a formal language by repeated applications of production rules. Write , where is a finite set of nonterminal symbols, is a disjoint finite alphabet of terminal symbols, is the start symbol, and is a finite set of production rules . In an unrestricted formal grammar, the word must contain at least one nonterminal symbol; may be any word over .
A grammar derivation replaces an occurrence of inside a word by . The generated formal language is
Intermediate words may still contain nonterminal symbols; these are sentential forms. For example, the production rules and give and generate exactly . Restricting each left side to one nonterminal symbol gives a context-free grammar.[ref]
A context-sensitive grammar has productions of the form , where is a nonterminal symbol and is a nonempty word. The surrounding words specify the context in which replacement is permitted. Every such step is length-nondecreasing.
An equivalent language-class description uses arbitrary noncontracting production rules with and a nonterminal in . If the empty word is included, the customary exception is with start symbol absent from every right side. Individual noncontracting rules need not have the displayed context-preserving form, although the generated language classes agree.
For example, replaces only when its immediate context is on the left and on the right. The language is context-sensitive and is not a context-free language. The associated computational model is a linear bounded automaton, whose usable tape is bounded by a constant times input length.
A linear bounded automaton is a Turing machine whose usable tape on an input of length is bounded by cells for a fixed constant . A common equivalent model places end markers around the input and permits rewriting only between them. The standard language-class characterization uses a nondeterministic machine: these machines recognize exactly the nonempty-word languages generated by context-sensitive grammars, with an explicit convention needed for the empty word.[ref]
For , repeatedly mark one unmarked , one and one , rejecting if the order is wrong or a matching symbol is absent. Accept when no symbols remain unmarked. This uses the original input cells and repeated sweeps, showing how bounded space can check three linked counts. “Linear bounded” limits space, not running time.
A sentential form of a formal grammar is any word derivable from the start symbol: . It may contain both terminal symbols and nonterminal symbols. A terminal-only sentential form is a word of the generated formal language.
For productions and , the derivation contains four sentential forms. The intermediate is not a sentence of the terminal language because remains. An arbitrary word over need not be a sentential form: it must actually be reachable by a grammar derivation.
Tracking sentential forms makes it possible to discuss intermediate parsing states and distinguish leftmost derivations from other orders of rewriting. The word need not be a complete output or a prefix of one in an arbitrary grammar.
A formation rule specifies how well-formed expressions can be constructed from simpler expressions in a formal language. The formal grammar of propositional formulas has rules for propositional variables, negation and binary logical implication.
A variable-based grammar has disjoint finite terminal and variable alphabets , a start variable , and productions in which and contains at least one variable.
A nonterminal is unreachable when no word derivable from the start symbol contains it. Productions whose left sides are unreachable do not affect the generated language.
A nonterminal symbol of a formal grammar is productive if for some word consisting only of terminal symbols; otherwise it is nonproductive. In a context-free grammar, a sentential form containing a nonproductive nonterminal symbol cannot derive a terminal word: the descendants of that occurrence would have to provide a terminal derivation from the nonterminal symbol. Consequently productions involving nonproductive nonterminal symbols can be discarded when simplifying a context-free grammar.
The context-free hypothesis matters. A general variable-based grammar can have a production rule while neither nor alone derives a terminal word. A terminal derivation from a larger context therefore need not demonstrate productivity of each individual nonterminal symbol.
A right-linear regular grammar has productions of the forms and , where are variables and is a terminal word.
Every sentential form reachable from the start variable of a right-linear grammar is either a terminal word or , where is the unique variable and occurs at the right end.
A variable is accessible when for some terminal word .
A variable is looping when for some terminal word through a nonempty derivation.
A variable is terminable when for some terminal word .
If a finite right-linear grammar generates an infinite language, some variable is accessible, looping, and terminable. It is the repeated variable on a sufficiently long accepting derivation.
For context-free grammars and with disjoint nonterminal symbol sets, introduce a fresh nonterminal symbol and put
Then , the concatenation of the two formal languages. After the first production, every production rule acts within one of the two component parse trees. Their terminal words form one word from followed by one from . Conversely, any pair of component derivations can be performed after .
The construction does not work for arbitrary variable-based grammars. Let have production rules and , and let have the single production rule . Here is empty and , but the combined formal grammar derives . The production rule consumes a terminal symbol supplied by the other component, crossing the boundary that context-free grammar rules preserve.
Retain every production of whose right-hand side contains a variable, replace every production with by , include , and use as start variable. If and are right-linear, the resulting grammar is right-linear and generates .
The regular construction relies on a regular derivation having exactly one terminal rule, at its end. In a general variable-based grammar several variables may each use terminal productions, so replacing every such production can introduce several copies of the second start variable.
Even if both input grammars are regular, the added production has two variables on its right-hand side and therefore need not be a regular production.

Articles by others on the same topic (1)

Formal grammar is a set of rules and structures that define the syntax of a language. It provides a formal way to describe how sentences or expressions in a language can be constructed. Formal grammars are widely used in computer science, linguistics, and artificial intelligence to define programming languages, natural languages, and various systems of communication.