Bezkontextové gramatiky a zásobníkové automaty

Context-free languages and pushdown automata

grant

teorie formální jazyků, primitivní slova, gramatiky, automaty

Plánovaný výzkum se zaměří na studium bezkontextových jazyků a zásobníkových automatů a jejich aplikací. Pro hlubší pochopení struktur formálních jazyků je nápomocné studovat jejich kombinatorické vlastnosti. Jedním z předmětů výzkumu je problém primitivních slov. Slovo nazýváme primitivní, pokud není mocninou jiného slova. P. Dömösi, M. Ito a S. Horváth prezentovali domněnku, že jazyk všech primitivních slov nad abecedou s několika symboly, Q, není bezkontextový. Nedávno publikované články se stále zabývají tímto proslulým dohadem, který je stále otevřeným problémem. Plánujeme dále rozvíjet toto zkoumání se zaměřením na malé bezkontextové gramatiky generující primitivní slova. Na druhou stranu, vezmeme-li v úvahu, že homomorfický obraz neprimitivního slova je také neprimitivní, budeme také studovat, zda je Q skutečnou homomorfickou charakterizací Chomsky-Schützenberger-Stanleyho typu. Doufáme, že toto zkoumání povede na důkaz platnosti či neplatnosti předchozí domněnky a otevřeného problému. Dále bychom rádi charakterizovali bezkontextové jazyky z neprimitivních slov. Během tohoto výzkumu můžeme odhalit nové důležité vlastnosti bezkontextových jazyků. Studium kombinatorických vlastností slov a jazyků nám může poskytnout řadu informací o struktuře jazyků s vazbou na Chomského hierarchii a odpovídající automaty. Jedním z nejdůležitějších výsledků v této oblasti je Bar-Hillelovo lemma, které poskytuje efektivní metodu pro testování, zda je jazyk bezkontextový či nikoli. K dispozici jsou také silnější verze tohoto lemmatu. Nasnadě je tedy studium třídy nelineárních bezkontextových jazyků. G. Horváth objevil silně iterující vlastnosti nelineárních bezkontextových jazyků, které bychom rádi také v tomto projektů dále zkoumali. Podle dobře známého teorému Chomsky-Schützenberger-Stanleyho, jež říká, že každý bezkontextový jazyk je homomorficky charakterizovaný pomocí, h, D a R, kde h je homomorfismus, D je Dyckův jazyk a R je regulární jazyk. Existuje několik rozšíření tohoto výsledku. V tomto projektu plánujeme pokračovat také v tomto výzkumu, kdy se pokusíme vytvořit skutečnou homomorfickou charakterizaci bezkontextových jazyků s danou kombinatorickou vlastností (skromnost (angl. slenderness), poloskromnost, palindromicita, atd.). Matematická hodnota očekávaných výsledků bude podpořena jejich publikací v mezinárodních vědeckých časopisech a na konferencích.

Meduna Alexandr, prof. RNDr., CSc. (UIFS) – hlavní řešitel
Čermák Martin, Ing., Ph.D.
Koutný Jiří, Ing., Ph.D.
Křivka Zbyněk, Ing., Ph.D. (UIFS)