Context-Free Grammars over Free Groups
Result description
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 GrammarsPenttonen Normal FormsFree GroupsRecursively Enumerable Languages
The result's identifiers
Result code in IS VaVaI
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Context-Free Grammars over Free Groups
Original language description
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.
Czech name
Bezkontextové gramatiky nad volnými grupami
Czech description
Dokument zavádí pojem bezkontextové gramatiky nad volnou grupou a zkoumá generativní schopnosti této struktury. Je představen algoritmus transformace libovolné gramatiky typu 0 na bezkontextovou gramatiku nad volnou grupou. Jako hlavní výsledek je dokázáno, že tyto gramatiky generují celou třídu rekurzívně vyčíslitelných jazyků.
Classification
Type
D - Article in proceedings
CEP classification
JC - Computer hardware and software
OECD FORD branch
—
Result continuities
Project
GA201/04/0441: Optimally integrated models of modern information technologies
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2005
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of 8th International Conference ISIM'05 Information System Implementation and Modeling
ISBN
80-86840-09-3
ISSN
—
e-ISSN
—
Number of pages
7
Pages from-to
95-101
Publisher name
NEUVEDEN
Place of publication
Ostrava
Event location
Hradec nad Moravicí
Event date
Apr 19, 2005
Type of event by nationality
EUR - Evropská akce
UT code for WoS article
—
Basic information
Result type
D - Article in proceedings
CEP
JC - Computer hardware and software
Year of implementation
2005