Limbaj Dyck

În informatică teoretică , în special în teoria limbajului , limbile Dyck sunt limbi formale individuale. Un limbaj Dyck este setul de cuvinte bine parantezate , peste un alfabet finit de paranteze de deschidere și de închidere. De exemplu, pe perechea de paranteze formată din ' (' și ' )' , cuvântul ' (()) ()' este un cuvânt bine parantizat, în timp ce cuvântul ' ()) (' nu este.

Limbajele Dyck joacă un rol important în informatica teoretică pentru a caracteriza limbajele algebrice . Teorema Schützenberger Chomsky afirmă că de fapt orice limbaj algebric este imaginea cu un morfism alfabetice de intersecție a unei limbi Deic cu un limbaj rațional .

Limbile lui Dyck au fost numite după matematicianul german Walther von Dyck .

Definiție formală

Intuitiv, un cuvânt este bine parantizat , numit și cuvântul lui Dyck , dacă poate fi redus la cuvântul gol prin eliminarea succesivă a perechilor adiacente de paranteze de același tip. De exemplu, pe alfabetul format din , cuvântul este parantezat deoarece ${\ displaystyle (, [,),]}$ ${\ displaystyle ([() []]) ()}$

{\ displaystyle ([() [\,]]) () \ to ([[\,]]) () \ to ([\,]) () \ to () () \ to () \ to \ varepsilon}

Să dăm definiția formală a unui cuvânt Dyck. Fie un alfabet, fie o copie disjunctă a . Pe setul de cuvinte pe , definim următoarea relație: $LA$ ${\ displaystyle {\ bar {A}} = \ {{\ bar {a}} \ mid a \ în A \}}$ $LA$ $LA$ ${\ displaystyle (A \ cup {\ bar {A}}) ^ {*}}$ ${\ displaystyle A \ cup {\ bar {A}}}$

