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)

Yes, this was pretty egregious. I have altered the example machine model to the form of Arbib's (1969) general automaton, but kept the modern symbols for elements of the tuple (big sigma for the alphabet, and so on). I expanded the history section to emphasize that automata theory predates and overlaps with computer science, and placed it more prominently to clarify the distinction. Terminator 2 really happened (talk) 18:43, 30 March 2021 (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)

WikiProject Computer science comments

One of the Central subjects of CS. Needs more inline references and a bit of cleanup to reach GA. Adam McCormick 08:08, 7 April 2007 (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 ${\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 (talk • contribs) 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))

I think that this article is very badly organized. It starts off with formal and informal description of automata, making it sound as though they are all the same. The descriptions are different for each form of automata, this only includes only DFA and is missing whole variables for more complex specifications. The entire structural variations section is weird, presenting random info in a disorganized manner. For example, nondeterminism is a different class of automata, not just a variation on description. They are equivalent for finite state automata, but not most other models. The classes of automata section does nothing more than list a few (not even a complete list!) different models, saying nothing about them. And the hierarchical list, while correct, would be nothing but confusing to someone who doesn't already know the information that it shows. I don't have time for a rewrite of this scope atm, but I'm going to try to come back to it in a few days. I think this needs to be almost rewritten entirely from scratch to be honest. There is good information here, but there is a lot missing and I don't think the page is structured well. Broswald (talk) 23:08, 3 November 2014 (UTC) Had to come back, just realized that the comparison of power says multidimensional turing machines are the highest power model, despite the fact that they are equivalent to all other turing machines, and the chart even lists them as equivalent!Broswald (talk) 23:11, 3 November 2014 (UTC)

Also in the second paragraph, the article references a "figure at right", but on mobile, it is not to the right which is an expected behavior on mobile. This is a little confusing and probably should be changed. It does seem that this is the least of the article's problems though. Zstrout (talk) 13:13, 5 November 2018 (UTC)

FSA in the main picture

No description is given about what it does, but it appears to recognize bit-strings with an even number of 0's, maybe some statement about this could be added to the description. — Preceding unsigned comment added by 108.3.137.225 (talk) 18:19, 25 February 2015 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified 3 external links on Automata theory. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20111116215852/http://planetmath.org/encyclopedia/CartesianClosedCategory.html to http://planetmath.org/encyclopedia/CartesianClosedCategory.html
• Added archive https://web.archive.org/web/20110915074653/http://planetmath.org/encyclopedia/SequentialMachine3.html to http://planetmath.org/encyclopedia/SequentialMachine3.html
• Added {{dead link}} tag to http://www.cs.ox.ac.uk/people/luke.ong/personal/teaching/moc/pda2up.pdf
• Added {{dead link}} tag to http://www.cs.ox.ac.uk/people/luke.ong/personal/teaching/moc/pda2up.pdf
• Added archive https://web.archive.org/web/20090503173000/http://www.cs.usfca.edu:80/~jbovet/vas.html to http://www.cs.usfca.edu/~jbovet/vas.html

When you have finished reviewing my changes, please set the checked parameter below to true or failed to let others know (documentation at {{Sourcecheck}}).

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 18 January 2022).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 05:55, 22 October 2016 (UTC)

Turning machine

Is that basically the the short name for the revolutionary calender and the wheel of the year? Myhartstands4 (talk) 00:32, 23 September 2020 (UTC)

Wtf

Is this really about 66.199.44.249 (talk) 21:40, 5 December 2022 (UTC)

cellular automata

seems odd that Stephen Wolfram is not mentioned in this wiki article .. 2601:3C5:4202:2B30:B8B2:DC0A:244A:668B (talk) 07:25, 26 January 2023 (UTC)