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.