most recent 30 from http://mathoverflow.net 2013-05-22T06:12:48Z http://mathoverflow.net/feeds/user/819 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/7155/famous-mathematical-quotes/7306#7306 mic 2009-11-30T19:09:22Z 2009-11-30T19:09:22Z

<p>"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is." --- John von Neumann. (From a 1947 ACM keynote, recalled by Alt in this <a href="http://portal.acm.org/citation.cfm?id=361528" rel="nofollow">1972 CACM article</a>.)</p>

http://mathoverflow.net/questions/1363/regular-languages-and-the-pumping-lemma/1473#1473 mic 2009-10-20T19:36:05Z 2009-10-20T19:36:05Z

<p>Some variants of the pumping lemma are complete for determining whether a language L is regular. For example, consider this two player game:</p> <p>Player 1 picks a positive integer k. Player 2 picks a string w of length k. Player 1 picks a string partition w=abc, with b non-empty. Player 2 picks z so exactly one of {wz, acz} is in L. The last player to make a valid move wins. </p> <p>Then L is regular iff Player 1 has a winning strategy. This comes down to Myhill-Nerode, as mentioned earlier. For a similar example, see <a href="http://doi.acm.org/10.1145/990524.990528" rel="nofollow">Jaffe</a>.</p>