Formal grammar

Suppose we have the following production rules:

1. ${\displaystyle S\rightarrow aSb}$

2. ${\displaystyle S\rightarrow ba}$

then we start with S, and can choose a rule to apply to it. If we choose rule 1, we obtain the string aSb. If we then choose rule 1 again, we replace S with aSb and obtain the string aaSbb. If we now choose rule 2, we replace S with ba and obtain the string aababb, and are done. We can write this series of choices more briefly, using symbols: ${\displaystyle S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aababb}$.

The language of the grammar is the infinite set ${\displaystyle \{a^{n}bab^{n}\mid n\geq 0\}=\{ba,abab,aababb,aaababbb,\dotsc \}}$, where ${\displaystyle a^{k}}$ is ${\displaystyle a}$ repeated ${\displaystyle k}$ times (and ${\displaystyle n}$ in particular represents the number of times production rule 1 has been applied). This grammar is context-free (only single nonterminals appear as left-hand sides) and unambiguous.

Suppose the rules are these instead:

1. ${\displaystyle S\rightarrow a}$

2. ${\displaystyle S\rightarrow SS}$

3. ${\displaystyle aSa\rightarrow b}$

This grammar is not context-free due to rule 3 and it is ambiguous due to the multiple ways in which rule 2 can be used to generate sequences of ${\displaystyle S}$s.

However, the language it generates is simply the set of all nonempty strings consisting of ${\displaystyle a}$s and/or ${\displaystyle b}$s. This is easy to see: to generate a ${\displaystyle b}$ from an ${\displaystyle S}$, use rule 2 twice to generate ${\displaystyle SSS}$, then rule 1 twice and rule 3 once to produce ${\displaystyle b}$. This means we can generate arbitrary nonempty sequences of ${\displaystyle S}$s and then replace each of them with ${\displaystyle a}$ or ${\displaystyle b}$ as we please.

That same language can alternatively be generated by a context-free, nonambiguous grammar; for instance, the regular grammar with rules

1. ${\displaystyle S\rightarrow aS}$

2. ${\displaystyle S\rightarrow bS}$

3. ${\displaystyle S\rightarrow a}$

4. ${\displaystyle S\rightarrow b}$

In the classic formalization of generative grammars first proposed by Noam Chomsky in the 1950s,[2][3] a grammar G consists of the following components:

• A finite set N of nonterminal symbols, that is disjoint with the strings formed from G.
• A finite set ${\displaystyle \Sigma }$ of terminal symbols that is disjoint from N.
• A finite set P of production rules, each rule of the form

${\displaystyle (\Sigma \cup N)^{*}N(\Sigma \cup N)^{*}\rightarrow (\Sigma \cup N)^{*}}$

where ${\displaystyle {*}}$ is the Kleene star operator and ${\displaystyle \cup }$ denotes set union. That is, each production rule maps from one string of symbols to another, where the first string (the "head") contains an arbitrary number of symbols provided at least one of them is a nonterminal. In the case that the second string (the "body") consists solely of the empty string—i.e., that it contains no symbols at all—it may be denoted with a special notation (often ${\displaystyle \Lambda }$, e or ${\displaystyle \epsilon }$) in order to avoid confusion.

• A distinguished symbol ${\displaystyle S\in N}$ that is the start symbol, also called the sentence symbol.

A grammar is formally defined as the tuple ${\displaystyle (N,\Sigma ,P,S)}$. Such a formal grammar is often called a rewriting system or a phrase structure grammar in the literature.[4][5]

The operation of a grammar can be defined in terms of relations on strings:

• Given a grammar ${\displaystyle G=(N,\Sigma ,P,S)}$, the binary relation ${\displaystyle {\underset {G}{\Rightarrow }}}$ (pronounced as "G derives in one step") on strings in ${\displaystyle (\Sigma \cup N)^{*}}$ is defined by:

  ${\displaystyle x{\underset {G}{\Rightarrow }}y\iff \exists u,v,p,q\in (\Sigma \cup N)^{*}:(x=upv)\wedge (p\rightarrow q\in P)\wedge (y=uqv)}$

• the relation ${\displaystyle {\overset {*}{\underset {G}{\Rightarrow }}}}$ (pronounced as G derives in zero or more steps) is defined as the reflexive transitive closure of ${\displaystyle {\underset {G}{\Rightarrow }}}$
• a sentential form is a member of ${\displaystyle (\Sigma \cup N)^{*}}$ that can be derived in a finite number of steps from the start symbol ${\displaystyle S}$; that is, a sentential form is a member of ${\displaystyle \left\{w\in (\Sigma \cup N)^{*}\mid S{\overset {*}{\underset {G}{\Rightarrow }}}w\right\}}$. A sentential form that contains no nonterminal symbols (i.e. is a member of ${\displaystyle \Sigma ^{*}}$) is called a sentence.[6]
• the language of ${\displaystyle G}$, denoted as ${\displaystyle {\boldsymbol {L}}(G)}$, is defined as the set of sentences built by ${\displaystyle G}$.

Note that the grammar ${\displaystyle G=(N,\Sigma ,P,S)}$ is effectively the semi-Thue system ${\displaystyle (N\cup \Sigma ,P)}$, rewriting strings in exactly the same way; the only difference is in that we distinguish specific nonterminal symbols, which must be rewritten in rewrite rules, and are only interested in rewritings from the designated start symbol ${\displaystyle S}$ to strings without nonterminal symbols.

