Result 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: Marq software s.r.o., 2005. p. 95-100. ISBN: 80-86840-09-3.
Type
conference paper
Language
English
Authors
Bidlo Radek, Ing., Ph.D., DIFS (FIT)
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.
Keywords
Context-Free Grammars, Penttonen Normal Forms, Free Groups, Recursively Enumerable Languages
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
ISBN
80-86840-09-3
Publisher
Marq software s.r.o.
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",
publisher="Marq software s.r.o.",
address="Ostrava",
isbn="80-86840-09-3"
}
Projects
Optimally Integrated Models of Modern Information Technologies, GACR, Standardní projekty, GA201/04/0441, start: 2004-01-01, end: 2006-12-31, completed
Research groups
Formal Model Research Group (RG FM)
Departments