Parola di Dyck
![Niente fonti!](http://upload.wikimedia.org/wikipedia/commons/thumb/6/64/Question_book-4.svg/45px-Question_book-4.svg.png)
Nella teoria dei linguaggi formali, una parola di Dyck è una stringa consistente di n simboli X ed n simboli Y tale che, preso comunque un segmento iniziale della stringa, esso non contenga più simboli Y che simboli X.[1] Queste parole sono alla base dei linguaggi con parentesi ben formati e ricorsivi.
Il linguaggio composto da tutte le parole di Dyck è chiamato linguaggio di Dyck.
Grammatica
La grammatica generante il linguaggio di Dyck è estremamente semplice:
Proprietà
Il linguaggio di Dyck gode delle seguenti proprietà:
- è chiuso secondo l'operazione di concatenazione;
- è un linguaggio ricorsivo, infinito ma non circolare;
- è anticommutativo;
- il numero delle parole di Dyck aventi lunghezza 2n (com'è stato provato da Désiré André nel 1887) corrisponde all'n-esimo numero di Catalan.
Esempi
Ad esempio, le parole di Dyck di lunghezza 6 sono:
xxxyyy | xyxxyy | xyxyxy | xxyyxy | xxyxyy |
invece queste non lo sono:
yyyxxx | yxyyxx | xyyxxy | yyxxyx | xyxyyx |
Definendo il simbolo x come la parentesi aperta ed il simbolo y come la parentesi chiusa, allora una parola di Dyck corrisponde ad un insieme di parentesi che sono disposte in maniera completa (ad ogni parentesi aperta ne corrisponde una chiusa) e logicamente coerente (le parentesi sono correttamente annidate e non vi è mai una parentesi chiusa senza che prima ci sia la relativa parentesi aperta). Con questa definizione, la serie delle parole di Dyck di lunghezza 6 diventa:
((())) | ()(()) | ()()() | (())() | (()()) |
L'insieme dei simboli di un linguaggio di Dyck può essere anche esteso, ad esempio:
Dimostrazione
Dimostriamo che le parole di Dyck di lunghezza sono , ovvero pari all'-esimo numero di Catalan.
Per semplicità di notazione, vediamo la dimostrazione nel caso ; la dimostrazione generale è del tutto analoga.
Le parole formate da lettere e da lettere sono in tutto contando anche le parole che non sono di Dyck. Denotiamo con questo insieme.
Contiamo adesso quante sono le parole di che non sono di Dyck. Denotiamo con l'insieme delle parole in che non sono di Dyck. Scriviamo ogni parola che non è di Dyck usando il colore rosso per la prima lettera della stringa dalla quale si capisce che non è una parola di Dyck, e usando il colore arancio per tutte le lettere a destra di quella in rosso. In questo modo in ogni parola che non è di Dyck a sinistra della rossa ci sono tante lettere quante lettere . Scriviamo ad esempio
Osserviamo che in ogni parola che non è di Dyck il numero di colorate di arancio supera di una unità il numero di colorate di arancio.
Denotiamo con l'insieme delle parole formate da lettere e da lettere . Esiste una biiiezione
definita semplicemente sostituendo ogni arancio con una e sostituendo ogni arancio con una . Questa biiezione contiene ad esempio le freccette
Ora il numero di parole di Dyck di lunghezza è
come volevasi.
Note
- ^ Giulia Zaccarelli, I CAMMINI DI DYCK - Tesi di laurea in teoria dei numeri (PDF), Università di Bologna, 2016, p. 8.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/af/Crystal128-kmplot.svg/25px-Crystal128-kmplot.svg.png)