regular grammar
A grammar of type 3 in the Chomsky hierarchy is called a regular grammar. These forms of grammars are not as efficiently manageable in terms of their complexity, so they do not play a role in the description of programming languages. For practical use, type 3 and type 2, regular and context-free grammars, of the Chomsky hierarchy, which are not so complex, are sufficient.
In natural languages, the grammar associated with the language defines the set of correct sentences allowed in the language. Analogously, programming languages are also described with the help of grammars. Thus not only languages can be described, but also a classification of languages can be made regarding the characteristics essential for the development of programming languages. This leads to a hierarchy of language classes, the so-called Chomsky hierarchy.
Alphabet: An alphabet A is a finite set of characters.
Grammar: A grammar G is a 4-tuple (T,N,P,s). Here denotes:
- T the set of terminal symbols, which are the basic elements of the language,
- N the set of non-terminals,
- P the set of productions of the form a "b, which are used to develop a syntax tree. Each production consists of a left and a right side with respect to a derivation arrow. The right side of a production is derived from the non-terminal on the left side here. Example: Block "BEGIN statement list END;
- s denotes the start symbol of the grammar from which any sentence in a language can be derived,
- V = T(u)N denotes the union set of terminal and non-terminal symbols, and
- V* denotes the strings over V.
Regular Grammar, Type 3 Grammar:
All productions have the form:
These grammars are also called one-way linear, left-linear, and right-linear, respectively.