most recent 30 from http://mathoverflow.net 2013-05-19T20:54:07Z http://mathoverflow.net/feeds/question/94597 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/94597/proving-that-a-problem-about-grammar-is-unsolvable Jason Li 2012-04-20T04:43:14Z 2012-04-20T04:43:14Z

<p>I came across this problem in the Martin D. Davis book about computability and on page 192, exercise 1(1):</p> <pre><code>show that there is no algorithm to determine of a given grammar G whether L(G) contains at least one word with exactly three symbols. </code></pre> <p>I understand that there is no algorithm to determine whether a given word w belongs to a given language L(G) generated by a given grammar G, and there is no algorithm to determine whether two given L(G1) L(G2) intersect, but the proof constructed a special counter example which might not be suitable for this problem.</p>