Double Greibach operator grammars (Q1589438)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1542267
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Double Greibach operator grammars |
scientific article; zbMATH DE number 1542267 |
Statements
Double Greibach operator grammars (English)
0 references
12 December 2000
0 references
Every context-free grammar can be transformed into one in double Greibach operator form, that satisfies both double Greibach form and operator form. Examination of the expressive power of various well-known subclasses of context-free grammars in double Greibach and/or operator form yields an extended hierarchy of language classes. Basic decision properties such as equivalence can be stated in stronger forms via new classes of languages in this hierarchy.
0 references
formal languages
0 references
context-free grammars
0 references
normal forms
0 references
hierarchy
0 references
decision properties
0 references
0.7877184152603149
0 references
0.7877184152603149
0 references
0.7725672125816345
0 references
0.7665483355522156
0 references
