I have a system that is deciding a subset of regular languages and am curious if anyone has seen this type before and if it has a name I could use to research more.
Specifically consider the collection of formal grammars with the following restrictions:
- There is a bijection between the terminal symbols and non-terminal symbols. In this post, I will use lowercase letters for terminal symbols and their uppercase counterparts as the associated non-terminal.
- All production rules are of the form:
A -> bBor
A -> ε.
So, these are basically regular grammars with the restriction that all rules which produce a terminal
b must then have the associated non-terminal
B directly afterwards. From the point of view of a finite automata, any automata that writes a
b must enter the same state
I believe the collection of languages described by these grammars are a proper subset of regular languages. For example, I don't think it can describe the regular language
(ac*a|bc*b) because it cannot "remember" whether the string started with
b while processing through the
Does anyone know if this type of language/grammar has been studied and how I could find more information about it if so? Thanks!