Complexity limits of simple semi conditional grammars revealed
Non-Terminal Complexity of Simple Semi-Conditional Grammars
Formal Languages and Automata Theory
Summary
This paper looks at a special kind of grammar called simple semi-conditional grammars (SSCGs), which are rules that describe how languages form. The authors find out how many building blocks (called non-terminals) these grammars need to create different types of languages, from very simple to very complicated ones. They also show that some SSCGs with only one non-terminal can still make languages that are tricky to recognize, but there are limits to this power. Finally, the paper finds that checking whether a word belongs to a language described by an SSCG with two non-terminals is already a tough problem for computers.
What this means in practice
- •For compiler designers: Recognize limitations on grammar sizes to optimize language parsing strategies.
- •For automata theory engineers: Avoid using single non-terminal SSCGs for certain regular language designs due to inherent complexity constraints.
A theory result. No direct application yet.
Authors
Henning Fernau, Sanjay Jain, Linus Richter, Frank Stephan, Dan Turetsky
Abstract
We study the complexity of simple semi-conditional grammars (SSCGs) in terms of the number of their terminals and non-terminals. We show that SSCGs with three non-terminals can generate all RE languages; two non-terminals suffice for linear languages; and one suffices for unary regular languages. We also determine both upper bounds and fundamental limitations of SSCGs: while certain one-non-terminal SSCGs can generate non-context-free languages, every language generated by a one-non-terminal SSCG is in non-deterministic linear space. We also prove that there exists a regular language of alphabet size at least 3 which cannot be generated by any one-non-terminal SSCG. Finally, we prove that membership testing for SSCGs of two non-terminals is already NP-hard.