Bezkontextové gramatiky a zásobníkové automaty

Context-free languages and pushdown automata

grant

formal language theory, primitive words, grammars, automata

The planned research will focus on the study of context-free languages and pushdown automata and their applications. To understand the structure of formal languages is a helpful tool to study their combinatorial properties. One of the subjects of this research is the problem of primitive words. A word is called primitive if it is not a power of another word. A widely known conjecture of P. Dömösi, M. Ito, and S. Horváth states that the language Q of all primitive words over an alphabet with several letters is not context-free. A number of recent papers investigated this well-known conjecture which is still open. We intend to continue our investigations on small context-free grammars generating primitive words. On the other hand, using the fact that a homomorphic map of a nonprimitive word is also nonprimitive, we also plan to study whether or not Q has a real Chomsky-Schützenberger-Stanley type homomorphic characterization. By our hope, these investigations may lead to prove or disprove our conjecture. In addition, we would like to characterize context-free languages consisting of non-primitive words. By this research we can also find new important properties of context-free languages. Studying the combinatorial properties of words and languages we can get a lot of information on the structure of languages in connection with the Chomsky hierarchy and corresponding automata. Regarding this subject, one of the most important results is the Bar-Hillel Lemma having an effective method for testing a language whether or not it is context-free. There are some well-known stronger versions of this result. One direction is to study the family of context-free non-linear languages. G. Horváth discovered a strong iteration property of context-free non-linear languages. In this project we would like to continue this line of research. By the well-known Chomsky-Schützenberger-Stanley theorem, every context-free language is homomorphically characterized by h and D, R, where h is a homomorphism, D is a Dyck language and R is a regular language. Several extensions of this result are known. In this project we plan to continue this research giving real homomorphic characterizations of context-free languages having certain combinatorial properties (slenderness, poly-slenderness, palindromicity, etc). The mathematical value of the expected results will be proved by their publications in international scientific journals and conferences.

Meduna Alexandr, prof. RNDr., CSc. (DIFS) – research leader
Čermák Martin, Ing., Ph.D.
Koutný Jiří, Ing., Ph.D.
Křivka Zbyněk, Ing., Ph.D. (DIFS)