Dyck jazyk

V teoretické informatice , zejména v teorii jazyků , jsou Dyckovy jazyky jednotlivci formálních jazyků . Jazyk Dyck je množina slov v závorkách , přes konečnou abecedu úvodních a závěrečných závorek. Například na dvojici závorek tvořených znaky „ (“ a „ )“ je slovo „ (()) ()“ slovo v dobře závorce, zatímco slovo „ ()) (“ není).

Dyckovy jazyky hrají důležitou roli v teoretické informatice pro charakterizaci algebraických jazyků . Teorém Schützenberger Chomsky říká, v tom smyslu, že jakákoli algebraické jazyk je obraz s abecedním morfismu z průsečíku jednoho jazyka Dyck s racionálním jazykem .

Dyckovy jazyky byly pojmenovány po německém matematikovi Waltherovi von Dyckovi .

Formální definice

Intuitivně je slovo dobře v závorkách , také nazývané Dyckovo slovo , pokud ho lze redukovat na prázdné slovo postupným odstraňováním sousedních dvojic závorek stejného typu. Například v abecedě tvořené písmenem je slovo uvedeno v závorkách, protože ${\ displaystyle (, [,),]}$ ${\ displaystyle ([() []]) ()}$

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

Uveďme formální definici Dyckova slova. Buď abeceda, nebo disjunktní kopie . Na množině slov o definujeme následující vztah: $NA$ ${\ displaystyle {\ bar {A}} = \ {{\ bar {a}} \ uprostřed \ v A \}}$ $NA$ $NA$ ${\ displaystyle (A \ cup {\ bar {A}}) ^ {*}}$ ${\ displaystyle A \ cup {\ bar {A}}}$

