Parola di Dyck

Da Wikipedia, l'enciclopedia libera.
(Reindirizzamento da Linguaggio di Dyck)
Vai alla navigazione Vai alla ricerca

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[modifica | modifica wikitesto]

La grammatica generante il linguaggio di Dyck è estremamente semplice:

Proprietà[modifica | modifica wikitesto]

Il linguaggio di Dyck gode delle seguenti proprietà:

Esempi[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica