Dyck sprog

I teoretisk datalogi , især i sprog teori , de Dyck-sprog er formelle sprog individer. Et Dyck-sprog er et sæt af ord med godt parentes over et endeligt alfabet med åbne og lukke parenteser. For eksempel på parret i parentes dannet af ' (' og ' )' er ordet ' (()) ()' et godt parentes ord, mens ordet ' ()) (' ikke er.

Dyck-sprog spiller en vigtig rolle i teoretisk datalogi for at karakterisere algebraiske sprog . Den sætning Schützenbergers Chomsky hedder i, at enhver algebraisk sprog er det billede med et alfabetisk morphism af skæringspunktet af et Dyck sprog med en rationel sprog .

Dyck's sprog blev opkaldt efter den tyske matematiker Walther von Dyck .

Formel definition

Intuitivt er et ord godt parenteseret , også kaldet Dyck's ord , hvis det kan reduceres til det tomme ord ved successivt at fjerne tilstødende par parenteser af samme type. F.eks. Er ordet i alfabetet dannet af parentes, fordi ${\ displaystyle (, [,),]}$ ${\ displaystyle ([() []]) ()}$

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

Lad os give den formelle definition af et Dyck-ord. Enten et alfabet og enten en uensartet kopi af . På sæt af ord på definerer vi følgende relation: $TIL$ ${\ displaystyle {\ bar {A}} = \ {{\ bar {a}} \ mid a \ in A \}}$ $TIL$ $TIL$ ${\ displaystyle (A \ cup {\ bar {A}}) ^ {*}}$ ${\ displaystyle A \ cup {\ bar {A}}}$

