# Automata as term rewriting systems

It came to my mind that automata (say to start DFA) can be thought as a special kind of rewriting systems. So if one has a word w , one tries to reduce it to the $$\epsilon$$ word. In other words acceptance is just a particular case of equational reasoning in term rewriting systems.

My question is, has this approach been developed before? In particular, it would be interesting to see if Turing machines can be modelled in this language.

Someone has suggested regular grammars do model deterministic automata. Maybe it is useful to recall the difference between abstract reduction system and term rewriting system. From "Term rewriting and all that":

A rewrite rule is an identity $$l \approx r$$ such that l i not a variable and $$Var(l) \supseteq Var(r)$$. In this case we may write $$l \to r$$. A term rewriting system is a set of rewrite rules.

It seems that formal gramars fit better the definition of abstract reduction system:

An abstract reduction system is a pair $$(A,\to)$$ where the reduction $$\to$$ is a binary relation on the set $$A$$, i.e. $$\to \subseteq A \times A$$.

For the future I note:

Relationship between Turing Machine and Lambda calculus?

• There is such a thing as a production rule: en.wikipedia.org/wiki/Production_(computer_science) though it does go in the opposite direction that you suggest.
– cody
Jan 17 '19 at 14:28
• You're more or less describing a Regular Grammar: en.wikipedia.org/wiki/Regular_grammar Jan 17 '19 at 15:40
• My idea is to extend the question little by little to see if this could be extended to turing machines, for instance Jan 18 '19 at 22:05
• Uhm, please refrain from extending your question little by little. If you have multiple (research-level) questions, please post multiple questions. From my experience, the people in this forum are very friendly and generous, but most of them don't have time for engaging in conversations/discussions. Consequently, the format of TCS-stackexchange is precisely Q&A and not something else. Jan 20 '19 at 20:08
• in some sense this would reflect duality memory-time Feb 3 '19 at 18:18