{\ displaystyle w \ to w '}

dacă există o factorizare cum ar fi , cu .

{\ displaystyle w = xa {\ bar {a}} y}

{\ displaystyle w '= xy}

a \ in A

Reducerea Dyck este închiderea tranzitivă a acestei relații. Un cuvânt al lui Dyck este un cuvânt care se reduce la cuvântul gol . Limba Dyck pe setul de cuvinte Dyck. $\ varepsilon$ ${\ displaystyle A \ cup {\ bar {A}}}$

Reducerea Dyck este un sistem de rescriere confluent . Congruența Dyck este închiderea reflexivă, simetrică și tranzitivă a relației.

Proprietăți

Concatenarea a două cuvinte Dyck este încă un cuvânt Dyck, deci limbajul lui Dyck este un submonoid al monoidului liber . ${\ displaystyle (A \ cup {\ bar {A}}) ^ {*}}$
Un cuvânt Dyck primar este un cuvânt Dyck care nu este o concatenare a mai multor cuvinte Dyck. Notăm sau setul de cuvinte primare Dyck sau limbajul lui Dyck. De asemenea, întâlnim notația atunci când alfabetul conține litere. ${\ displaystyle D_ {A}}$ $D$ ${\ displaystyle D_ {A} ^ {*}}$ ${\ displaystyle D ^ {*}}$ ${\ displaystyle D_ {n} ^ {*}}$ $nu$
Setul de cuvinte Dyck prime este un cod bifix (adică un prefix și un sufix). Monoizii sunt, prin urmare, submonoizi liberi . ${\ displaystyle D_ {A} ^ {*}}$
Limbile Dyck și limbile Dyck prime sunt limbaje algebrice deterministe. Iată o gramatică: Variabila generează limbajul Dyck , variabila generează limbajul primelor cuvinte Dyck .
${\ displaystyle {\ begin {array} {rcl} S & \ to & TS \ mid \ varepsilon \\ T & \ to & aS {\ bar {a}} \ quad (a \ in A) \ end {array} }}$
$S$ ${\ displaystyle D_ {A} ^ {*}}$ $T$ ${\ displaystyle D_ {A}}$
O altă gramatică întâlnită frecvent este: Variabila generează limbajul lui Dyck , dar gramatica este ambiguă .
${\ displaystyle {\ begin {array} {rcl} S & \ to & SS \ mid \ varepsilon \\ S & \ to & aS {\ bar {a}} \ quad (a \ in A) \ end {array} }}$
$S$ ${\ displaystyle D_ {A} ^ {*}}$
Teorema Chomsky-Schützenberger afirmă că orice limbaj algebric este o imagine homomorfă a intersecției unui limbaj Dyck cu un limbaj rațional.
Această teoremă poate fi rafinată după cum urmează: orice limbaj algebric este o imagine homomorfă a intersecției unui limbaj rațional și imaginea omomorfă inversă a limbajului lui Dyck pe două perechi de paranteze: unde și sunt morfisme și este un limbaj rațional. $THE$
${\ displaystyle L = h (K \ cap g ^ {- 1} (D_ {2} ^ {*}))}$
$h$ $g$ $K$
În mod echivalent, această afirmație înseamnă că orice limbaj algebric este o imagine prin transducție rațională , sau că limbajul este un generator al conului rațional al limbajelor algebrice. $D_ {2} ^ {*}$ $D_ {2} ^ {*}$
Limbajul lui Dyck pe două perechi de paranteze aparține clasei de complexitate TC 0 (ro) .
Cuvintele lui Dyck au multe proprietăți și caracterizări combinatorii. Numărul de cuvinte Dyck pe o pereche de paranteze de lungime este egal cu numărul catalan . $2n$ $C_ {n}$
Monoidul sintactic al limbajului lui Dyck este monoidul biciclic .

Limbi Dyck bilaterale

Intuitiv, un cuvânt Dyck pe două fețe este un cuvânt bine format de simboluri și inversele lor care se simplifică atunci când sunt adiacente, ca într-un grup. Aici, este folosit în schimb pentru a simboliza reversul literei . Limbile Dyck pe două fețe, formate din cuvinte Dyck pe două fețe, sunt legate de definiția grupurilor libere . ${\ displaystyle a ^ {- 1} a = 1}$ $\ bar a$ $La$

Fie un alfabet, fie o copie disjunctă a . Aici, copia scrisorii este văzută ca reversul său formal. Pe setul de cuvinte pe , definim o relație de reducere după cum urmează: $LA$ ${\ displaystyle {\ bar {A}} = \ {{\ bar {a}} \ mid a \ în A \}}$ $LA$ $LA$ $\ bar a$ $La$ ${\ displaystyle (A \ cup {\ bar {A}}) ^ {*}}$ ${\ displaystyle A \ cup {\ bar {A}}}$

${\ displaystyle w \ to w '}$ dacă există o factorizare sau astfel încât , cu . Reducerea Dyck pe două fețe este închiderea tranzitivă a acestei relații. ${\ displaystyle w = xa {\ bar {a}} y}$ ${\ displaystyle w = x {\ bar {a}} ay}$ ${\ displaystyle w '= xy}$ $a \ in A$

De exemplu, avem

{\ displaystyle {\ bar {a}} aa {\ bar {a}} \ to a {\ bar {a}} \ to \ varepsilon}

Un cuvânt Dyck pe două fețe este un cuvânt care se reduce la cuvântul gol . Relația de rescriere definită mai sus este confluentă și orice cuvânt este redus la un cuvânt ireductibil (adică care nu conține niciun factor sau un singur factor ) . Setul de cuvinte ireductibile este un limbaj rațional . El este în bijuterie cu grupul liber de pe . $\ varepsilon$ ${\ displaystyle a {\ bar {a}}}$ ${\ displaystyle {\ bar {a}} a}$ $LA$

Limba Dyck cu două fețe pe setul de cuvinte Dyck cu două fețe. ${\ displaystyle A \ cup {\ bar {A}}}$

Proprietăți

Limbajele Dyck bilaterale sunt algebrice. Iată o gramatică:

{\ displaystyle {\ begin {array} {rcl} S & \ to & TS \ mid \ varepsilon \\ T & \ to & aS {\ bar {a}} \ quad (a \ in A) \\ T & \ to & {\ bar {a}} Sa \ quad (a \ in A) \ end {array}}}

Această gramatică este ambiguă. De exemplu, cuvântul are următoarele două derivări la stânga : ${\ displaystyle a {\ bar {a}} a {\ bar {a}}}$

{\ displaystyle {\ begin {array} {l} S \ to TS \ to aS {\ bar {a}} S \ to a {\ bar {a}} S \ to a {\ bar {a}} TS \ la o {\ bar {a}} aS {\ bar {a}} S \ la o {\ bar {a}} a {\ bar {a}} S \ la {{bar {a}} a {\ bar {a}} \\ S \ to TS \ to aS {\ bar {a}} S \ to aTS {\ bar {a}} S \ to a {\ bar {a}} Sa {\ bar {a} } S \ to a {\ bar {a}} a {\ bar {a}} S \ to a {\ bar {a}} a {\ bar {a}} \ end {array}}}

Există gramatici lipsite de ambiguitate pentru limbile Dyck pe două fețe. Iată una:

{\ displaystyle {\ begin {array} {rcl} S & \ to & cS_ {c} {\ bar {c}} S \ quad (c \ in A \ cup {\ bar {A}}) \\ S_ { c} & \ to & bS_ {b} {\ bar {b}} S_ {c} \ quad (b, c \ în A \ cup {\ bar {A}}, b \ neq {\ bar {c}} ) \\ S & \ to & \ varepsilon \\ S_ {c} & \ to & \ varepsilon \ quad (c \ in A \ cup {\ bar {A}}) \ end {array}}}

În cazul în care alfabetul este compus dintr-o singură literă , această gramatică se reduce la: $LA$ $La$

{\ displaystyle {\ begin {array} {rcl} S & \ to & aS_ {a} {\ bar {a}} S \ mid {\ bar {a}} S _ {\ bar {a}} aS \ mid \ varepsilon \ \ S_ {a} & \ to & aS_ {a} {\ bar {a}} S_ {a} \ mid \ varepsilon \\ S _ {\ bar {a}} & \ to & {\ bar { a}} S_ {\ bar {a}} aS _ {\ bar {a}} \ mid \ varepsilon \ end {array}}}

Teorema Chomsky-Schützenberger rămâne valabilă atunci când limbile Dyck sunt înlocuite de limbile Dyck bilaterale.

Referințe

Olivier Carton , Limbaje formale, calculabilitate și complexitate ,2008[ detaliul ediției ] ( citiți online )
Jean-Michel Autebert , Limbi algebrice , Masson,1987, 278 p. ( ISBN 978-2-225-81087-9 )
(ro) Wilhelm Magnus , Abraham Karrass și Donald Solitar , Combinatorial Group Theory. Prezentări de grupuri în termeni de generatori și relații , Dover Publications ,2004, 444 p. ( ISBN 0-486-43830-9 , citit online )Reeditare a celei de-a doua ediții, 1976

Note și referințe

Terminologia „bilateral” nu este frecventă: în engleză, se folosește adesea „ cuvinte Dyck pe două fețe ”. Jacques Labelle ( Quebec Annals of Mathematical Sciences vol. 17, n o 1, 1993) folosește în mod explicit termenul „cu două fețe” Jacques Sakarovitch numit „cuvânt Dyck” cuvintele pe două fețe și cuvintele „cuvântul lui Shamir” Dyck. Matematicienii, în teoria grupurilor combinatorii, cunosc doar cuvinte bilaterale și omit adjectivul.

Articole similare