język Dyck

W informatyce teoretycznej , zwłaszcza w teorii języka , języki Dyck są jednostkami języków formalnych . Język Dyck to zestaw dobrze ujętych w nawiasy słów , nad skończonym alfabetem otwierających i zamykających nawiasów. Na przykład, w parze nawiasów utworzonej przez ' (' i ' )' , słowo ' (()) ()' jest słowem dobrze umieszczonym w nawiasach, podczas gdy słowo ' ()) (' nie jest).

Języki Dyck odgrywają ważną rolę w informatyce teoretycznej w charakteryzowaniu języków algebraicznych . Twierdzenie Schützenberger Chomsky twierdzi w istocie, że każdy język algebraiczny jest obraz z alfabetycznej morfizmu od skrzyżowania języka Dyck z racjonalnym języku .

Języki Dycka zostały nazwane na cześć niemieckiego matematyka Walthera von Dycka .

Formalna definicja

Intuicyjnie, słowo jest dobrze umieszczone w nawiasach , zwane także słowem Dycka , jeśli można je zredukować do pustego słowa, usuwając kolejno sąsiednie pary nawiasów tego samego typu. Na przykład w alfabecie utworzonym przez , słowo jest umieszczone w nawiasach, ponieważ ${\ styl wyświetlania (, [,),]}$ ${\ styl wyświetlania ([() []]) ()}$

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

Podajmy formalną definicję słowa Dyck. Albo alfabet, albo rozłączna kopia . Na zbiorze słów on definiujemy następującą relację: $DO$ ${\ displaystyle {\ bar {A}} = \ {{\ bar {a}} \ mid a \ w A \}}$ $DO$ $DO$ ${\ displaystyle (A \ filiżanka {\ bar {A}}) ^ {*}}$ ${\ displaystyle A \ filiżanka {\ bar {A}}}$

