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.