Department of Information Systems

Context-free languages and pushdown automata

Research leader:Meduna Alexander
Team members:Čermák Martin, Koutný Jiří, Křivka Zbyněk
Agency:Ministry of Education, Youth and Sports Czech Republic
Keywords: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.
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 context-free languages
  • 7. 7. 2011: P. Dömösi (College of Nyíregyháza, Hungary): Context-free 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


2012KOUTNÝ Jiří and MEDUNA Alexander. Tree-controlled Grammars with Restrictions Placed upon Cuts and Paths. Kybernetika. 2012, vol. 48, no. 1, pp. 165-175. ISSN 0023-5954.
 MEDUNA Alexander and ZEMEK Petr. One-Sided Forbidding Grammars and Selective Substitution Grammars. International Journal of Computer Mathematics. 2012, vol. 89, no. 5, pp. 586-596. ISSN 0020-7160.
 ČERMÁK Martin, HORÁČEK Petr and MEDUNA Alexander. Rule-restricted automaton-grammar transducers: Power and linguistic applications. Mathematics for Applications. Brno: Department of Mathematics FEEC BUT, 2012, vol. 1, no. 1, pp. 13-35. ISSN 1805-3610.
 ČERMÁK Martin, KOUTNÝ Jiří and MEDUNA Alexander. Parsing Based on n-Path Tree-Controlled Grammars. Theoretical and Applied Informatics. Varšava: 2012, vol. 2011, no. 23, pp. 213-228. ISSN 1896-5334.
2011KOUTNÝ Jiří, KŘIVKA Zbyněk and MEDUNA Alexander. Pumping Properties of Path-Restricted Tree-Controlled Languages. In: 7th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science. Brno: Brno University of Technology, 2011, pp. 61-69. ISBN 978-80-214-4305-1.
 KOUTNÝ Jiří. Syntax Analysis of Tree-Controlled Languages. In: Proceedings of the 17th Conference STUDENT EEICT 2011 Volume 3. Brno: Brno University of Technology, 2011, p. 5. ISBN 978-80-214-4273-3.
 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. 269-283. ISSN 0324-721X.
 ČERMÁK Martin and MEDUNA Alexander. n-Accepting 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. 168-183. ISBN 978-615-5097-19-5.
 ČERMÁK Martin. Basic Properties of n-Languages. In: Proceedings of the 17th Conference and Competition STUDENT EEICT 2011 Volume 3. Brno: Faculty of Information Technology BUT, 2011, pp. 460-464. ISBN 978-80-214-4273-3.
2010LUKÁŠ Roman and MEDUNA Alexander. Multigenerative Grammar Systems and Matrix Grammars. Kybernetika. 2010, vol. 46, no. 1, pp. 68-82. ISSN 0023-5954.

Your IPv4 address:
Switch to IPv6 connection

DNSSEC [dnssec]