Dyckov jazyk

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 

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 

Kategória:Formálne jazyky