Dyck språk

Gitter av de 14 Dyck-orden med längden 8 - [ och ] tolkas som upp och ner

I teorin om formella språk inom datavetenskap , matematik och lingvistik är ett Dyck-ord en balanserad sträng av parenteser. Uppsättningen av Dyck-ord bildar ett Dyck-språk . Den enklaste, D1, använder bara två matchande parenteser, t.ex. [ och ].

Dyck ord och språk är uppkallade efter matematikern Walther von Dyck . De har applikationer för att analysera uttryck som måste ha en korrekt kapslad sekvens av hakparenteser, såsom aritmetiska eller algebraiska uttryck.

Formell definition

Låt $\Sigma =\{[,]\}$ vara alfabetet som består av symbolerna [ och ]. Låt $\Sigma ^{*}$ beteckna dess Kleene-stängning . Dyckspråket definieras som :

\{u\in \Sigma ^{*}\vert {\text{ alla prefix för }}u{\text{ innehåller inte fler ]:n än [s}}{\text{ och antalet [s i }}u{\text{ är lika med antalet ]s}}\}.

Kontextfri grammatik

Det kan vara till hjälp att definiera Dyck-språket via en kontextfri grammatik i vissa situationer. Dyck-språket genereras av den kontextfria grammatiken med ett enda icke-terminalt $S$ , och produktionen:

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

Det vill säga, S är antingen den tomma strängen ( $ε$ ) eller är "[", ett element i Dyck-språket, det matchande "]" och ett element i Dyck-språket.

En alternativ kontextfri grammatik för Dyck-språket ges av produktionen:

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

Det vill säga, S är noll eller fler förekomster av kombinationen av "[", ett element i Dyck-språket och ett matchande "]", där flera element i Dyck-språket på höger sida av produktionen är fria att skilja sig från varandra.

Alternativ definition

I ytterligare andra sammanhang kan det istället vara till hjälp att definiera Dyck-språket genom att dela upp $\Sigma ^{*}$ i ekvivalensklasser, enligt följande. För alla element $u\in \Sigma ^{*}$ av längd $|u|$ , vi definierar delfunktioner $\operatorname {insert} :\Sigma ^{*}\times \mathbb {N} \rightarrow \Sigma ^{* }$ och $\operatorname {delete} :\Sigma ^{*}\times \mathbb {N} \rightarrow \Sigma ^{*}$ av

\operatorname {insert} (u,j)

är

u

med "

[]

" infogat i

{\displaystyle j}:

e positionen

\operatorname {delete} (u,j)

är

u

med "

[]

" borttagen från

{\displaystyle j}:

e positionen

med den förståelsen att $\operatorname {insert} (u,j)$ är odefinierat för $j>|u|$ och $\operatorname {delete} (u,j)$ är odefinierat om $j>|u|-2$ . Vi definierar en ekvivalensrelation $R$ på $\Sigma ^{*}$ enligt följande: för element $a,b\in \Sigma ^{*}$ vi har $(a,b)\in R$ om och bara om det finns en sekvens av noll eller fler tillämpningar av $\operatorname {insert}$ och ${\ displaystyle \operatorname {delete} }$ funktioner som börjar med $a$ och slutar med $b$ . Att sekvensen av nolloperationer tillåts står för reflexiviteten hos R $\displaystyle R}$ . Symmetri följer av observationen att varje ändlig sekvens av applikationer av $\operatorname {insert}$ till en sträng kan ångras med en ändlig sekvens av applikationer av $\operatorname {delete}$ . Transitivitet framgår tydligt av definitionen.

Ekvivalensrelationen delar upp språket $\Sigma ^{*}$ i ekvivalensklasser. Om vi tar ${\displaystyle \epsilon } för att beteckna den tomma strängen, så$ kallas språket som motsvarar ekvivalensklassen $\operatorname {Cl} (\epsilon )$ Dyck-språket .

Egenskaper

Dyck-språket är stängt under driften av sammanlänkning .
Genom att behandla $\Sigma ^{*}$ som en algebraisk monoid under konkatenering ser vi att monoidstrukturen överförs till kvoten $\Sigma ^{*}/R$ , vilket resulterar i syntaktisk monoid av Dyck-språket . Klassen $\operatorname {Cl} (\epsilon )$ kommer att betecknas $1$ .
Den syntaktiska monoiden för Dyck-språket är inte kommutativ : om $u=\operatörsnamn {Cl} ([)$ och $v=\operatörsnamn {Cl } (])$ sedan $uv=\operatörsnamn {Cl} ([])=1\neq \operatörsnamn {Cl} (][)=vu$ .
Med notationen ovan är $uv=1$ men varken $u$ eller $v$ är inverterbara i $\Sigma ^{*}/R$ .
Den syntaktiska monoiden i Dyck-språket är isomorf till den bicykliska semigruppen på grund av egenskaperna hos $\operatorname {Cl} ([)$ och $\operatorname {Cl} (])$ som beskrivs ovan.
Enligt Chomsky-Schützenbergers representationsteorem är vilket sammanhangsfritt språk som helst en homomorfisk bild av skärningspunkten mellan något reguljärt språk och ett Dyck-språk på en eller flera typer av parantes.
Dyck-språket med två distinkta typer av parenteser kan kännas igen i komplexitetsklassen T $\displaystyle TC^{0}}$ .
Antalet distinkta Dyck-ord med exakt $n$ par parenteser och $k$ innersta par (dvs. delsträngen $[\ ]$ ) är Narayana-talet $\operatorname {N} (n,k)$ .
Antalet distinkta Dyck-ord med exakt $n$ par parenteser är det $n$ -te katalanska talet $C_{n}$ . Lägg märke till att Dyck-språket för ord med $n$ parentespar är lika med föreningen, över alla möjliga $k$ , av Dyck-språken av ord med $n$ parentespar med $k$ innersta par , som definierats i föregående punkt. Eftersom $k$ kan sträcka sig från 0 till $n$ får vi följande likhet, vilket faktiskt gäller:

