Język Dycka

Krata 14 słów Dycka o długości 8 - [ i ] interpretowana jako góra i dół

W teorii języków formalnych informatyki , matematyki i językoznawstwa słowo Dycka jest zrównoważonym ciągiem nawiasów. Zbiór słów Dyck tworzy język Dyck . Najprostszy, D1, używa tylko dwóch pasujących nawiasów, np. [ i ].

Słowa i język Dycka zostały nazwane na cześć matematyka Walthera von Dycka . Mają zastosowanie w analizowaniu wyrażeń, które muszą mieć poprawnie zagnieżdżoną sekwencję nawiasów, takich jak wyrażenia arytmetyczne lub algebraiczne.

Definicja formalna

Niech ${\ Displaystyle \ Sigma = \ {[,] \}}$ będzie alfabetem składającym się z symboli [ i ]. Niech oznaczają $_$ zamknięcie . Język Dyck jest zdefiniowany jako:

{\ Displaystyle \ {u \ in \ Sigma ^ {*} \ vert {\ tekst {wszystkie przedrostki}} u {\ tekst {zawierają nie więcej] niż ['s}} {\ tekst {i liczba [jest w }}u{\text{ równa się liczbie ]}}\}.}

Gramatyka bezkontekstowa

pomocne może być zdefiniowanie języka Dyck za pomocą gramatyki bezkontekstowej . Język Dyck jest generowany przez gramatykę bezkontekstową z pojedynczym nieterminalnym $S$ , a produkcja:

S \to ε | "[" S "]" S

Oznacza to, że S jest pustym łańcuchem ( $ε$ ) lub jest „[”, elementem języka Dyck, pasującym „]” i elementem języka Dyck.

Alternatywną gramatykę bezkontekstową dla języka Dyck podaje produkcja:

S \to ("[" S "]") *

Oznacza to, że S to zero lub więcej wystąpień kombinacji „[”, elementu języka Dyck i pasującego „]”, gdzie wiele elementów języka Dyck po prawej stronie produkcji może różnić się od nawzajem.

Alternatywna definicja

$na$ innych kontekstach zamiast tego pomocne może być zdefiniowanie języka Dyck poprzez podzielenie klasy równoważności w następujący sposób Dla dowolnego elementu długości ${\ Displaystyle | u |}$ ${\ Displaystyle u \ in \ Sigma ^ {*}}$ , definiujemy funkcje częściowe ${\ Displaystyle \ operatorname {wstaw}: \ Sigma ^ {*} \ razy \ mathbb {N} \ rightarrow \ Sigma ^ {* }}$ i ${\ Displaystyle \ nazwa operatora {usuń}: \ Sigma ^ {*} \ razy \ mathbb {N} \ rightarrow \ Sigma ^ {*}}$ przez

{\ Displaystyle \ operatorname {wstaw} (u, j)}

jest

{\ Displaystyle u}

z "

{\ Displaystyle []}

"wstawionym w pozycję

{\ Displaystyle j}

{\ Displaystyle \ operatorname {usuń} (u, j)}

jest

{\ Displaystyle u}

z "

{\ Displaystyle []}

" usunięto z pozycji

{\ Displaystyle j}

$_$ założeniu dla ${\ Displaystyle j> | u |}$ i ${\ Displaystyle \ operatorname {usuń} (u, j)}$ jest niezdefiniowane, jeśli ${\ Displaystyle j> | u | -2}$ . Definiujemy relację równoważności na ${\ Displaystyle$ $\ Sigma ^ {*}}$ w następujący sposób: dla elementów $*}}$ mamy ${\ Displaystyle (a, b) \ in R}$ wtedy i tylko wtedy, gdy istnieje sekwencja zero lub więcej zastosowań insert $\ displaystyle \ operatorname {insert}}$ i ${\ displaystyle \ nazwa operatora {usuń}}$ funkcje zaczynające się na ${\ displaystyle a}$ i kończące się na ${\ displaystyle b}$ . To, że dozwolona jest sekwencja operacji zerowych $odpowiada$ za zwrotność . Symetria wynika z obserwacji, że dowolną skończoną sekwencję zastosowań $do$ $łańcucha$ za pomocą skończonej sekwencji zastosowań . Przechodniość wynika z definicji.

Relacja równoważności dzieli język na klasy równoważności. ${\ Displaystyle \ Sigma ^ {*}}$ Jeśli przyjmiemy $znaków ,$ $\ displaystyle \ epsilon}$ język odpowiadający klasie równoważności językiem Dyck ϵ

