Jazyk sestávající z vyvážených řetězců hranatých závorek
Lattice of 14 Dyck words of length 8 - [ a ] interpretováno jako nahoru a dolů
V teorii formální jazyky z počítačová věda, matematika, a lingvistika, a Dyckovo slovo je vyvážený tětiva hranatých závorek [a]. Sada slov Dyck tvoří Dyck jazyk.
Dyckova slova a jazyk jsou pojmenovány po matematikovi Walther von Dyck. Mají aplikace v analýza výrazů, které musí mít správně vnořenou posloupnost závorek, jako jsou aritmetické nebo algebraické výrazy.
Formální definice
Nechat
být abeceda skládající se ze symbolů [a]. Nechat
označit jeho Kleene uzavření.v Dyck jazyk je definován jako:
![{ displaystyle {u in Sigma ^ {*} vert { text {všechny předpony}} u { text {neobsahují více] než než ['s}} { text {a počet ['in}} u { text {se rovná počtu]' s}} }.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b525c448682a61c1231019f8542e5baa838e1429)
Bezkontextová gramatika
Může být užitečné definovat jazyk Dyck pomocí a bezkontextová gramatika V některých situacích je jazyk Dyck generován bezkontextovou gramatikou s jediným neterminálem Sa výroba:
- S → ε | "[" S "]" S
To znamená, S je buď prázdný řetězec (ε) nebo je „[“, prvek jazyka Dyck, odpovídající „]“ a prvek jazyka Dyck.
Alternativní bezkontextová gramatika pro jazyk Dyck je dána produkcí:
- S → ("[" S "]")*
To znamená, S je nula nebo více výskytů kombinace „[“, prvku jazyka Dyck a odpovídající „]“, kde se více prvků jazyka Dyck na pravé straně produkce může od sebe lišit.
Alternativní definice
V dalších kontextech může být užitečné definovat jazyk Dyck rozdělením
do tříd ekvivalence, jak následuje. Pro každý prvek
délky
, definujeme dílčí funkce
a
podle
je
s „
"vloženo do
th pozice
je
s „
"smazáno z
th pozice
s pochopením toho
není definováno pro
a
není definováno, pokud
. Definujeme vztah ekvivalence
na
takto: pro prvky
my máme
právě tehdy, pokud existuje posloupnost nulových nebo více aplikací systému
a
funkce začínající na
a končí na
. Že je povolena posloupnost nulových operací, odpovídá za reflexivita z
. Symetrie vyplývá z pozorování, že jakákoli konečná posloupnost aplikací
na řetězec lze vrátit zpět s konečnou posloupností aplikací
. Přechodnost je zřejmé z definice.
Vztah ekvivalence rozděluje jazyk
do tříd ekvivalence. Pokud vezmeme
pro označení prázdného řetězce, pak jazyk odpovídající třídě ekvivalence
se nazývá Dyck jazyk.
Vlastnosti
- Jazyk Dyck je uzavřen za provozu zřetězení.
- Léčbou
jako algebraický monoidní při zřetězení vidíme, že se monoidní struktura přenáší na kvocient
, což má za následek syntaktický monoid jazyka Dyck. Třída
bude označeno
. - Syntaktický monoid jazyka Dyck není komutativní: pokud
a
pak
. - S výše uvedenou notací,
ale ani jeden
ani
jsou invertibilní v
. - Syntaktický monoid jazyka Dyck je isomorfní s bicyklická poloskupina na základě vlastností
a
popsáno výše. - Podle Chomsky – Schützenbergerova věta o reprezentaci, jakýkoli bezkontextový jazyk je homomorfní obraz průniku některých běžný jazyk s jazykem Dyck na jednom nebo více druzích dvojitých závorek.[1]
- Jazyk Dyck se dvěma odlišnými typy závorek lze rozpoznat v souboru třída složitosti
.[2] - Počet zřetelných slov Dyck s přesně n dvojice závorek a k nejvnitřnější páry (viz podřetězec
) je Narayana číslo
. - Počet zřetelných slov Dyck s přesně n dvojice závorek je n-th Katalánské číslo
. Všimněte si, že jazyk Dyck slov s n dvojice závorek se rovná sjednocení, přes všechny možné kDyckových jazyků slov n dvojice závorek s k nejvnitřnější páry, jak je definováno v předchozím bodě. Od té doby k se může pohybovat od 0 do n, získáme následující rovnost, která skutečně platí:

Příklady
Můžeme definovat vztah ekvivalence
v jazyce Dyck
. Pro
my máme
kdyby a jen kdyby
, tj.
a
mají stejnou délku. Tento vztah rozděluje jazyk Dyck
kde
. Všimněte si, že
je prázdné pro liché
.
Po zavedení Dyckových slov délky
, můžeme k nim zavést vztah. Pro každého
definujeme vztah
na
; pro
my máme
kdyby a jen kdyby
lze dosáhnout z
sérií řádné swapy. Řádná výměna slovem
zamění výskyt '] [' s '[]'. Pro každou
vztah
dělá
do částečně objednaná sada. Vztah
je reflexní protože trvá prázdná posloupnost správných swapů
na
. Přechodnost následuje, protože můžeme rozšířit posloupnost správných swapů, která trvá
na
zřetězením se sekvencí správných swapů, které zaberou
na
vytvoření sekvence, která trvá
do
. To vidět
je také antisymetrický zavedeme pomocnou funkci
definována jako součet za všechny předpony
z
:
![{ displaystyle sigma _ {n} (u) = součet _ {vw = u} { Big (} ({ text {počet [je v}} v) - ({ text {počet] je v}} v) { Big)}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e0fd8aa71ca85cca59c89bb57a3e877e32c393bd)
Následující tabulka to ilustruje
je přísně monotónní s ohledem na řádné výměny.
Přísná monotónnost 
dílčí součty  |  |  |  |  |
---|
 |  | ] | [ |  |
---|
 |  | [ | ] |  |
---|
dílčí součty  |  |  |  |  |
---|
Rozdíl dílčích součtů | 0 | 2 | 0 | 0 |
---|
Proto
tak
když dojde k řádné výměně
do
. Nyní, když předpokládáme, že obojí
a
, pak existují neprázdné sekvence správných swapů, například
je brána v úvahu
a naopak. Ale pak
což je nesmyslné. Proto kdykoli obojí
a
jsou v
, my máme
, proto
je antisymetrický.
Částečně objednaná sada
je znázorněno na ilustraci doprovázející úvod, pokud interpretujeme [jako stoupající a] jako klesající.
Zobecnění
Existují varianty jazyka Dyck s více oddělovači, např. Na abecedě "(", ")", "[" a "]". Slova takového jazyka jsou slova, která jsou pro všechny oddělovače správně uvedena v závorkách, tj. Lze číst slovo zleva doprava, tlačit každý otevírací oddělovač na zásobník a kdykoli dosáhneme uzavíracího oddělovače, musíme být schopni vyskočí odpovídající oddělovač otevření z horní části zásobníku.
Viz také
Poznámky
- ^ Kambites, Communications in Algebra Volume 37, číslo 1 (2009) 193-208
- ^ Barrington a Corbett, Information Processing Letters 32 (1989) 251-256
Reference