Grammars & Formal Languages

A formal grammar is a finite set of local rewriting rules that can generate an infinite language. Its power comes from separating reusable structural categories—nonterminals—from the terminal symbols that appear in finished words. Derivations describe the rewrite history; parse trees reveal the hierarchical structure that history builds.

The notation used to print a grammar is a separate concern. BNF, ISO EBNF, the EBNF used by W3C specifications, and ABNF are metalanguages with different operator conventions. A reader must first understand the underlying productions, then apply the notation legend of the particular specification.

A grammar is a generator #

For a context-free grammar, each production has the form

$$A\to\alpha, \qquad A\in N,\quad \alpha\in(N\cup\Sigma)^*.$$

If a string of grammar symbols contains $A$, one derivation step may replace that occurrence by $\alpha$:

$$xAy\Rightarrow x\alpha y.$$

The reflexive, transitive closure $\Rightarrow^*$ allows zero or more steps. A sentential form is any string reachable from $S$; the generated language retains only completed terminal strings:

$$L(G)=\{w\in\Sigma^*\mid S\Rightarrow^*w\}.$$

This is different from an automaton's direction of work. A grammar starts with one abstract symbol and expands toward a word; a recognizer starts with a word and decides whether it belongs. The descriptions can characterize the same language, but their mechanisms are not identical.

Derivations record order; parse trees record structure #

Consider a grammar for bracketed lists of zero or more item tokens:

$$\begin{aligned} L &\to [\ O\ ],\\ O &\to \varepsilon\mid I,\\ I &\to \mathtt{item}\mid \mathtt{item},I. \end{aligned}$$

One leftmost derivation of [item,item] is

$$L\Rightarrow[O]\Rightarrow[I] \Rightarrow[\mathtt{item},I] \Rightarrow[\mathtt{item},\mathtt{item}].$$

A leftmost derivation always expands the leftmost nonterminal; a rightmost derivation chooses the rightmost. Those are scheduling policies for constructing a tree. The parse tree itself records which production expanded each nonterminal and preserves the ordered children.

flowchart TD
  L["L"] --> LB["["]
  L --> O["O"]
  L --> RB["]"]
  O --> I1["I"]
  I1 --> A1["item"]
  I1 --> C[","]
  I1 --> I2["I"]
  I2 --> A2["item"]

Reading terminal leaves from left to right gives the yield [item,item]. Several unrestricted derivation sequences can expand independent subtrees in different orders while producing the same tree, so “two derivation sequences” alone is not yet evidence of ambiguity.

The grammar's construction also exposes an invariant: every generated word begins with [, ends with ], and its interior is either empty or alternates an item with zero or more comma–item pairs. A soundness proof follows the productions. A completeness proof works backward: any intended nonempty list has a first item and either stops or has a comma followed by a shorter list.

Ambiguity is competing structure #

The deliberately ambiguous expression grammar

$$E\to E+E\mid E*E\mid \mathtt{id}$$

gives id + id * id two structures:

flowchart LR
  subgraph P1["Parse 1: id + (id * id)"]
    A0["+"] --> A1["id"]
    A0 --> A2["*"]
    A2 --> A3["id"]
    A2 --> A4["id"]
  end
  subgraph P2["Parse 2: (id + id) * id"]
    B0["*"] --> B1["+"]
    B0 --> B4["id"]
    B1 --> B2["id"]
    B1 --> B3["id"]
  end

The terminal sequence is the same, but the root operation—and therefore grouping—is different. A precedence-bearing grammar separates levels:

$$\begin{aligned} \mathit{Expr} &\to \mathit{Expr}+\mathit{Term}\mid\mathit{Term},\\ \mathit{Term} &\to \mathit{Term}*\mathit{Atom}\mid\mathit{Atom},\\ \mathit{Atom} &\to \mathtt{id}\mid(\mathit{Expr}). \end{aligned}$$

Now multiplication is constructed below addition, and the left recursion makes repeated operators group to the left in the structural reading. Showing that this one word has one intended tree demonstrates the repair locally; proving the grammar unambiguous for every word is a stronger induction over expression structure.

Left recursion is also not synonymous with ambiguity. It is a structural form that some parsing strategies cannot handle directly, while other parsers can; ambiguity remains a property of generated parse structure.

Production restrictions form the Chomsky hierarchy #

The grammar types differ by which replacements are permitted. The historical definitions and modern textbook conventions vary around empty-word exceptions, so the convention must be declared rather than inferred.

Each stronger restriction yields a language family contained in the less restricted one. Chomsky's finite-state correspondence proves that type-3 languages are precisely finite-state languages, and his separation result shows that type 2 contains languages not generated by type-3 grammars.

flowchart BT
  R["Type 3 · regular<br/>finite-state memory"] --> C["Type 2 · context-free<br/>recursive tree structure"]
  C --> S["Type 1 · context-sensitive"]
  S --> U["Type 0 · unrestricted"]

The memory labels in this diagram are orientation, not definitions. A full treatment of pushdown, linear-bounded, and Turing-machine recognizers belongs in their own chapters; compressing them into one hierarchy picture would hide their mechanisms.

Right-linear grammars and finite automata are equivalent #

Use the right-linear convention

$$A\to aB, \qquad A\to a,$$

plus a separately declared $S\to\varepsilon$ rule when the language contains the empty word. Other equivalent conventions allow epsilon from accepting-state nonterminals; consistency matters more than punctuation.

Grammar to NFA #

For each nonterminal create one NFA state, and add a fresh accepting state $f$:

• $A\to aB$ becomes $A\xrightarrow{a}B$;
• $A\to a$ becomes $A\xrightarrow{a}f$;
• if the declared convention permits $A\to\varepsilon$, mark $A$ accepting or add an equivalent epsilon path.

