Talk:Automata theory

From Wikipedia, the free encyclopedia

Socrates
Philosophy Portal
This article is within the scope of the WikiProject Philosophy, which collaborates on articles related to philosophy. To participate, you can edit this article or visit the project page for more details.
??? This article has not yet received a rating on the quality scale.
??? This article has not yet received an importance rating on the importance scale.
Automata theory was a good article nominee, but did not meet the good article criteria at the time. There are suggestions below for improving the article. Once these are addressed, the article can be renominated. Editors may also seek a reassessment of the decision if they believe there was a mistake.

Reviewed version: March 8, 2007
This article is within the scope of WikiProject Computer science, which aims to create a comprehensive computer science reference for Wikipedia. Visit the project page for more information and to join in on related discussions.
B rated as B-Class on the assessment scale
High rated as High-importance on the assessment scale

Contents

[edit] Misc

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)

Update: 3 years have passed, and I have never gotten up the energy to do this re-write. I see lots of improvements, but the thing where the opening section equates FSMs and automata-in-general is still there. One of these days I might get to it, haha, but don't count on it. Oh, and while it would be nice to tackle less-basic automata like L-systems or other infinite automata, or even esoteric things I've never heard of like Buchi automata, the first step is to get the basics right.  ;P --jholman (talk) 22:52, 5 March 2008 (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)

--- What about semi-automata? Carnide 13:34, 30 January 2007 (UTC) carnide

[edit] Failed GA

This article failed the GA noms due to lack of inline citations and unexplained jargon. Tarret 20:51, 8 March 2007 (UTC)

I should hope so, since it's not very accurate, either. --jholman (talk) 22:53, 5 March 2008 (UTC)

[edit] GA nomination

I just came to this article for the first time, and can't see a thing I'd improve in it. So I've nominated it as a good article. JulesH 20:40, 20 February 2007 (UTC)

  • I can add some information about operations on automatas with examples (actually the images i've just added are part of my examples). I'll do it this month when I'll have more free time :) --SOMNIVM 00:36, 6 March 2007 (UTC)

I am a big fan of adding diagrams/pictures...however it could have been much clearer if an articulated table of possible outcomes had been added. Jensocan 19:06, 21 June 2007 (UTC)Karin

[edit] Automata vs. finite automata

The article must be renamed to finite state automaton or finite automaton or possibly even finite state machine.

There are many other types of automata:

  • pushdown automata
  • linear bounded automata
  • counter machines
  • Turing machines
  • Petri nets
  • cellular automata
  • the game of Life

etc. etc.

They deserve a general overview article.

Rp

(Yuck, on second reading, I notice that jholman made the same mark above, 2 years ago.)