A REGULARITY CONDITION FOR CONTEXT-FREE GRAMMARS

DOI10.1142/S0129054108005991MaRDI QIDQ3526539zbMATH OpenOpenAlexFDO

Authors Beatrice Palano

Publication date 25 September 2008

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054108005991

zbMATH Keywords

complexity measure

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45)

Recommendations

• On the degrees of non-regularity and non-context-freeness
• On the degree of non-regularity of context-free languages
• A graph-based regularity test for deterministic context-free languages
• Descriptional complexity of context-free grammar forms
• scientific article; zbMATH DE number 3850491

Cites work

• A few remarks on the index of context-free grammars and languages
• An analog of a theorem about context-free languages
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• On certain formal properties of grammars
• On Context-Free Languages
• On the index of a context-free grammar and language
• Self-embedded context-free grammars with regular counterparts

Cited in

(7)

• A-coverings for context free grammars
• On the regularity of languages generated by context-free evolutionary grammars
• A new algorithm for regularizing one-letter context-free grammars.
• Self-embedded context-free grammars with regular counterparts
• On the degrees of non-regularity and non-context-freeness
• On the degree of non-regularity of context-free languages
• Workspace theorems for regular-controlled grammars

This page was built for publication: A REGULARITY CONDITION FOR CONTEXT-FREE GRAMMARS

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3526539)