Formal Grammar

CORE DEFINITION

In formal language theory, a formal grammar is a set of production rules for strings in a formal language. These rules describe how to generate valid strings that conform to the syntax of the language using its alphabet. A grammar does not describe the meaning of strings or what can be done with them in any context—only their form. Formal language theory is a branch of applied mathematics that studies formal grammars and languages. It has wide applications in theoretical computer science, theoretical linguistics, formal semantics, and mathematical logic. A formal grammar is a set of rules for rewriting strings, starting from a 'start symbol'. Therefore, a grammar is usually considered a language generator. However, it can also sometimes serve as the basis for a 'recognizer' (a function in computer science that determines whether a given string belongs to the language or is syntactically incorrect). Formal language theory uses another theory to describe recognizers, namely automata theory. An interesting result in automata theory is that for certain formal languages, no recognizer can be designed.