{\ displaystyle w \ to w '}

hvis der findes en faktorisering som f.eks . med .

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

{\ displaystyle w '= xy}

a \ i A

Den reduktion Dyck er den transitive lukning af denne relation. Et ord af Dyck er et ord, der reduceres til det tomme ord . Den Dyck sprog på det sæt af Dyck ord. $\ varepsilon$ ${\ displaystyle A \ cup {\ bar {A}}}$

Dyck-reduktion er et sammenflydende omskrivningssystem . Dyck-kongruens er den refleksive, symmetriske og transitive lukning af forholdet.

Ejendomme

Sammenkædningen af to Dyck-ord er stadig et Dyck-ord, så Dyck's sprog er en submonoid af det frie monoid . ${\ displaystyle (A \ cup {\ bar {A}}) ^ {*}}$
Et primært Dyck- ord er et Dyck-ord, der ikke er en sammenkædning af flere Dyck-ord. Vi betegner eller sæt af primære Dyck-ord og eller Dyck's sprog. Vi møder også notationen, når alfabetet indeholder bogstaver. ${\ displaystyle D_ {A}}$ $D$ ${\ displaystyle D_ {A} ^ {*}}$ ${\ displaystyle D ^ {*}}$ ${\ displaystyle D_ {n} ^ {*}}$ $ikke$
Sættet med primære Dyck-ord er en bifix-kode (dvs. et præfiks og en suffiks- kode ). Monoider er derfor gratis submonoider . ${\ displaystyle D_ {A} ^ {*}}$
Dyck-sprog og primære Dyck- sprog er deterministiske algebraiske sprog . Her er en grammatik: Variablen genererer sproget for Dyck , variablen genererer sproget for de første Dyck-ord .
${\ displaystyle {\ begin {array} {rcl} S & \ til & TS \ mid \ varepsilon \\ T & \ til & aS {\ bar {a}} \ quad (a \ i A) \ end {array} }}$
$S$ ${\ displaystyle D_ {A} ^ {*}}$ $T$ ${\ displaystyle D_ {A}}$
En anden ofte opstået grammatik er: Variablen genererer Dyck's sprog , men grammatikken er tvetydig .
${\ displaystyle {\ begin {array} {rcl} S & \ til & SS \ mid \ varepsilon \\ S & \ til & aS {\ bar {a}} \ quad (a \ i A) \ end {array} }}$
$S$ ${\ displaystyle D_ {A} ^ {*}}$
The Chomsky-Schützenberger sætning siger, at ethvert algebraisk sprog er et homomorft billede af skæringspunktet mellem et Dyck-sprog og et rationelt sprog.
Denne sætning kan raffineres som følger: ethvert algebraisk sprog er et homomorft billede af skæringspunktet mellem et rationelt sprog og det omvendte homomorfe billede af Dyck's sprog på to par parenteser: hvor og er morfismer og er en sprogrationel. $DET$
${\ displaystyle L = h (K \ cap g ^ {- 1} (D_ {2} ^ {*}))}$
$h$ $g$ $K$
Tilsvarende betyder denne erklæring, at ethvert algebraisk sprog er et billede gennem rationel transduktion , eller at sproget er en generator for den rationelle kegle af algebraiske sprog. $D_ {2} ^ {*}$ $D_ {2} ^ {*}$
Dyck's sprog på to par parenteser hører til kompleksitetsklassen TC 0 (en) .
Dycks ord har mange kombinatoriske egenskaber og karakteriseringer. Antallet af Dyck-ord i et par parenteser er lig med det catalanske tal . $2n$ $C_ {n}$
Den syntaktiske monoid af Dyck's sprog er den bicykliske monoid .

Bilaterale Dyck-sprog

Intuitivt er et tosidet Dyck-ord et velformet ord af symboler og deres inverser, der forenkler, når de er tilstødende, som i en gruppe. Her bruges det i stedet for at symbolisere det modsatte af brevet . To-sidede Dyck-sprog, dannet af to-sidede Dyck-ord, er relateret til definitionen af frie grupper . ${\ displaystyle a ^ {- 1} a = 1}$ $\ bar a$ $Til$

Enten et alfabet og enten en uensartet kopi af . Her ses kopien af brevet som dets formelle omvendte. På sæt af ord på definerer vi en reduktionsforhold som følger: $TIL$ ${\ displaystyle {\ bar {A}} = \ {{\ bar {a}} \ mid a \ in A \}}$ $TIL$ $TIL$ $\ bar a$ $Til$ ${\ displaystyle (A \ cup {\ bar {A}}) ^ {*}}$ ${\ displaystyle A \ cup {\ bar {A}}}$

${\ displaystyle w \ to w '}$ hvis der er en faktorisering eller sådan , med . Den tosidede Dyck-reduktion er den midlertidige lukning af dette forhold. ${\ displaystyle w = xa {\ bar {a}} y}$ ${\ displaystyle w = x {\ bar {a}} ay}$ ${\ displaystyle w '= xy}$ $a \ i A$

For eksempel har vi det

{\ displaystyle {\ bar {a}} aa {\ bar {a}} \ til en {\ bar {a}} \ til \ varepsilon}

Et tosidet Dyck-ord er et ord, der koger ned til det tomme ord . Omskrivningsforholdet defineret ovenfor er sammenflydende, og ethvert ord reduceres til et irreducerbart ord (dvs. indeholder ingen eller en enkelt faktor ) . Sættet af irreducible ord er et rationelt sprog . Han er i forbindelse med den gratis gruppe på . $\ varepsilon$ ${\ displaystyle a {\ bar {a}}}$ ${\ displaystyle {\ bar {a}} a}$ $TIL$

Det sprog Dyck to-sidet på det sæt af Dyck ord tosidede. ${\ displaystyle A \ cup {\ bar {A}}}$

Ejendomme

Bilaterale Dyck-sprog er algebraisk. Her er en grammatik:

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

Denne grammatik er tvetydig. For eksempel har ordet følgende to venstre afledninger : ${\ displaystyle a {\ bar {a}} a {\ bar {a}}}$

{\ displaystyle {\ begin {array} {l} S \ til TS \ til aS {\ bar {a}} S \ til en {\ bar {a}} S \ til en {\ bar {a}} TS \ til en {\ bar {a}} aS {\ bar {a}} S \ til en {\ bar {a}} en {\ bar {a}} S \ til en {\ bar {a}} en {\ bjælke {a}} \\ S \ til TS \ til aS {\ bar {a}} S \ til aTS {\ bar {a}} S \ til en {\ bar {a}} Sa {\ bar {a} } S \ til en {\ bar {a}} en {\ bar {a}} S \ til en {\ bar {a}} en {\ bar {a}} \ end {array}}}

Der er entydige grammatikker for tosidede Dyck-sprog. Her er en:

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

I det tilfælde hvor alfabetet består af et enkelt bogstav , reduceres denne grammatik til: $TIL$ $Til$

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

Chomsky-Schützenberger-sætningen forbliver gyldig, når Dyck-sprog erstattes af bilaterale Dyck-sprog.

Referencer

Olivier Carton , Formelle sprog, beregningsevne og kompleksitet ,2008[ udgave af udgaven ] ( læs online )
Jean-Michel Autebert , algebraiske sprog , Masson,1987, 278 s. ( ISBN 978-2-225-81087-9 )
(en) Wilhelm Magnus , Abraham Karrass og Donald Solitar , Combinatorial Group Theory. Præsentationer af grupper med hensyn til generatorer og relationer , Dover Publications ,2004, 444 s. ( ISBN 0-486-43830-9 , læs online )Genoptryk af anden udgave, 1976

Noter og referencer

Terminologien "bilateral" er ikke hyppig: på engelsk bruger man ofte " tosidede Dyck-ord ". Jacques Labelle ( Quebec Annals of Mathematical Sciences bind 17, nr . 1, 1993) bruger udtrykkeligt udtrykket "tosidet" Jacques Sakarovitch kaldet "Dyck-ord" de to-sidede ord og "ord af Shamir" -ord Dyck. Matematikere kender i kombinatorisk gruppeteori kun bilaterale ord og udelader adjektivet.

Relaterede artikler