formalgrammar

A formal grammar specifies the syntax of a language through production rules that replace symbols. It is described as a four-tuple (V, Σ, R, S): V is the set of nonterminals, Σ the terminals, R the rules, and S the start symbol. Terminals appear in strings; nonterminals are placeholders used during derivation.

Rules in R define how symbols can be replaced by other symbols or strings of symbols. A derivation is a sequence of rule applications starting from S that yields a string over Σ. The strings that can be generated from S by zero or more applications of rules form the language described by the grammar. A parse tree or derivation tree represents the structure of a derivation visually.

Formal grammars are classified in the Chomsky hierarchy. Type-3 grammars, or regular grammars, have rules limited to right- or left-linear forms and generate regular languages. Type-2 grammars, or context-free grammars, have a single nonterminal on the left-hand side and generate context-free languages. Type-1 grammars, or context-sensitive grammars, allow rules that do not decrease the length of strings in general. Type-0 grammars, or unrestricted grammars, place no restrictions and generate the recursively enumerable languages.

Each level of the hierarchy corresponds to a machine: regular languages by finite automata, context-free by pushdown automata, context-sensitive by linear bounded automata, and recursively enumerable by Turing machines.

Formal grammars are foundational in computer science and linguistics. They underlie the design of programming languages and compilers, enabling syntax analysis and parsing. They also support formal specifications in verification and protocol design, and are often written in EBNF.

History: The field originated with Noam Chomsky's work in the 1950s and 1960s, linking language structure to rule-based grammars; it has since become central to theoretical CS and language processing.