Dyck-taal

In de theorie van formele talen van de informatica, wiskunde en taalkunde is een Dyck-woord een uitgebalanceerde reeks haakjes. De verzameling Dyck-woorden vormt een Dyck-taal. De eenvoudigste, D1, gebruikt slechts twee overeenkomende haakjes, bijvoorbeeld ( en ).

Raster van de 14 Dyck-woorden met een lengte van 8 - [ en ] geïnterpreteerd als op en neer

Dyck-woorden en -taal zijn vernoemd naar de wiskundige Walther von Dyck. Ze hebben toepassingen bij het ontleden van uitdrukkingen die een correct geneste reeks haakjes moeten hebben, zoals rekenkundige of algebraïsche uitdrukkingen.

Formele definitie

Laat $\Sigma =\{[,]\}$ het alfabet zijn dat bestaat uit de symbolen [ en ]. Laat $\Sigma ^{*}$ de Kleene-ster aanduiden. De Dyck-taal wordt gedefinieerd als:

$\{u\in \Sigma ^{*}\vert {\text{ alle prefixen van }}u{\text{ bevatten niet meer ] dan [}}{\text{ en het aantal [ in }}u{\text{ is gelijk aan het aantal ]}}\}.$

Eigenschappen

• De Dyck-taal is gesloten onder de werking van concatenatie.

• Door $\Sigma ^{*}$ te behandelen als een algebraïsche monoïde onder concatenatie zien we dat de monoïdestructuur overgaat op het quotiënt $\Sigma ^{*}/R$, resulterend in de syntactische monoïde van de Dyck-taal. De klasse $\operatorname {Cl} (\epsilon )$ wordt aangegeven met $1$.

• De syntactische monoïde van de Dyck-taal is niet commutatief: als $u=\operatorname {Cl} ([)$ en $v=\operatorname {Cl} (])$ dan $uv=\operatorname {Cl} ([])=1\neq \operatorname {Cl} (][)=vu$.

• Met de bovenstaande notatie, $uv=1$ maar geen van beide $u$ noch $v$ zijn omkeerbaar in $\Sigma ^{*}/R$.

• De syntactische monoïde van de Dyck-taal is isomorf met de bicyclische semigroep vanwege de eigenschappen van $\operatorname {Cl} ([)$ en $\operatorname {Cl} (])$ hierboven omschreven.

• Volgens de representatiestelling van Chomsky-Schützenberger is elke contextvrije taal een homomorf beeld van de doorsnede van een reguliere taal met een Dyck-taal op een of meer soorten haakjesparen.

• Het aantal verschillende Dyck-woorden met precies n paren haakjes en k binnenste paren (namelijk de subtekenreeks $[\ ]$) is het Narayana-getal $\operatorname {N} (n,k)$.

• Het aantal verschillende Dyck-woorden met precies n paar haakjes is het n-de Catalan-getal $C_{n}$. Merk op dat de Dyck-taal van woorden met n haakjesparen gelijk is aan de unie, over alle mogelijke k, van de Dyck-talen van woorden met n haakjesparen met k binnenste paren, zoals gedefinieerd in het vorige punt. Omdat k kan variëren van 0 tot n, verkrijgen we de volgende gelijkheid, die inderdaad geldt:

$C_{n}=\sum _{k=1}^{n}\operatorname {N} (n,k)$