Dyckov jazyk

Dyckov jazyk nad 2n-prvkovou abecedou $\{a_{1},b_{1},a_{2},b_{2},\ldots ,a_{n},b_{n}\}(n\in \mathbb {N} )$ je v teórii formálnych jazykov bezkontextový jazyk, pomenovaný podľa matematika Walthera von Dycka, generovaný nasledujúcou gramatikou:

$\sigma \to \varepsilon \ |\ a_{1}\sigma b_{1}\sigma \ |\ a_{2}\sigma b_{2}\sigma \ |\ \ldots \ |\ a_{n}\sigma b_{n}\sigma .$

V prípade, že $a_{1},a_{2},\ldots ,a_{n}$ sú nejaké typy ľavých zátvoriek a $b_{1},b_{2},\ldots ,b_{n}$ sú zodpovedajúce typy pravých zátvoriek, zodpovedá Dyckov jazyk nad abecedou $\{a_{1},b_{1},a_{2},b_{2},\ldots ,a_{n},b_{n}\}$ jayzku všetkých dobrých uzátvorkovaní nad danými typmi zátvoriek.

Gramatika generujúca Dyckov jazyk je jednoznačná (pre každé slovo z jazyka existuje práve jeden strom odvodenia).

Význam Dyckových jazykov umocňuje aj tzv. Chomského-Schützenbergerova veta, ktorá hovorí, že každý bezkontextový jazyk je homomorfným obrazom prieniku niektorého Dyckovho jazyka s vhodným regulárnym jazykom.

Príklad

Nasleduje príklad Dyckovho jazyka $D_{2}$ nad štvorprvkovou abecedou pozostávajúcou zo znakov $(,),[,]$. Daný Dyckov jazyk bude generovaný gramatikou:

$\sigma \to \varepsilon \ |\ (\sigma )\sigma \ |\ [\sigma ]\sigma .$

Takýto jazyk je jazykom všetkých dobrých uzátvorkovaní nad danou abecedou, a teda, napríklad:

$(\ (\ )\ [\ ]\ )\in D_{2},\qquad (\ [\ [\ ]\ ]\ (\ (\ )\ )\ )\in D_{2},\qquad )\ (\notin D_{2},\qquad (\ [\ (\ ]\ )\ )\notin D_{2}.$

Zdroj

Tento článok je čiastočný alebo úplný preklad článku Язык_Дика na ruskej Wikipédii.