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.

Comments

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?
As mentioned in the comments, regular grammars are more or less a (string) rewriting system, where the arrow of a derivation is in the reverse direction of the rewriting arrow. Since you seem to be especially interested in term rewriting systems (as opposed to string rewriting systems), the automaton model that you are probably looking for is that of tree automata, that is, finite automata accepting trees instead of strings. I've heard that the following is a very good book on tree automata (although I haven't read through it yet).

H. Comon, M. Dauchet, R. Gilleron, C. Löding
and F. Jacquemard, D. Lugiez, S. Tison and M. Tommasi: "Tree Automata: Techniques and Applications", 2007.

As far as I can tell, the question you asked is quite natural and thus has already been explored. With some googling I found out that Sophie Tison (co-author of the TATA book above) had some invited talks with "term rewriting" and "tree automata" in the title (I haven't read them either).

Tison S. (2011) Tree Automata, (Dis-)Equality Constraints and Term Rewriting. In: Ong L. (eds) Typed Lambda Calculi and Applications. TLCA 2011. Lecture Notes in Computer Science, vol 6690. Springer, Berlin, Heidelberg

Tison S. (2000) Tree Automata and Term Rewrite Systems. In: Bachmair L. (eds) Rewriting Techniques and Applications. RTA 2000. Lecture Notes in Computer Science, vol 1833. Springer, Berlin, Heidelberg