Dyckov jazyk nad 2n-prvkovou abecedou ${\displaystyle \{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:

${\displaystyle \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 ${\displaystyle a_{1},a_{2},\ldots ,a_{n}}$ sú nejaké typy ľavých zátvoriek a ${\displaystyle b_{1},b_{2},\ldots ,b_{n}}$ sú zodpovedajúce typy pravých zátvoriek, zodpovedá Dyckov jazyk nad abecedou ${\displaystyle \{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 ${\displaystyle D_{2}}$ nad štvorprvkovou abecedou pozostávajúcou zo znakov ${\displaystyle (,),}$. Daný Dyckov jazyk bude generovaný gramatikou:

${\displaystyle \sigma \to \varepsilon \ |\ (\sigma )\sigma \ |\ \sigma .}$

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

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

Zdrojupraviť | upraviť zdroj

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