Detail publikace

Context-Free Grammars over Free Groups

BIDLO, R.

Originální název

Context-Free Grammars over Free Groups

Typ

článek ve sborníku ve WoS nebo Scopus

Jazyk

angličtina

Originální abstrakt

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.

Klíčová slova

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

Autoři

BIDLO, R.

Rok RIV

2005

Vydáno

10. 3. 2005

Místo

Ostrava

ISBN

80-86840-09-3

Kniha

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

Strany od

95

Strany do

100

Strany počet

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