Publication Details

Context-Free Grammars over Free Groups

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

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

Abstract

This document introduces the notion of context-free grammar over a freegroup and examines the generative capacity of this structure. Thealgorithm of transformation of any type-0 grammar to an equivalentcontext-free grammar over a free group is demonstrated. As the mainresult, the equivalence of the family of recursively enumerablelanguages and the family of languages generated by context-freegrammars 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
BibTeX 
@inproceedings{BUT21454,
  author="Radek {Bidlo}",
  title="Context-Free Grammars over Free Groups",
  booktitle="Proceedings of 8th International Conference ISIM'05 Information System Implementation and Modeling",
  year="2005",
  pages="95--100",
  address="Ostrava",
  isbn="80-86840-09-3"
}
Back to top