Department of Information Systems
Contextfree languages and pushdown automata 
Reseach leader:  Meduna Alexander 
Team members:  Čermák Martin, Koutný Jiří, Křivka Zbyněk 
Agency:  MŠMT 
Code:  MEB041003 
Start:  2010 
End:  2011 
Keywords:  formal language theory, primitive words, grammars, automata 
Annotation: 
The planned research will focus on the study of contextfree 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 contextfree. A number of recent papers investigated this wellknown conjecture which is still open. We intend to continue our investigations on small contextfree 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 ChomskySchützenbergerStanley type homomorphic characterization. By our hope, these investigations may lead to prove or disprove our conjecture. In addition, we would like to characterize contextfree languages consisting of nonprimitive words. By this research we can also find new important properties of contextfree 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 BarHillel Lemma having an effective method for testing a language whether or not it is contextfree. There are some wellknown stronger versions of this result. One direction is to study the family of contextfree nonlinear languages. G. Horváth discovered a strong iteration property of contextfree nonlinear languages. In this project we would like to continue this line of research.
By the wellknown ChomskySchützenbergerStanley theorem, every contextfree 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 contextfree languages having certain combinatorial properties (slenderness, polyslenderness, palindromicity, etc).
The mathematical value of the expected results will be proved by their publications in international scientific journals and conferences. 
Accomplishments: 
In addition to publications as the main results of this project (see below), we organized 4 public seminars with 6 lectures (all in English) at Faculty of information technology, Brno University of Technology:
 29. 3. 2011: J. Falucskai (College of Nyíregyháza, Hungary): Some Algorithms Concerning Uniquely Decipherable Codes; G. Horváth (University of Debrecen, Hungary): Pumping lemmas for linear and nonlinear contextfree languages
 7. 7. 2011: P. Dömösi (College of Nyíregyháza, Hungary): Contextfree languages and primitive words
 21. 7. 2011: János Falucskai (College of Nyíregyháza, Hungary): A New Interpretation of the Decipherability
 2. 11. 2011: P. Dömösi (College of Nyíregyháza, Hungary): Something About Cryptography; G. Horváth (University of Debrecen, Hungary): The Language of Primitive Words

Publications
2012  KOUTNý Jiří and MEDUNA Alexander. Treecontrolled Grammars with Restrictions Placed upon Cuts and Paths. Kybernetika. 2012, vol. 48, no. 1, pp. 165175. ISSN 00235954. 
 MEDUNA Alexander and ZEMEK Petr. OneSided Forbidding Grammars and Selective Substitution Grammars. International Journal of Computer Mathematics. 2012, vol. 89, no. 5, pp. 586596. ISSN 00207160. 
 ČERMáK Martin, HORáčEK Petr and MEDUNA Alexander. Rulerestricted automatongrammar transducers: Power and linguistic applications. Mathematics for Applications. Brno: Department of Mathematics FEEC BUT, 2012, vol. 1, no. 1, pp. 1335. ISSN 18053610. 
 ČERMáK Martin, KOUTNý Jiří and MEDUNA Alexander. Parsing Based on nPath TreeControlled Grammars. Theoretical and Applied Informatics. Varšava: 2012, vol. 2011, no. 23, pp. 213228. ISSN 18965334. 
2011  KOUTNý Jiří, KřIVKA Zbyněk and MEDUNA Alexander. Pumping Properties of PathRestricted TreeControlled Languages. In: 7th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science. Brno: Brno University of Technology, 2011, pp. 6169. ISBN 9788021443051. 
 KOUTNý Jiří. Syntax Analysis of TreeControlled Languages. In: Proceedings of the 17th Conference STUDENT EEICT 2011 Volume 3. Brno: Brno University of Technology, 2011, p. 5. ISBN 9788021442733. 
 KřIVKA Zbyněk and MASOPUST Tomáš. Cooperating Distributed Grammar Systems with Random Context Grammars as Components. Acta Cybernetica. 2011, vol. 20, no. 2, pp. 269283. ISSN 0324721X. 
 ČERMáK Martin and MEDUNA Alexander. nAccepting Restricted Pushdown Automata Systems. In: 13th International Conference on Automata and Formal Languages. Nyíregyháza: Computer and Automation Research Institute, Hungarian Academy of Sciences, 2011, pp. 168183. ISBN 9786155097195. 
 ČERMáK Martin. Basic Properties of nLanguages. In: Proceedings of the 17th Conference and Competition STUDENT EEICT 2011 Volume 3. Brno: Faculty of Information Technology BUT, 2011, pp. 460464. ISBN 9788021442733. 
2010  LUKáš Roman and MEDUNA Alexander. Multigenerative Grammar Systems and Matrix Grammars. Kybernetika. 2010, vol. 46, no. 1, pp. 6882. ISSN 00235954. 

