Dyck language

The Dyck languages ​​are in theoretical computer science specific context-free formal languages ​​, ie type 2 languages ​​according to the Chomsky hierarchy. They are named after the mathematician Walther von Dyck.

For every natural number is the Dyck language is the word set of correctly bracketed ( well-formed ) expressions of different pairs of brackets. Induction can be defined as follows:

• (This is the empty word. )
• If, as is also true.
• If, as is also true for all. (This is the -th opening parenthesis. )

The Dyck language, the two pairs of brackets "[]" and include "()". Then, for example:

A word from a Dyck language can be reduced to an empty word by gradually each pair of parentheses occur in the correct sequence is replaced by the empty word. A Dyck word can be represented as a Rutishauser Brace Mountains. The position of the clamp is shown, the respective clip depth in the word, and the ordinate on the abscissa. Dyck languages ​​are deterministic context -free and thus, in particular context-free. However, they are not regular.

Grammar of the Dyck language:

For there are corresponding productions of the kind.

• Compiler
• Theory of formal languages