Regulargrammatiken

Regulargrammatiken, or reguläre Grammatiken in German-language texts, are a class of formal grammars in the Chomsky hierarchy that generate exactly the regular languages. A regular grammar is defined by a finite set of nonterminal symbols, a finite alphabet of terminals, a start symbol, and production rules. In the common right-linear form, all productions have the shape A -> aB or A -> a or A -> ε, where A and B are nonterminals and a is a terminal. Left-linear grammars use the shape A -> Ba or A -> a or ε. A grammar that uses only right-linear or only left-linear productions is called regular.

Regulargrammatiken are expressively equivalent to finite automata: every regular grammar can be transformed into a finite automaton that accepts the same language, and every finite automaton can be converted into a regular grammar. This duality underpins many practical methods, such as using regular expressions to specify patterns and then compiling or converting them into grammars or automata.

Decidability and complexity: membership of a string in the language generated by a regular grammar (or the equivalent automaton) is decidable in time linear in the length of the string; emptiness, finiteness, and equivalence of regular languages are decidable.

Applications: Regulargrammatiken are foundational in lexical analysis and compiler design, where token patterns are specified as regular expressions and implemented as finite automata; they also appear in text processing and formal language theory as a simple, well-understood class of languages.

Limitations: Regulargrammatiken cannot generate certain nested structures, such as matching parentheses or equal-length patterns like a^n b^n, which require more powerful formalisms like context-free grammars.