Regular grammar

A regular grammar is a formal grammar of type 3 of the Chomsky hierarchy. The languages ​​generated by such grammars are called regular languages ​​.

Definition

A regular grammar is a context-free grammar whose production rules satisfy certain further restrictions. There are two different types of constraints, then define the specific regular right and left regular grammars. As one considers the practicalities of handling applications mostly on the right- regular grammars, one often says too short "regular " where you actually " quite regularly " means.

For production rules of regular grammars, the left side may be only one non-terminal symbol. For every regular grammar is also context-free. In addition, the right side may each rule at most one terminal and a nonterminal symbol included. All rules with two symbols on their right sides must have the same order of terminal and nonterminal symbol.

Right Regular grammars

In right regular grammars the right side of a production may be only the empty word, a terminal symbol or a terminal followed by a single nonterminal. Derivations in such grammars that is growing at the right end of a sentence form.

Formally, one can express the condition on the production level of a right regular grammar as:

Stands for the empty word.

Links Regular grammars

In the left regular grammars may be reversed only the empty word, a terminal symbol or a nonterminal followed by a terminal the right side of a production. Here, therefore, extend the derivations the set forms the left side.

Formal see the conditions as follows:

Other spellings

The condition for regular grammars can also be shorter note, by defining the set of valid production rules:

For arbitrary and thus only the following pattern rules are quite regular case allowed:

For the left regular grammars is in lieu of the former pattern, a the following:

Each of the first production is right - or left- regular ( also called right-and left -linear ). A regular grammar must not mix rules according to two patterns for 1.

Regular Languages

A generated by a regular grammar language is called regular language. Always exists at least one regular grammar for each regular language.

The regular languages ​​are proving to be closed under complementation, concatenation, intersection, union, and formation of the clover ash statements.

Each regular language is also a suitable deterministic - described finite-state machine, and accepts a suitable regular expression - and necessarily also by a non-deterministic. Conversely, the languages ​​accepted a deterministic or non-deterministic finite automaton or a regular expression describes, also generated by a suitable regular grammar. Defined by four different formalisms language classes coincide in that the regular languages ​​in a class, them brings its importance.

The classes of the right regular and left regular grammars coincide: for every left regular grammar quite a regular grammar that generates the same language, and vice versa.

Description of the derivation process

If one follows the course of a derivation in a fairly regular grammar, so there are all forms of sentence, which did not yet have a nonterminal symbol, a word from terminals in front, followed by a single nonterminal. Thus, the derived word occurs gradually by adding a terminal symbol on the right side of the initial terminal word and simultaneous change of the final nonterminal.

The following example grammar with regular right part describes the language.

With the following rules:

The word has the following derivation:

This process corresponds to the reading of the word in a finite automaton. There is a corresponding machine, whose non-terminal symbols correspond to the states and where there is a transition in the automaton for each rule. The automaton for the example grammar is shown in the picture.

Swell

• Theory of formal languages