Dyckov jazyk

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

Dyckov jazyk nad 2n-prvkovou abecedou je v teórii formálnych jazykov bezkontextový jazyk, pomenovaný podľa matematika Walthera von Dycka, generovaný nasledujúcou gramatikou:

V prípade, že sú nejaké typy ľavých zátvoriek a sú zodpovedajúce typy pravých zátvoriek, zodpovedá Dyckov jazyk nad abecedou 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 nad štvorprvkovou abecedou pozostávajúcou zo znakov . Daný Dyckov jazyk bude generovaný gramatikou:

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

Zdroj[upraviť | upraviť zdroj]

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