# Talk:Automata theory

## 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)

> Unless someone beats me to it

To beat someone, who is wearing glasses, is not fair. I do not consider this.--Efidetum (talk) 15:32, 5 July 2009 (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)

## 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)

In particular, software systems implementing those are of interest.--Efidetum (talk) 16:27, 5 July 2009 (UTC) (still)

added a applications sections.ƒoאŁoɠicƙtalk 01:22, 25 October 2009 (UTC)

## Copied from semigroup talk page

### 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

## 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)

## 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

> can't see a thing I'd improve in it

For instance, the citations, therefore I came here, originally, are improvable. BTW, efidetum (AKA Qwertzde) ... and the American academy.--Efidetum (talk) 16:12, 5 July 2009 (UTC)

## Summary of algorithm/complexity of decision problems for automata

Hopcroft and Ullman have a table in their book that summarizes a load of theorems for given decision problems for each of the automata/language classes. I have created a much enhanced table for wikipedia, that for undecidable problems specifies where exactly in the sarithmetic hiearchy the problem lies, and for decidable problems gives either the complexity class (like for example ${\displaystyle {\mathcal {PSPACE}}}$-complete), or the runtime of an algorithm.

The question I have is where should such a table go? It belongs to automata theory. formal languages, and formal grammars, but also to complexity and decidability. But the table seems out of place for inclusion on any particular page. Any suggestion on where it should go? Hahahaha4 (talk) 15:53, 17 September 2008 (UTC)

## Which level?

Does the "reversible FSA" class is equivalent to the FSA class or not? My opinion is that the reversible FSA is lower than the Aperiodic finite state automaton. --77.126.244.146 (talk) 13:12, 29 March 2009 (UTC)

## Not a complete sentence?

"A FSM is a machine that, given an input of symbols, "jumps", or transitions, through a series of states according to a transition function (which can be expressed as a table). "

"that..." needs an independant clause. "given..." is a dependant clause, as is "through...". something like that anyway...

Sahuagin (talk) 19:53, 7 April 2009 (UTC)

No, this is a complete sentence. To demonstrate that, let me delete several parenthetical asides, to get an equivalent sentence: "A FSM is a machine that jumps through a series of states". I'm guessing that your confusion was to assume that "symbols, jumps, or transitions" was a list of alternatives, which is a bad parse. —Preceding unsigned comment added by JHolman (talkcontribs) 01:41, 7 October 2010 (UTC)
Ah, I see; in that case there are way too many commas. It should then read: "A FSM is a machine that, given an input of symbols, "jumps" or transitions through a series of states according to a transition function (which can be expressed as a table)." Sahuagin (talk) 06:28, 13 February 2011 (UTC)
Um, this all reminds me of a joke I just read about a computer programmer and his wife. She asks him to go to the corner shop to get a carton of milk, and if they have some eggs to get six. Off he goes and comes back with six cartons of milk. 'Why did the you get all that milk', she asks with great restraint. 'They had eggs', replies the husband. Dmcq (talk) 16:10, 15 February 2011 (UTC)

## Uses of Capital/Lowercase Q/q

I just thought I'd say that I find the use of Q/q confusing, in the intro section. Perhaps a new symbol, something that is not q, for the start state? Joseph Fyfield 02:05, 6 March 2011 (UTC)

## Article too narrowly construes the notion of a theory of automata

John von Neumann would not have been so restrictive in his approach to automata theory; his view would have been far broader than might be suggested by the definition given in this article. On need read either The Computer and The Brain or his Hixon Symposium paper to reach this conclusion. Clearly, biological phenomena figured strongly in von Neumann's motivations to develop automata theory, and this article should soundly express this historical fact. William R. Buckley (talk) 05:42, 9 March 2011 (UTC)

## Confusing

I've added the {confusing} template to the page as, well, it just is. I'm quite surprised that this was nominated as a good article. It isn't a good article.

The introduction is okay, but the detailed description makes no sense to a newcomer. Ideally a newcomer should be able to learn about the topic from reading the article. Currently this is not possible as the article text moves too fast through the topic to do this. It starts off with a confusing explanation of automata terminology in one paragraph. It then lapses into the ⟨Q,Σ,δ,q0,A⟩ symbols which are poorly explained. Some example automata might be necessary to facilitate this. Currently it is all very abstract.

After this point it takes great pains to describe variation in automata in great detail. None of this makes any sense at all as the core idea has not properly been explained yet. And it is not clear what the difference is between a **class** and a **category** of automata.

Before you ask, I cannot improve the article as I do not understand the topic. 213.123.192.77 (talk) 12:30, 26 September 2011 (UTC)

Automata theory is very mathematical subject. I do not know that if it can be simplified for layman. (Ashutosh Gupta (talk) 14:11, 26 September 2011 (UTC))

I have made some modifications in *category theory* section and removed the 'confusing' remark. Although, I agree with your comment but I have seen this kind of description in all the computer science books. May be an example will ease the informal description. (Ashutosh Gupta (talk) 07:56, 27 September 2011 (UTC))