C_{n}=\summa _{k=1}^{n}\operatörsnamn {N} (n,k)

Exempel

Vi kan definiera en ekvivalensrelation $L$ på Dyck-språket ${\mathcal {D}}$ . För $u,v\in {\mathcal {D}}$ har vi $(u,v)\in L$ if and only if $|u|=|v|$ , dvs $u$ och $v$ har samma längd. Denna relation delar upp Dyck-språket: ${\mathcal {D}}/L=\{{\mathcal {D}}_{0},{\mathcal { D}}_{1},\ldots \}$ . Vi har ${\mathcal {D}}={\mathcal {D}}_{0}\cup {\mathcal {D} }_{2}\cup {\mathcal {D}}_{4}\cup \ldots =\bigcup _{n=0}^{\infty }{\mathcal {D}}_{n}$ där ${\mathcal {D}}_{n}=\{u\in {\mathcal {D}}\mid |u|=n\}$ . Observera att ${\mathcal {D}}_{n}$ är tom för udda $n$ .

Efter att ha introducerat Dyck-orden med längden $n$ , kan vi introducera en relation på dem. För varje $n\in \mathbb {N}$ definierar vi en relation $S_{n}$ på ${\mathcal {D}}_{n}$ ; för $u,v\in {\mathcal {D}}_{n}$ har vi $(u,v)\in S_{n }$ om och endast om $v$ kan nås från $u$ genom en serie av korrekta byten . Ett ordentligt byte i ett ord $u\in {\mathcal {D}}_{n}$ byter ut en förekomst av '][' med '[]'. För varje $n\in \mathbb {N}$ gör relationen $S_{n}$ ${\mathcal {D}}_{n}$ till en delvis beställt set . Relationen $S_{n}$ är reflexiv eftersom en tom sekvens av korrekta byten tar $u$ till $u$ . Transitivitet följer eftersom vi kan utöka en sekvens av korrekta swappar som tar $u$ till $v$ genom att sammanfoga den med en sekvens av korrekta swappar som tar $v$ till $w$ bildar en sekvens som tar $u$ till $w$ . För att se att $S_{n}$ också är antisymmetrisk introducerar vi en hjälpfunktion $\sigma _{n}:{\mathcal {D}}_{n}\ högerpil \mathbb {N}$ definierad som en summa över alla prefix $v$ för $u$ :

\sigma _{n}(u)=\summa _{vw =u}{\Big (}({\text{antal [s i }}v)-({\text{antal ]s i }}v){\Big )}

Följande tabell illustrerar att $\sigma _{n}$ är strikt monotont med avseende på korrekta swappar.

Strikt monotoni av $\sigma _{n}$
delsummor av $\sigma _{n}(u)$	$P$	$P-1$	$P$	$Q$
$u$	$\ldots$	]	[	$\ldots$
$u'$	$\ldots$	[	]	$\ldots$
delsummor av $\sigma _{n}(u')$	$P$	$P+1$	$P$	$Q$
Skillnad på delsummor	0	2	0	0

Därför $\sigma _{n}(u')-\sigma _{n}(u)=2>0$ så $\sigma _{n}(u)<\sigma _{n}(u')$ när det finns ett ordentligt byte som tar $u$ till ${\ displaystyle u'}$ . Om vi nu antar att både $(u,v),(v,u)\in S_{n}$ och $u\ neq v$ , då finns det icke-tomma sekvenser av korrekta swappar såsom $u$ tas in i $v$ och vice versa. Men då $\sigma _{n}(u)<\sigma _{n}(v)<\sigma _{n}(u) )$ vilket är meningslöst. Därför, när både $(u,v)$ och $(v,u)$ är i $S_{n}$ , har vi $u=v$ , därför är $S_{n}$ antisymmetrisk.

Den partiellt ordnade mängden $D_{8}$ visas i illustrationen som medföljer inledningen om vi tolkar en [ som att gå upp och ] som att gå ner.

Generaliseringar

Det finns varianter av Dyck-språket med flera avgränsare, t.ex. D2 på alfabetet "(", ")", "[" och "]". Orden i ett sådant språk är de som är väl inom parentes för alla avgränsare, dvs man kan läsa ordet från vänster till höger, trycka på varje öppningsavgränsare på stapeln, och när vi når en avslutande avgränsare måste vi kunna för att skjuta upp den matchande öppningsavgränsaren från toppen av högen. (Räknealgoritmen ovan generaliserar inte).

Se även

Anteckningar