Publication Details
Context-Free Grammars over Free Groups
BIDLO, R. Context-Free Grammars over Free Groups. In 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 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
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"
}