Nieruchomości

Język Dyck jest zamknięty w ramach operacji konkatenacji .
Traktując jako monoid algebraiczny w $^ {*}}$ , widzimy, że struktura monoidu przenosi się na iloraz , czego Σ $Sigma$ monoid składniowy języka Dyck . Klasa zostanie oznaczona jako ${\ Displaystyle \ operatorname {Cl} (\ epsilon$ $)$ .
Monoid składniowy języka Dyck nie jest przemienny : ${\ Displaystyle u = \ operatorname {Cl} ([)}$ i ${\ Displaystyle v = \ operatorname {Cl } (])}$ wtedy ${\ Displaystyle uv = \ operatorname {Cl} ([]) = 1 \ neq \ operatorname {Cl} (][)=vu}$ .
${\ Displaystyle \ Sigma ^ {*}/$ zapisem, ale ani ${\ displaystyle$ $u},$ ani ${\ displaystyle v} nie$ odwracalne w .
Monoid składniowy języka Dyck jest izomorficzny z bicykliczną półgrupą dzięki właściwościom i ${\ Displaystyle \ operatorname {Cl} ([)}$ i ${\ Displaystyle \ operatorname {Cl} (])}$ opisane powyżej.
Zgodnie z twierdzeniem o reprezentacji Chomsky'ego – Schützenbergera każdy język bezkontekstowy jest homomorficznym obrazem przecięcia jakiegoś języka regularnego z językiem Dycka na jednym lub kilku rodzajach par nawiasów.
Język Dyck z dwoma różnymi typami nawiasów można rozpoznać w klasie złożoności ${\ displaystyle TC ^ {0}}$ .
Liczba różnych słów Dycka z dokładnie $n$ parami nawiasów i $k$ najbardziej wewnętrznymi parami (mianowicie podłańcuch ${\ Displaystyle [\ ]}$ ) to liczba Narayana ${\ Displaystyle \ operatorname {N} (n,k)}$ .
Liczba różnych słów Dycka z dokładnie $n$ parami nawiasów to $n$ -ta liczba katalońska $\ displaystyle C_ {n}}$ . Zauważ, że język Dycka słów z $n$ parami nawiasów jest równy sumie, po wszystkich możliwych $k$ , języków Dycka słów z $n$ par nawiasów z $k$ najbardziej wewnętrznymi parami , jak zdefiniowano w poprzednim punkcie. Ponieważ $k$ może mieścić się w zakresie od 0 do $n$ , otrzymujemy następującą równość, która rzeczywiście zachodzi:

{\ Displaystyle C_ {n} = \ suma _ {k = 1} ^ {n} \ operatorname {N} (n, k)}

Przykłady

Relację równoważności możemy zdefiniować w języku Dycka. ${\ displaystyle$ $\ mathcal {D}}}$ . u ${\ Displaystyle u, v \ in {\ mathcal {D}}}$ mamy $Displaystyle (u, v) \ in L}$ wtedy i tylko wtedy, gdy ${\ Displaystyle | u | = | v|}$ , tj. ${\ displaystyle u}$ i ${\ displaystyle v}$ mają tę samą długość. Ta relacja dzieli język Dycka: ${\ Displaystyle {\ mathcal {D}} / L = \ {{\ mathcal {D}} _ {0}, {\ mathcal { D}}_{1},\ldotki \}}$ . re ${\ Displaystyle {\ mathcal {D}} = {\ mathcal {D}} _ {0} \ puchar {\ mathcal {D$ gdzie ${\ Displaystyle {\ mathcal {D}} _ {n} = \ {u \ in {\ mathcal {D}} \ mid | u | = n \}}$ . $n$ , że jest puste dla nieparzystego $\ displaystyle n}$ .

Po wprowadzeniu słów Dycka o długości $.$ możemy wprowadzić na nich związek Dla każdego $\ Displaystyle$ relację $S_ {n}}$ $Displaystyle {\ mathcal {D}} _ {n}$ n ; u ${\ Displaystyle u, v \ w {\ mathcal {D}} _ {n}}$ mamy $w S_ {n }}$ $można$ i tylko wtedy, gdy osiągnąć z $zamian$ odpowiednich . $wystąpienie$ zamiana w słowie ”. Dla każdej $\ Displaystyle S_ {n}}$ $displaystyle$ ${\ mathcal {D}} _ {n}}$ { \ \ jest częściowo zamówiony zestaw . Relacja jest zwrotna $}$ ponieważ pusta sekwencja odpowiednich zamian prowadzi $do$ u $u$ . Przechodniość następuje, ponieważ możemy rozszerzyć sekwencję odpowiednich zamian, która prowadzi $do$ $}$ { $,$ $displaystyle v}$ łącząc ją z sekwencją odpowiednich zamian, która prowadzi do $w}$ sekwencję, która prowadzi do $displaystyle$ . Aby zobaczyć, że jest również antysymetryczny , wprowadzamy funkcję pomocniczą ${\ mathcal {D}} _ {n} \ rightarrow \ mathbb {N}} zdefiniowane$ $:$ ${\ displaystyle u}$ suma wszystkich przedrostków ${\ displaystyle v}$ u :