{\ styl wyświetlania w \ do w '}

jeśli istnieje rozkład na czynniki, taki jak , z .

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

{\ styl wyświetlania w '= xy}

a \ w A

Redukcja Dyck jest przechodni zamknięcie tej relacji. Słowo Dyck jest słowem, które sprowadza się do pustym słowem . Język Dyck na zbiorze słów Dyck. $\ varepsilon$ ${\ displaystyle A \ filiżanka {\ bar {A}}}$

Redukcja Dycka to konfluentny system przepisywania . Kongruencja Dycka jest zwrotnym, symetrycznym i przechodnim zamknięciem relacji.

Nieruchomości

Konkatenacja dwóch słów Dycka jest nadal słowem Dyck, więc język Dycka jest podmonoidem wolnego monoidu . ${\ displaystyle (A \ filiżanka {\ bar {A}}) ^ {*}}$
Pierwsze słowo Dyck to słowo Dyck, które nie jest konkatenacją wielu słów Dyck. Oznaczamy lub zbiór pierwszych słów Dycka i lub język Dycka. Z notacją spotykamy się również wtedy, gdy alfabet zawiera litery. ${\ styl wyświetlania D_ {A}}$ $D$ ${\ Displaystyle D_ {A} ^ {*}}$ ${\ styl wyświetlania D ^ {*}}$ ${\ styl wyświetlania D_ {n} ^ {*}}$ $nie$
Zbiór pierwszych słów Dycka to kod bifix (tj. kod prefiksu i sufiksu ). Monoidy są zatem wolnymi submonoidami . ${\ Displaystyle D_ {A} ^ {*}}$
Języki Dyck i pierwsze języki Dyck są deterministycznymi językami algebraicznymi . Oto gramatyka: Zmienna generuje język Dyck , zmienna generuje język pierwszych słów Dyck .
${\ displaystyle {\ begin {array} {rcl} S & \ do & TS \ mid \ varepsilon \\ T & \ do & aS {\ bar {a}} \ quad (a \ w A) \ end {array} }}$
$S$ ${\ Displaystyle D_ {A} ^ {*}}$ $T$ ${\ styl wyświetlania D_ {A}}$
Inna często spotykana gramatyka to: zmienna generuje język Dycka , ale gramatyka jest niejednoznaczna .
${\ displaystyle {\ początek {tablica} {rcl} S & \ do & SS \ mid \ varepsilon \\ S & \ do & aS {\ bar {a}} \ quad (a \ w A) \ end {tablica} }}$
$S$ ${\ Displaystyle D_ {A} ^ {*}}$
Twierdzenie Chomsky'ego – Schützenbergera mówi, że każdy język algebraiczny jest homomorficznym obrazem przecięcia języka Dycka z językiem racjonalnym.
Twierdzenie to można doprecyzować w następujący sposób: każdy język algebraiczny jest homomorficznym obrazem przecięcia języka wymiernego i odwrotnym homomorficznym obrazem języka Dycka na dwóch parach nawiasów: gdzie i są morfizmami i jest językiem racjonalnym. $TEN$
${\ displaystyle L = h (K \ czapka g ^ {-1} (D_ {2} ^ {*}))}$
$h$ $g$ $K$
Równoważnie to stwierdzenie oznacza, że każdy język algebraiczny jest obrazem poprzez racjonalną transdukcję lub że język jest generatorem racjonalnego stożka języków algebraicznych. $D_ {2} ^ {*}$ $D_ {2} ^ {*}$
Język Dycka na dwóch parach nawiasów należy do klasy złożoności TC 0 (en) .
Słowa Dycka mają wiele właściwości i charakterystyk kombinatorycznych. Liczba słów Dycka w parze nawiasów długości jest równa liczbie katalońskiej . $2n$ $C_ {n}$
Monoidem składniowym języka Dycka jest monoid bicykliczny .

Dwustronne języki Dyck

Intuicyjnie, dwustronne słowo Dyck jest dobrze uformowanym słowem symboli i ich odwrotności, które upraszczają się, gdy sąsiadują ze sobą, na przykład w grupie. Tutaj jest używany zamiast symbolizować rewers litery . Dwustronne języki Dyck, utworzone z dwustronnych słów Dyck, są związane z definicją wolnych grup . ${\ displaystyle a ^ {- 1} a = 1}$ $\ pasek a$ $W celu$

Albo alfabet, albo rozłączna kopia . Tutaj kopia listu jest jego formalnym rewersem. Na zbiorze słów on definiujemy relację redukcji w następujący sposób: $DO$ ${\ displaystyle {\ bar {A}} = \ {{\ bar {a}} \ mid a \ w A \}}$ $DO$ $DO$ $\ pasek a$ $W celu$ ${\ displaystyle (A \ filiżanka {\ bar {A}}) ^ {*}}$ ${\ displaystyle A \ filiżanka {\ bar {A}}}$

${\ styl wyświetlania w \ do w '}$ jeśli istnieje faktoryzacja lub takie, że , z . Dwustronna redukcja Dycka jest przejściowym zamknięciem tej relacji. ${\ displaystyle w = xa {\ bar {a}} y}$ ${\ styl wyświetlania w = x {\ bar {a}} ay}$ ${\ styl wyświetlania w '= xy}$ $a \ w A$

Na przykład mamy

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

Dwu- stronne Dyck słowo jest słowem, które sprowadza się do pustego słowa . Relacja przepisywania zdefiniowana powyżej jest konfluentna, a każde słowo jest zredukowane do słowa nieredukowalnego (to znaczy nie zawierającego żadnego lub pojedynczego czynnika ) . Zbiór nieredukowalnych słów jest językiem racjonalnym . Jest w bijekcji z wolną grupą na . $\ varepsilon$ ${\ displaystyle a {\ bar {a}}}$ ${\ displaystyle {\ bar {a}} a}$ $DO$

Język Dyck dwustronny na planie Dyck słowy dwustronnego. ${\ displaystyle A \ filiżanka {\ bar {A}}}$

Nieruchomości

Dwustronne języki Dyck są algebraiczne. Oto gramatyka:

{\ displaystyle {\ zacząć {tablica} {rcl} S & \ do & TS \ mid \ varepsilon \\ T & \ do & aS {\ bar {a}} \ quad (a \ w A) \\ T & \ to & {\ bar {a}} Sa \ quad (a \ in A) \ end {array}}}

Ta gramatyka jest niejednoznaczna. Na przykład słowo ma następujące dwie lewe derywacje : ${\ displaystyle a {\ bar {a}} a {\ bar {a}}}$

{\ displaystyle {\ begin {array} {l} S \ do TS \ do aS {\ bar {a}} S \ do a {\ bar {a}} S \ do {\ bar {a}} TS \ do a {\ bar {a}} aS {\ bar {a}} S \ do a {\ bar {a}} a {\ bar {a}} S \ do a {\ bar {a}} a {\ bar {a}} \\ S \ do TS \ do aS {\ bar {a}} S \ do aTS {\ bar {a}} S \ do a {\ bar {a}} Sa {\ bar {a} } S \ do a {\ bar {a}} a {\ bar {a}} S \ do a {\ bar {a}} a {\ bar {a}} \ end {tablica}}}

Istnieją jednoznaczne gramatyki dla dwustronnych języków Dyck. Tutaj jest jeden:

{\ displaystyle {\ zacząć {tablica} {rcl} S & \ do & cS_ {c} {\ bar {c}} S \ quad (c \ w A \ filiżanka {\ bar {A}}) \\ S_ { c} & \ do & bS_ {b} {\ bar {b}} S_ {c} \ quad (b, c \ in A \ cup {\ bar {A}}, b \ neq {\ bar {c}} ) \\ S & \ do & \ varepsilon \\ S_ {c} & \ do & \ varepsilon \ quad (c \ in A \ cup {\ bar {A}}) \ end {array}}}

W przypadku, gdy alfabet składa się z jednej litery , gramatyka ta sprowadza się do: $DO$ $W celu$

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

Twierdzenie Chomsky'ego – Schützenbergera pozostaje aktualne, gdy języki Dyck zostaną zastąpione przez języki Dyck bilateralne.

Bibliografia

Olivier Carton , Języki formalne, obliczalność i złożoność ,2008[ szczegóły wydania ] ( przeczytaj online )
Jean-Michel Autebert , Języki algebraiczne , Masson,1987, 278 s. ( ISBN 978-2-225-81087-9 )
(en) Wilhelm Magnus , Abraham Karrass i Donald Solitar , Kombinatoryczna teoria grup. Prezentacje grup pod kątem generatorów i relacji , Dover Publikacje ,2004, 444 s. ( ISBN 0-486-43830-9 , czytaj online )Przedruk drugiego wydania, 1976

Uwagi i referencje

Terminologia „dwustronny” nie jest częste: po angielsku, jeden często używa „ dwustronny Dyck słowa ”. Jacques Labelle ( Quebec, Annals of Sciences matematyczne vol. 17, n o 1, 1993), wyraźnie stosuje się termin "dwustronny" Jacques Sakarovitch zwane "Dyck słowo" dwustronnego słowa i "słowo Shamir" słów Dyck. Matematycy w kombinatorycznej teorii grup znają tylko wyrazy dwustronne i pomijają przymiotnik.

Powiązane artykuły