Publication Details

Context-Free Grammars over Free Groups

BIDLO Radek. Context-Free Grammars over Free Groups. In: Proceedings of 8th International Conference ISIM'05 Information System Implementation and Modeling. Ostrava, 2005, pp. 95-100. ISBN 80-86840-09-3.
Czech title
Bezkontextové gramatiky nad volnými grupami
Type
conference paper
Language
english
Authors
Bidlo Radek, Ing. (DIFS FIT BUT)
Keywords

Context-Free Grammars, Penttonen Normal Forms, Free Groups, Recursively Enumerable Languages

Abstract

This document introduces the notion of context-free grammar over a free group and examines the generative capacity of this structure. The algorithm of transformation of any type-0 grammar to an equivalent context-free grammar over a free group is demonstrated. As the main result, the equivalence of the family of recursively enumerable languages and the family of languages generated by context-free grammars over free groups is proved.

Published
2005
Pages
95-100
Proceedings
Proceedings of 8th International Conference ISIM'05 Information System Implementation and Modeling
Conference
8th International Conference on Information Systems Implementation and Modelling, Hradec nad Moravicí, CZ
ISBN
80-86840-09-3
Place
Ostrava, CZ
BibTeX 
@INPROCEEDINGS{FITPUB7726,
   author = "Radek Bidlo",
   title = "Context-Free Grammars over Free Groups",
   pages = "95--100",
   booktitle = "Proceedings of 8th International Conference ISIM'05 Information System Implementation and Modeling",
   year = 2005,
   location = "Ostrava, CZ",
   ISBN = "80-86840-09-3",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/7726"
}
Back to top