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:
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 :
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