# On the general relationship between automata, expressions, and grammars

When I took Theory of Computation, the main points of interest were three kinds of automata: finite, pushdown, and Turing, one type of expression: regular expressions which are equivalent to finite automata, and one type of grammar: context-free grammars which are equivalent to pushdown automata. Although there were brief notes about other types of grammars and automata and what sorts of language they can recognize, the only hierarchy they explored was the $$\text{regular \leftarrow context-free \leftarrow context-sensitive \leftarrow recursively-enumerable}$$ chain, and even at that, context-sensitive was only mentioned.

I always thought this was a sort of ugly and ad hoc structure, so a few decades ago, I sat down and tried to come up with something more fine-grained and more motivated by the nature of the formalism (automata, expressions, and grammars) than by the languages they recognized. I don't recall all the details, but it went something like this:

automata expression grammar language
1-node acyclic empty single empty production null
2-node acyclic single-letter single-production, single symbol on right trivial
linear graph no operators single-production singleton
acyclic graph alternation only single-nonterminal on left, no mutual productions finitary
general graph add closure single-nonterminal on, left-restricted mutual productions regular
re-entrant add recursive labels single-nonterminal on left context-free

## Notes

It went beyond this, but I think this is enough to give you the idea.

I'm not sure about all of the equivalences. Like I said, I did this a long time ago.

Automata are directed graphs with the edges labeled by letters with one required START node and at least one STOP node. A linear graph is an acyclic graph where all nodes have at most one in edge and at most one out edge. A re-entrant automaton is a version of the push-down automaton without that ugly explicit stack. It has new node types ENTER and EXIT. An EXIT node jumps back to the most recent ENTER node.

All grammars have at least one production with the start symbol on the left.

Here is an example of a recursive label R in an expression: "ab(R:aRb)ab". The idea is that the expression can either match the empty string or be matched recursively. Note that non-recursive labels add no computational power; they only let you shorten an expression.

## Question

I don't think any of this is especially difficult but it was very cool, so I've always wondered if someone somewhere has published a paper or book that explores this hierarchy. I'm primarily interested in the structure of the problem space and the comparison of the different formalisms rather than in the related computability issues.

Can anyone point me in the direction of some papers or books that have similar goals?

• Your first section just describes the well-known Chomsky hierarchy in formal grammar theory, and the Type-0 r.e. languages are generated by all formal grammars with production rules which can be recognized by a terminating Turing machine. Not quite understand your objection "I always thought this was a sort of ugly and ad hoc structure". Can you summarize its weakness and the advantage your new hierarchy proposal bring here? May 2, 2022 at 5:15
• @mohottnad, "ugly" just means not aesthetically pleasing. If you don't see beauty in mathematics, I don't think this can be explained to you. "Ad hoc" means not systematic. For example, the FSA seems like a natural structure, but adding a stack just seems like an odd thing to do as an isolated change. It could be justified as one of a set of additions, but on its own, it just seems capricious. Why a stack? Why not a FIFO queue? Why not a set? Why not a random-access list? My goals was to make it more systematic by defining a large space of systems. May 2, 2022 at 6:48

Automata Theory was (at least in the US) much more popular in the 60's and 70's than it is today. There are still applications today in Programming Language Theory (aka "Theory B"). If you look at CS Theory conferences with a Track B and PLV conferences, you may find current literature.

As for textbooks, the first edition of Hopcroft--Ulman and Algebraic Automata Theory (https://www.amazon.com/Algebraic-Automata-Cambridge-Advanced-Mathematics/dp/0521604923) are quite good.

You may also find Symbolic Dynamics to be of interest (e.g., https://home.cs.colorado.edu/~raf/media/papers/one-block.pdf).

Note that from a Complexity Theoretic perspective, there are some well-known equivalences:

• $$\textsf{REG} = \textsf{DSPACE}(O(1)) = \textsf{NSPACE}(O(1))$$
• I am not sure of the best upper bound for $$\textsf{CFL}$$. However, consider the class of decision problems that are logspace reducible to CFLs- call this class $$\textsf{LogCFL}$$. It is known that $$\textsf{LogCFL} = \textsf{SAC}^{1}$$, which sits right between $$\textsf{NL}$$ and $$\textsf{AC}^{1}$$.
• $$\textsf{CSL} = \textsf{NSPACE}(O(n))$$.

So from a Complexity perspective, folks don't usually look too closely at the grammar structure. Simulating the underlying model is of interest, as this allows us to relate complexity classes.

From a PLV perspective, one programming language grammars are slightly more powerful than CFLs, but not so powerful that our compilers will struggle to efficiently validate the syntax, etc. So from that perspective, it's not surprising that folks don't look much beyond CFGs.