Dyck-taal
![](http://upload.wikimedia.org/wikipedia/commons/thumb/0/01/Dyck_lattice_D4.svg/260px-Dyck_lattice_D4.svg.png)
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 ).
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 het alfabet zijn dat bestaat uit de symbolen [ en ]. Laat de Kleene-ster aanduiden. De Dyck-taal wordt gedefinieerd als:
Eigenschappen
- De Dyck-taal is gesloten onder de werking van concatenatie.
- Door te behandelen als een algebraïsche monoïde onder concatenatie zien we dat de monoïdestructuur overgaat op het quotiënt , resulterend in de syntactische monoïde van de Dyck-taal. De klasse wordt aangegeven met .
- De syntactische monoïde van de Dyck-taal is niet commutatief: als en dan .
- Met de bovenstaande notatie, maar geen van beide noch zijn omkeerbaar in .
- De syntactische monoïde van de Dyck-taal is isomorf met de bicyclische semigroep vanwege de eigenschappen van en 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 .
- Het aantal verschillende Dyck-woorden met precies n paar haakjes is het n-de Catalan-getal . 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:
Bron
- Dit artikel of een eerdere versie ervan is een (gedeeltelijke) vertaling van het artikel Dyck language op de Engelstalige Wikipedia, dat onder de licentie Creative Commons Naamsvermelding/Gelijk delen valt. Zie de bewerkingsgeschiedenis aldaar.