Parola di Dyck
# Parola di Dyck

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. 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:

    $\Sigma =\{\ x,y\ \}$
    $S\to xSyS|\varepsilon$

## 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:

    $\Sigma ={\Big \\ (,),[,],\{,\}\ {\Big \}}$

## Dimostrazione

Dimostriamo che le parole di Dyck di lunghezza $2n$ sono ${\binom {2n}{n}}-{\binom {2n}{n+1}}$, ovvero pari all'$n$-esimo numero di Catalan.

Per semplicità di notazione, vediamo la dimostrazione nel caso $n=4$; la dimostrazione generale è del tutto analoga.

Le parole formate da $4$ lettere $X$ e da $4$ lettere $Y$ sono in tutto ${\binom {8}{4}}$ contando anche le parole che non sono di Dyck. Denotiamo con $P(4,4)$ questo insieme.

Contiamo adesso quante sono le parole di $P(4,4)$ che non sono di Dyck. Denotiamo con $N(4,4)$ l'insieme delle parole in $P(4,4)$ che non sono di Dyck. Scriviamo ogni parola che non è di Dyck usando il colore rosso per la prima lettera $Y$ 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 ${\color {Red}Y}$ rossa ci sono tante lettere $X$ quante lettere $Y$. Scriviamo ad esempio

    $XY{\color {Red}Y}{\color {Orange}XXYXY},\quad XXXYYY{\color {Red}Y}{\color {Orange}X},\quad {\color {Red}Y}{\color {Orange}XYXYXYX},\quad XYXY{\color {Red}Y}{\color {Orange}XXY},\quad \dots$

Osserviamo che in ogni parola che non è di Dyck il numero di ${\color {Orange}X}$ colorate di arancio supera di una unità il numero di ${\color {Orange}Y}$ colorate di arancio.

Denotiamo con $P(3,5)$ l'insieme delle parole formate da $3$ lettere $X$ e da $5$ lettere $Y$. Esiste una biiiezione

    $N(4,4)\longrightarrow P(3,5)$

definita semplicemente sostituendo ogni ${\color {Orange}X}$ arancio con una ${\color {midnightblue}Y}$ e sostituendo ogni ${\color {Orange}Y}$ arancio con una ${\color {midnightblue}X}$. Questa biiezione contiene ad esempio le freccette

${\begin{aligned}XY{\color {Red}Y}{\color {Orange}XXYXY}&\longmapsto XY{\color {Red}Y}{\color {midnightblue}YYXYX}\\[.7ex]XXXYYY{\color {Red}Y}{\color {Orange}X}&\longmapsto XXXYYY{\color {Red}Y}{\color {midnightblue}Y}\\[.7ex]{\color {Red}Y}{\color {Orange}XYXYXYX}&\longmapsto {\color {Red}Y}{\color {midnightblue}YXYXYXY}\end{aligned}}$

Ora il numero di parole di Dyck di lunghezza $8$ è

    $\left\vert P(4,4)\right\vert -\left\vert N(4,4)\right\vert =\left\vert P(4,4)\right\vert -\left\vert P(3,5)\right\vert ={\binom {8}{4}}-{\binom {8}{5}}$

come volevasi.

