From Wikipedia, the free encyclopedia

This article is part of a WikiProject to improve Wikipedia's articles related to Computer science. For guidelines see WikiProject Computer science and Wikipedia:Contributing FAQ.

I am considering, as my first wikontribution, an edit of this page, and am in the name of caution mentioning it here first (I see I'm supposed to Be Bold, but the edit I have in mind seems a bit radical...). This page describes almost exclusively finite automata, even going so far as to claim that automata theory is the study of finite automata, and other similar conflations. There's a perfectly excellent entry on finite automata at Finite state machine, even linked in this article. The section of Automata theory detailing the description/notation of DFAs is arguably better (more detailed), although there is a link from Finite state machine to State diagram, which largely rectifies this weakness.

I propose that Automata theory ought to have a high-level description of automata theory in general; its place in computing science and its history for example. There is also room for sub-sections on DFAs, PDAs, Turing Machines, and other automata, condensed from the material in those entries. The additional detail currently given in this entry should be moved to Finite State Machine, or arguably to State Diagram. --jholman 04:12, 11 Jan 2005 (UTC)

Go for it! This sounds like an excellent idea to me. You might also slip in mention of infinite word automata, tree automata...

You may want to mention Buchi automata as well. The language they accept are infinite strings which enter an accept state an infinite number of times. I don't know much of the theory, but I know Anil Nerode (of the Myhill-Nerode theorem) is currently researching them. TooMuchMath 00:55, 2 February 2006 (UTC)

Your definition of automaton is very hard to understand for a beginner. You use characters that I have no idea of their meaning (e.g. "w" at the end). I was following you up to that point.

JHolman is right, this article's definition of automata theory is bull. I've put a {Disputed} template on it, and will edit it when I've got the time. (Unless someone beats me to it...) Qwertyus 10:46, 21 December 2005 (UTC)

[edit] Applications of Automata Theory?

Could anyone possibly add a section discussing some of the applications of automata theory, both in computation and other sciences? For example:
Applications of Automata Theory
Keith 03:13, 19 April 2006 (UTC)

[edit] Copied from semigroup talk page

[edit] Semigroup Applications

I liked seeing the example of applying Semigroups to computer science. Greater reader interest could be generated by listing more examples of Semigroups used in communications theory, partical physics, and other areas of applied mathematics.

iirc, algebraic automata theory makes heavy use of semigroups. far as i can see, there's currently no page on WP covering that stuff. perhaps folks knowledgable in that area would being willing to take that up. Mct mht 05:50, 13 December 2006 (UTC)