Indietro

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

                                     

1. Grammatica

La grammatica generante il linguaggio di Dyck è estremamente semplice:

Σ = { x, y } {\displaystyle \Sigma =\{\ x,y\ \}} S → x S y S | ε {\displaystyle S\to xSyS|\varepsilon }
                                     

2. Proprietà

I linguaggi di Dyck godono delle seguenti proprietà:

  • è anticommutativo;
  • è un linguaggio ricorsivo, infinito ma non circolare;
  • è chiuso secondo loperazione di concatenazione;
  • 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.
                                     

3. Esempi

Ad esempio, le parole di Dyck di lunghezza 6 sono:

invece queste non lo sono:

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:

Linsieme dei simboli di un linguaggio di Dyck può essere anche esteso, ad esempio:

Σ = {,\{,\}\ {\Big \}}}