For these examples, formal languages are specified using set-builder notation.

Consider the grammar ${\displaystyle G}$ where ${\displaystyle N=\left\{S,B\right\}}$, ${\displaystyle \Sigma =\left\{a,b,c\right\}}$, ${\displaystyle S}$ is the start symbol, and ${\displaystyle P}$ consists of the following production rules:

1. ${\displaystyle S\rightarrow aBSc}$

2. ${\displaystyle S\rightarrow abc}$

3. ${\displaystyle Ba\rightarrow aB}$

4. ${\displaystyle Bb\rightarrow bb}$

This grammar defines the language ${\displaystyle L(G)=\left\{a^{n}b^{n}c^{n}\mid n\geq 1\right\}}$ where ${\displaystyle a^{n}}$ denotes a string of n consecutive ${\displaystyle a}$'s. Thus, the language is the set of strings that consist of 1 or more ${\displaystyle a}$'s, followed by the same number of ${\displaystyle b}$'s, followed by the same number of ${\displaystyle c}$'s.

Some examples of the derivation of strings in ${\displaystyle L(G)}$ are:

(Note on notation: ${\displaystyle P{\underset {i}{\Rightarrow }}Q}$ reads "String P generates string Q by means of production i", and the generated part is each time indicated in bold type.)

A context-free grammar is a grammar in which the left-hand side of each production rule consists of only a single nonterminal symbol. This restriction is non-trivial; not all languages can be generated by context-free grammars. Those that can are called context-free languages.

The language ${\displaystyle L(G)=\left\{a^{n}b^{n}c^{n}\mid n\geq 1\right\}}$ defined above is not a context-free language, and this can be strictly proven using the pumping lemma for context-free languages, but for example the language ${\displaystyle \left\{a^{n}b^{n}\mid n\geq 1\right\}}$ (at least 1 ${\displaystyle a}$ followed by the same number of ${\displaystyle b}$'s) is context-free, as it can be defined by the grammar ${\displaystyle G_{2}}$ with ${\displaystyle N=\left\{S\right\}}$, ${\displaystyle \Sigma =\left\{a,b\right\}}$, ${\displaystyle S}$ the start symbol, and the following production rules:

1. ${\displaystyle S\rightarrow aSb}$

2. ${\displaystyle S\rightarrow ab}$

A context-free language can be recognized in ${\displaystyle O(n^{3})}$ time (see Big O notation) by an algorithm such as Earley's recogniser. That is, for every context-free language, a machine can be built that takes a string as input and determines in ${\displaystyle O(n^{3})}$ time whether the string is a member of the language, where ${\displaystyle n}$ is the length of the string.[8] Deterministic context-free languages is a subset of context-free languages that can be recognized in linear time.[9] There exist various algorithms that target either this set of languages or some subset of it.

In regular grammars, the left hand side is again only a single nonterminal symbol, but now the right-hand side is also restricted. The right side may be the empty string, or a single terminal symbol, or a single terminal symbol followed by a nonterminal symbol, but nothing else. (Sometimes a broader definition is used: one can allow longer strings of terminals or single nonterminals without anything else, making languages easier to denote while still defining the same class of languages.)

The language ${\displaystyle \left\{a^{n}b^{n}\mid n\geq 1\right\}}$ defined above is not regular, but the language ${\displaystyle \left\{a^{n}b^{m}\mid m,n\geq 1\right\}}$ (at least 1 ${\displaystyle a}$ followed by at least 1 ${\displaystyle b}$, where the numbers may be different) is, as it can be defined by the grammar ${\displaystyle G_{3}}$ with ${\displaystyle N=\left\{S,A,B\right\}}$, ${\displaystyle \Sigma =\left\{a,b\right\}}$, ${\displaystyle S}$ the start symbol, and the following production rules:

1. ${\displaystyle S\rightarrow aA}$
2. ${\displaystyle A\rightarrow aA}$
3. ${\displaystyle A\rightarrow bB}$
4. ${\displaystyle B\rightarrow bB}$
5. ${\displaystyle B\rightarrow \epsilon }$

All languages generated by a regular grammar can be recognized in ${\displaystyle O(n)}$ time by a finite-state machine. Although in practice, regular grammars are commonly expressed using regular expressions, some forms of regular expression used in practice do not strictly generate the regular languages and do not show linear recognitional performance due to those deviations.

Many extensions and variations on Chomsky's original hierarchy of formal grammars have been developed, both by linguists and by computer scientists, usually either in order to increase their expressive power or in order to make them easier to analyze or parse. Some forms of grammars developed include:

• Tree-adjoining grammars increase the expressiveness of conventional generative grammars by allowing rewrite rules to operate on parse trees instead of just strings.[10]
• Affix grammars[11] and attribute grammars[12][13] allow rewrite rules to be augmented with semantic attributes and operations, useful both for increasing grammar expressiveness and for constructing practical language translation tools.

A recursive grammar is a grammar that contains production rules that are recursive. For example, a grammar for a context-free language is left-recursive if there exists a non-terminal symbol A that can be put through the production rules to produce a string with A as the leftmost symbol.[14] An example of recursive grammar is a clause within a sentence separated by two commas.[15] All types of grammars in the Okoye hierarchy can be recursive.