{\ displaystyle w \ to w '}

pokud existuje faktorizace jako , s .

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

{\ displaystyle w '= xy}

a \ v A

Snížení Dyck je tranzitivní uzávěr tohoto vztahu. Slovo Dyck je slovo, který se redukuje na prázdné slovo . Jazyk Dyck na množině slov Dyck. $\ varepsilon$ ${\ displaystyle A \ cup {\ bar {A}}}$

Dyckova redukce je konfluentní systém přepisování . Dyckova kongruence je reflexivní, symetrické a přechodné uzavření vztahu.

Vlastnosti

Zřetězení dvou Dyckových slov je stále Dyckovým slovem, takže Dyckův jazyk je submonoidem volného monoidu . ${\ displaystyle (A \ cup {\ bar {A}}) ^ {*}}$
Hlavní slovo Dyck je slovo Dyck, které není spojením několika slov Dyck. Označujeme nebo množinu hlavních Dyckových slov a nebo Dyckův jazyk. Setkáváme se také se zápisem, když abeceda obsahuje písmena. ${\ displaystyle D_ {A}}$ $D$ ${\ displaystyle D_ {A} ^ {*}}$ ${\ displaystyle D ^ {*}}$ ${\ displaystyle D_ {n} ^ {*}}$ $ne$
Sada hlavních slov Dyck je kód bifix (tj. Kód předpony a přípony). Monoidy jsou tedy bezplatné submonoidy . ${\ displaystyle D_ {A} ^ {*}}$
Dyckovy jazyky a nejlepší dyckovské jazyky jsou deterministické algebraické jazyky . Tady je gramatika: Proměnná generuje jazyk Dyck , proměnná generuje jazyk prvních slov Dyck .
${\ displaystyle {\ begin {array} {rcl} S & \ to & TS \ mid \ varepsilon \\ T & \ to & aS {\ bar {a}} \ quad (a \ v A) \ end {pole} }}$
$S$ ${\ displaystyle D_ {A} ^ {*}}$ $T$ ${\ displaystyle D_ {A}}$
Další často se vyskytující gramatika: Proměnná generuje Dyckův jazyk , ale gramatika je nejednoznačná .
${\ displaystyle {\ begin {pole} {rcl} S & \ to & SS \ mid \ varepsilon \\ S & \ to & aS {\ bar {a}} \ quad (a \ v A) \ end {pole} }}$
$S$ ${\ displaystyle D_ {A} ^ {*}}$
Věta Chomsky-Schützenberger uvádí, že jakýkoli algebraický jazyk je homomorfní obraz průniku jazyka Dyck s jazykem racionálním.
Tuto větu lze upřesnit následovně: jakýkoli algebraický jazyk je homomorfní obraz průniku racionálního jazyka a inverzní homomorfní obraz Dyckova jazyka na dvou párech závorek: kde a jsou morfismy a je jazykem racionálním. $THE$
${\ displaystyle L = h (K \ cap g ^ {- 1} (D_ {2} ^ {*}))}$
$h$ $G$ $K.$
Ekvivalentně toto tvrzení znamená, že jakýkoli algebraický jazyk je obrazem prostřednictvím racionální transdukce nebo že tento jazyk je generátorem racionálního kuželu algebraických jazyků. $D_ {2} ^ {*}$ $D_ {2} ^ {*}$
Dyckův jazyk na dvou párech závorek patří do třídy složitosti TC 0 (en) .
Dyckova slova mají mnoho kombinačních vlastností a charakterizací. Počet slov Dyck na dvojici dlouhých závorek se rovná katalánskému číslu . $2n$ $C_ {n}$
Syntaktický monoid Dyckova jazyka je bicyklický monoid .

Bilaterální Dyckovy jazyky

Intuitivně je dvoustranné Dyckovo slovo dobře vytvořené slovo symbolů a jejich inverzí, které se zjednodušují, když sousedí, jako ve skupině. Zde se místo toho používá k symbolizaci zadní strany písmene . Oboustranné Dyckovy jazyky, vytvořené z oboustranných Dyckových slov, souvisí s definicí volných skupin . ${\ displaystyle a ^ {- 1} a = 1}$ $\ bar a$ $Na$

Buď abeceda, nebo disjunktní kopie . Zde je kopie dopisu považována za formální opak. Na množině slov dále definujeme redukční vztah následujícím způsobem: $NA$ ${\ displaystyle {\ bar {A}} = \ {{\ bar {a}} \ uprostřed \ v A \}}$ $NA$ $NA$ $\ bar a$ $Na$ ${\ displaystyle (A \ cup {\ bar {A}}) ^ {*}}$ ${\ displaystyle A \ cup {\ bar {A}}}$

${\ displaystyle w \ to w '}$ pokud existuje faktorizace nebo taková , s . Oboustranná Dyckova redukce je přechodným uzavřením tohoto vztahu. ${\ displaystyle w = xa {\ bar {a}} y}$ ${\ displaystyle w = x {\ bar {a}} ay}$ ${\ displaystyle w '= xy}$ $a \ v A$

Například máme

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

Dvou- jednostranný Dyck slovo je slovo, které redukuje na prázdné slovo . Relační relace definovaná výše je splývající a jakékoli slovo je redukováno na neredukovatelné slovo (tj. Neobsahuje žádný nebo jediný faktor ) . Sada neredukovatelných slov je racionální jazyk . Je v bijekci s volnou skupinou . $\ varepsilon$ ${\ displaystyle a {\ bar {a}}}$ ${\ displaystyle {\ bar {a}} a}$ $NA$

Jazyk Dyck oboustranné na množině Dyck slov oboustranných. ${\ displaystyle A \ cup {\ bar {A}}}$

Vlastnosti

Bilaterální Dyckovy jazyky jsou algebraické. Zde je gramatika:

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

Tato gramatika je nejednoznačná. Například slovo má následující dvě derivace vlevo : ${\ displaystyle a {\ bar {a}} a {\ bar {a}}}$

{\ displaystyle {\ begin {pole} {l} S \ k TS \ k aS {\ bar {a}} S \ k {\ bar {a}} S \ k {\ bar {a}} TS \ do {\ bar {a}} aS {\ bar {a}} S \ do {\ bar {a}} a {\ bar {a}} S \ do {\ bar {a}} a {\ bar {a}} \\ S \ na TS \ na aS {\ bar {a}} S \ na aTS {\ bar {a}} S \ na {\ bar {a}} Sa {\ bar {a} } S \ k {\ bar {a}} a {\ bar {a}} S \ k {\ bar {a}} a {\ bar {a}} \ end {pole}}}

Existují jednoznačné gramatiky pro oboustranné jazyky Dyck. Tady je jeden:

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

V případě, že se abeceda skládá z jednoho písmene , je tato gramatika redukována na: $NA$ $Na$

{\ 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 {pole}}}

Věta Chomsky-Schützenberger zůstává v platnosti, i když jsou dyckovské jazyky nahrazeny bilaterálními dyckovými jazyky.

Reference

Olivier Carton , Formální jazyky, vypočítatelnost a složitost ,2008[ detail vydání ] ( číst online )
Jean-Michel Autebert , algebraické jazyky , Masson,1987, 278 s. ( ISBN 978-2-225-81087-9 )
(en) Wilhelm Magnus , Abraham Karrass a Donald Solitar , teorie kombinatorické skupiny. Prezentace skupin z hlediska generátorů a vztahů , Dover Publications ,2004, 444 s. ( ISBN 0-486-43830-9 , číst online )Dotisk druhého vydání, 1976

Poznámky a odkazy

Terminologie „bilaterální“ není častá: v angličtině se často používá „ oboustranná Dyckova slova “. Jacques Labelle ( Quebec Annals of matematické vědy vol. 17, n o 1, 1993) výslovně používá termín "dvoustranný" Jacques Sakarovitch názvem "Dyck slovo" oboustranného slova a "slovo Shamir" slova Dyck. Matematici v kombinatorické grupové teorii znají pouze bilaterální slova a adjektivum vynechávají.

Související články