The start nonterminal becomes the start state. A derivation emitting $a_1\ldots a_n$ corresponds step for step to a path labeled by those terminals. Induction on the number of productions proves both soundness and completeness.

NFA to grammar #

For each NFA state $q$, create a nonterminal $A_q$. For every transition $p\xrightarrow{a}q$, add

$$A_p\to aA_q.$$

For each accepting state $q$, add $A_q\to\varepsilon$ under this conversion convention. The start state's nonterminal is the grammar start. Induction on path length shows that a labeled path to an accepting state exists exactly when the corresponding terminal derivation exists.

Worked correspondence: words ending in ab #

Consider

$$\begin{aligned} S&\to aS\mid bS\mid aA,\\ A&\to b. \end{aligned}$$

The alternatives $S\to aS$ and $S\to aA$ are the same nondeterministic choice as “keep scanning” versus “guess that this a starts the final suffix.” The conversion produces:

For bbab, the derivation and path align:

$$S\Rightarrow bS\Rightarrow bbS\Rightarrow bbaA\Rightarrow bbab,$$

$$S\xrightarrow{b}S\xrightarrow{b}S\xrightarrow{a}A\xrightarrow{b}f.$$

For baba, every guessed final a either meets the wrong next symbol or finishes before the input does. Correspondingly, no derivation removes every nonterminal while yielding baba.

Recursive grammars express unbounded nesting #

The grammar

$$B\to\varepsilon\mid [B]B$$

generates balanced bracket strings. Each use of [B]B contributes one matched pair: the first $B$ generates the nested interior and the second generates what follows.

Two invariants characterize the intended structure:

1. Every generated word has equally many [ and ] symbols.
2. Every prefix has at least as many [ as ] symbols.

Soundness follows by structural induction on the parse tree. For completeness, take any nonempty balanced word. Its first [ has a matching ]; split the word into the balanced interior and balanced remainder, then apply induction to both.

No finite automaton can recognize exact unbounded balance. Prefixes consisting of $n$ opening brackets require different residual behavior: the suffix of $n$ closing brackets completes exactly the matching depth. By Myhill–Nerode, there are infinitely many distinguishable prefixes.

A finite automaton can approximate the language up to a fixed depth $k$, because it needs only $k+1$ depth states plus overflow/error. The gap is not that finite automata cannot count at all; they cannot retain an unbounded exact count.

BNF, EBNF, and ABNF are metalanguages #

The mathematical grammar and the notation used to serialize it are separate layers. ISO/IEC 14977 standardizes one Extended BNF. The W3C XML specification declares its own EBNF notation, including grouping, alternation, optionality, repetition, and subtraction. RFC 5234 defines ABNF for Internet specifications, including its rule form, repetition syntax, numeric terminals, and incremental alternatives.

The same bracketed-list language can be written several ways, provided each block carries its own legend.

These lines are translations of one intended structure, not a claim that ?, [], quotes, or repetition markers have universal meaning. In ABNF, for example, bracketed elements and repetition are defined by RFC 5234; in W3C's XML grammar, the specification's own notation section governs.

Proving that a grammar describes the intended language #

Testing sample strings can reveal errors but cannot establish equivalence for an infinite language. A reusable proof has two directions:

Soundness #

Show that every production preserves an invariant satisfied by intended words. Induction may be over derivation length or parse-tree structure. For the bracket grammar, every constructor adds a matched outer pair around a balanced interior and concatenates a balanced remainder.

Completeness #

Show that every intended word has a structural decomposition corresponding to some production. Apply induction to the smaller pieces. For a comma-separated list, split off the first item; for balanced brackets, split at the closing bracket matching the first opener.

When a proposed grammar is wrong, seek the shortest witness:

• an extra word generated by the grammar but outside the intended language, or
• a missing word in the intended language that has no derivation.

Shortest witnesses localize the faulty choice because all shorter structures already behave correctly.

Useful static analyses on a grammar #

Three finite fixed-point analyses expose dead structure before parsing begins:

Nullable

A nonterminal is nullable if it derives $\varepsilon$.

Productive

A nonterminal is productive if it derives at least one terminal word.

Reachable

A nonterminal is reachable if some derivation from $S$ contains it.

Compute each set by repeatedly adding nonterminals whose production right sides satisfy the current condition until no set changes. A nonterminal that is unreachable or unproductive cannot participate in any completed start-symbol derivation. Removing it is safe only after that claim is established; deleting a nullable or merely inconvenient symbol can change the language.

Normal forms and parsing algorithms build on these analyses, but their transformations need exact side conditions—especially around $\varepsilon$ and the start symbol. They should not be treated as name-only rewrite recipes.

Diagnostic checklist #

• Are terminals and nonterminals disjoint and visually distinguishable?
• Does every displayed terminal word have all nonterminals eliminated?
• Are $\Rightarrow$ and $\Rightarrow^*$ being used as rewrite relations rather than automaton transitions?
• Are two derivations actually two parse trees, or merely two expansion orders for the same tree?
• Is ambiguity attributed to the grammar rather than automatically to the language?
• Does a claimed right-linear grammar keep the continuing nonterminal consistently on one side?
• Is the empty-word convention stated before translating accepting states?
• Does the grammar-to-automaton proof align one emitted terminal with one transition?
• Is an EBNF/ABNF operator interpreted from the local official legend?
• Do soundness and completeness cover all generated and all intended words, rather than a sample?

The core mental model is structural generation: productions define which trees may be built, and terminal words are their yields. Regular grammars restrict those trees until only finite-state continuation remains; context-free recursion permits unbounded nesting. The notation printed around those rules is important, but it is never a substitute for their semantics.