Dyckov jazyk

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie

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[upraviť | upraviť zdroj]

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[upraviť | upraviť zdroj]

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