Content deleted Content added
Mike Cline (talk | contribs) m moved Talk:Deterministic finite-state machine to Talk:Deterministic finite automaton: per WP:RM |
Loadmaster (talk | contribs) →DFA cannot recognize anbn?: new section |
||
Line 89:
:''The above discussion is preserved as an archive of a [[WP:RM|requested move]]. <span style="color:red">'''Please do not modify it.'''</span> Subsequent comments should be made in a new section on this talk page. No further edits should be made to this section.</div><!-- Template:RM bottom -->
== DFA cannot recognize ''a<sup>n</sup>b<sup>n</sup>''? ==
The [[Deterministic finite automaton#Advantages and disadvantages|article states]] that: {{quote|1=Many simple languages, including any problem that requires more than constant space to solve, cannot be recognized by a DFA. [...] Another simpler example is the language consisting of strings of the form ''a{{sup|n}}b{{sup|n}}'' — some finite number of ''a'''s, followed by an equal number of ''b'''s.}} I don't think that is correct. Consider the following state diagram:
:S{{sub|0}} → ''a'' → S{{sub|1}} → ''b'' → S{{sub|2}} (''ab'')
:S{{sub|0}} → ''a'' → S{{sub|1}} → ''a'' → S{{sub|3}} → ''b'' → S{{sub|4}} → ''b'' → S{{sub|5}} (''aabb'')
:S{{sub|0}} → ''a'' → S{{sub|1}} → ''a'' → S{{sub|3}} → ''a'' → S{{sub|6}} → ''b'' → S{{sub|7}} → ''b'' → S{{sub|8}} → ''b'' → S{{sub|9}} → (''aaabbb'')
:And so forth.
As long as ''n'' is limited to a specific finite number, it looks like a DFA can indeed be built for the language ''a{{sup|n}}b{{sup|n}}''. Granted, it will take a large number of states (perhaps on the order of 2{{sup|''n''}}?) to embed the counting of ''a'''s and ''b'''s, but it still seems possible. Or did I miss something in the text? — [[User:Loadmaster|Loadmaster]] ([[User talk:Loadmaster|talk]]) 17:48, 27 January 2014 (UTC)
| |||