Dyckov jazyk

Dyckov jazyk nad 2n-prvkovou abecedou $\{a_1,b_1,a_2,b_2,\dots ,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 \epsilon |a_1\sigma b_1\sigma |a_2\sigma b_2\sigma |\dots |a_n\sigma b_n\sigma .$

V prípade, že $a_1,a_2,\dots ,a_n$ sú nejaké typy ľavých zátvoriek a $b_1,b_2,\dots ,b_n$ sú zodpovedajúce typy pravých zátvoriek, zodpovedá Dyckov jazyk nad abecedou $\{a_1,b_1,a_2,b_2,\dots ,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 \epsilon |(\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,([[]](()))\in D_2,)(\notin D_2,([(]))\notin D_2.$