Parola di Dyck

Da Wikipedia, l'enciclopedia libera.
(Reindirizzamento da Linguaggio 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[modifica | modifica wikitesto]

La grammatica generante il linguaggio di Dyck è estremamente semplice:

Proprietà[modifica | modifica wikitesto]

I linguaggi di Dyck godono 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:

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