Detail publikačního výsledku

Context-Free Grammars over Free Groups

BIDLO, R.

Originální název

Context-Free Grammars over Free Groups

Anglický název

Context-Free Grammars over Free Groups

Druh

Stať ve sborníku mimo WoS a Scopus

Originální abstrakt

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.

Anglický abstrakt

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.

Klíčová slova

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

Klíčová slova v angličtině

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

Autoři

BIDLO, R.

Vydáno

10.03.2005

Nakladatel

Marq software s.r.o.

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",
  publisher="Marq software s.r.o.",
  address="Ostrava",
  isbn="80-86840-09-3"
}