Dyck language

This article or the following section is not adequately provided with supporting documents ( e.g. individual evidence ). Information without sufficient evidence could be removed soon. Please help Wikipedia by researching the information and including good evidence.

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

For every natural number , the Dyck language is the word set of correctly bracketed (well-formed) expressions with different pairs of brackets. Inductive can be defined as follows: ${\displaystyle n}$ ${\displaystyle D_{n}}$ ${\displaystyle n}$ ${\displaystyle D_{n}}$

• ${\displaystyle \varepsilon \in D_{n}}$(Where is the empty word .) ${\displaystyle \varepsilon }$
• If so, then also applies . ${\displaystyle v,w\in D_{n}}$ ${\displaystyle vw\in D_{n}}$
• If so, it also applies to everyone . (Where is the -th opening bracket.) ${\displaystyle w\in D_{n}}$ ${\displaystyle \{_{i}w\}_{i}\in D_{n}}$ ${\displaystyle i\in \{1,2,\dotsc ,n\}}$ ${\displaystyle \{_{i}}$ ${\displaystyle i}$

The Dyck language can include the two brackets [,] and (,). Then, for example: ${\displaystyle D_{2}}$

• ${\displaystyle [[(\,)[\,]](\,)]\in \ D_{2}}$
• ${\displaystyle ([\,)]\notin \ D_{2}}$
• ${\displaystyle ))\notin \ D_{2}}$

A word from a Dyck language can be reduced to an empty word by gradually replacing each pair of brackets that appear in the correct order with the empty word . A Dyck word can be represented as a Rutishauser Klammergebirge. The position of the bracket in the word is shown on the abscissa and the respective bracket depth is shown on the ordinate . Dyck languages ​​are deterministically context-free and therefore in particular context-free . However, they are not regular . ${\displaystyle \varepsilon }$

Grammar of the Dyck language : ${\displaystyle D_{2}}$

${\displaystyle S\rightarrow \varepsilon }$

${\displaystyle S\rightarrow SS}$

${\displaystyle S\rightarrow [S]}$

${\displaystyle S\rightarrow (S)}$

For there are productions of the kind . ${\displaystyle D_{n}}$ ${\displaystyle n}$ ${\displaystyle S\rightarrow \{S\}}$