{\ Displaystyle \ sigma _ {n} (u) = \ suma _ {vw =u}{\Duża (}({\text{liczba [ w }}v)-({\text{liczba ] w }}v){\Duża )}}

Poniższa tabela ilustruje, że $jest$ ściśle monotoniczna odniesieniu do właściwych zamian

Ścisła monotoniczność ${\ Displaystyle \ sigma _ {n}}$
σ ${\ Displaystyle \ sigma _ {n} (u)$	${\ displaystyle P.}$	${\ displaystyle P-1}$	${\ displaystyle P.}$	${\ displaystyle Q}$
${\ displaystyle u}$	${\ displaystyle \ ldots}$	]	[	${\ displaystyle \ ldots}$
${\ displaystyle u'}$	${\ displaystyle \ ldots}$	[	]	${\ displaystyle \ ldots}$
σ $u')}$	${\ displaystyle P.}$	${\ displaystyle P + 1}$	${\ displaystyle P.}$	${\ displaystyle Q}$
Różnica sum częściowych	0	2	0	0

Stąd ${\ Displaystyle \ sigma _ {n} (u ') - \ sigma _ {n} (u) = 2> 0}$ więc ${\ Displaystyle \ sigma _ {n} (u) <\ sigma _ {n} (u')},$ gdy istnieje właściwa zamiana, która przenosi ${\ displaystyle u}$ do ${\ styl wyświetlania u'}$ . Teraz, jeśli założymy, że zarówno ${\ Displaystyle (u, v), (v, u) \ w S_ {n}}$ i ${\ Displaystyle u \ neq v}$ $,$ to istnieją niepuste sekwencje odpowiednich zamian, takie $brane$ pod i odwrotnie. $)}$ ${\ Displaystyle \ sigma _ {n} (u) <\ sigma _ {n} (v) <\ sigma _ {n} ($ u co jest bezsensowne. Dlatego $_$ $=$ są _ $_$ _ ${\ displaystyle u = v}$ , stąd ${\ displaystyle S_ {n}}$ jest antysymetryczny.

Częściowo uporządkowany zestaw jest pokazany na ilustracji $towarzyszącej$ wstępowi, jeśli zinterpretujemy [ jako wzrost i ] jako

Uogólnienia

Istnieją warianty języka Dyck z wieloma ogranicznikami, np. D2 na alfabecie „(”, „)”, „[” i „]”. Słowa takiego języka to te, które są dobrze ujęte w nawiasy dla wszystkich ograniczników, tj. można czytać słowo od lewej do prawej, przesunąć każdy otwierający ogranicznik na stosie, a za każdym razem, gdy dojdziemy do ogranicznika zamykającego, musimy być w stanie aby zdjąć pasujący ogranicznik otwierający ze szczytu stosu. (Powyższy algorytm liczenia nie uogólnia).

Zobacz też

Notatki