Result Details

How to Generate Recursively Enumerable Languages Using Only Context-free Productions and Eight Nonterminals

BIDLO, R.; BLATNÝ, P. How to Generate Recursively Enumerable Languages Using Only Context-free Productions and Eight Nonterminals. Proceedings of 11th Conference and Competition Student EEICT 2005, Volume 3. Brno: Faculty of Electrical Engineering and Communication BUT, 2005. p. 536-541. ISBN: 80-214-2890-2.
Type
conference paper
Language
English
Authors
Bidlo Radek, Ing., Ph.D., FIT (FIT), DIFS (FIT)
Blatný Petr, Ing., Ph.D., FIT (FIT), DIFS (FIT)
Abstract

The notion of a context-free grammar over a free group is introduced.The transformation of any type-0 grammar to an equivalent context-freegrammar over a free group is demonstrated. This approach causes anundesirable increase of the number of nonterminal symbols. Hence weintroduce a method for their reduction.

Keywords

Context-Free Grammars, Derivations, Free Groups, Recursively Enumerable Languages

Published
2005
Pages
536–541
Proceedings
Proceedings of 11th Conference and Competition Student EEICT 2005, Volume 3
Conference
STUDENT EEICT 2005
ISBN
80-214-2890-2
Publisher
Faculty of Electrical Engineering and Communication BUT
Place
Brno
BibTeX 
@inproceedings{BUT18908,
  author="Radek {Bidlo} and Petr {Blatný}",
  title="How to Generate Recursively Enumerable Languages Using Only Context-free Productions and Eight Nonterminals",
  booktitle="Proceedings of 11th Conference and Competition Student EEICT 2005, Volume 3",
  year="2005",
  pages="536--541",
  publisher="Faculty of Electrical Engineering and Communication BUT",
  address="Brno",
  isbn="80-214-2890-2"
}
Research groups
Formal Model Research Group (RG FM)
Departments
Department of Information Systems (DIFS)
Back to top