Publication detail

Context-Free Grammars over Free Groups

BIDLO, R.

Original Title

Context-Free Grammars over Free Groups

Type

conference paper

Language

English

Original 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.

Keywords

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

Authors

BIDLO, R.

RIV year

2005

Released

10. 3. 2005

Location

Ostrava

ISBN

80-86840-09-3

Book

Proceedings of 8th International Conference ISIM'05 Information System Implementation and Modeling

Pages from

95

Pages to

100

Pages count

7

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"
}