Parola di Dyck

Questa voce o sezione sull'argomento matematica non cita le fonti necessarie o quelle presenti sono insufficienti.

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:

\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}}$