Content deleted Content added
Loadmaster (talk | contribs) →DFA cannot recognize anbn?: new section |
Deltahedron (talk | contribs) →DFA cannot recognize anbn?: infinitely many words |
||
Line 98:
: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)
:The wording is intended to describe the language <math>\{ a^n b^n : n \in \mathbf{N} \}</math> which has infinitely many words (indeed, exactly one of length 2''n'' for every ''n''≥0) and I think it does so. This is not a regular language, and cannot be recognised by a DFA. [[User:Deltahedron|Deltahedron]] ([[User talk:Deltahedron|talk]]) 19:38, 27 January 2014 (UTC)
| |||