tag:blogger.com,1999:blog-3722233.post5924614008711571824..comments2023-05-28T20:30:27.485-05:00Comments on Computational Complexity: A question in Formal Lang Theory about Size of Desc of Languages.Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-3722233.post-65148517890990083202016-01-13T10:49:51.523-06:002016-01-13T10:49:51.523-06:00Anonymous, THanks
Bruno- the lang you seek is in t...Anonymous, THanks<br />Bruno- the lang you seek is in the paper Anonymous referenced<br /><br />GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-38953043899594815242016-01-12T05:48:28.033-06:002016-01-12T05:48:28.033-06:00This is the second time I read a post of yours abo...This is the second time I read a post of yours about sizes of DFAs and NDFAs, and I think of asking a (perhaps obvious) question: Is a language L known that may be computed by an NDFA of size S, but where every L_n (n-bit segment) requires DFAs of size 2^S? (i.e., the same size-S NDFA needs DFAs of size 2^S at every length)<br /><br />I was once told that there was a very hard question around sizes of DFAs vs sizes of NDFAs, but I cannot remember exactly which question it was.Brunohttps://www.blogger.com/profile/07463033182343789250noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-28769837103998315982016-01-12T02:02:37.062-06:002016-01-12T02:02:37.062-06:00I think you can find a reasonable answer in the fo...I think you can find a reasonable answer in the following paper:<br /><br />Albert R. Meyer, Michael J. Fischer:<br />Economy of Description by Automata, Grammars, and Formal Systems. SWAT (FOCS) 1971<br />http://dx.doi.org/10.1109/SWAT.1971.11<br /><br />Take a look at Proposition 6. It gives you a regular language L_n such that the following conditions hold:<br /><br />(1) L_n has a DPDA of size poly(n), and<br />(4) any DFA for L_n has size doubly exponential in n.<br /><br />Now (4) => (2) any NFA for L_n has size exponential in n:<br />because from a smaller NFA you would get a smaller DFA.<br /><br />Finally, (3) L_n has an NFA of size exponential in n:<br />this is by direct construction (it suffices to consider exponentially many {0,1}-suffixes, and for each of them build an exponentially large NFA for the prefix).<br /><br />Does that make sense to you?<br /><br />This example is not very tight, though: it has poly instead of n and so on.<br /><br />Dmitry Chistikov<br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-76661228620088614412016-01-11T11:39:53.620-06:002016-01-11T11:39:53.620-06:00L_n is the one-elements set containing just the on...L_n is the one-elements set containing just the one very long<br />string a^{2^n}. You misread it as<br /><br />L_n = {a^{2^n} | n\in N} which would not make sense since<br />n is being used in two places.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-78395563131298409682016-01-11T11:25:13.495-06:002016-01-11T11:25:13.495-06:00L^n={a^2^n} isn't regular, so how can you talk...L^n={a^2^n} isn't regular, so how can you talk about its NDFA size?Anonymousnoreply@blogger.com