Monday, January 11, 2016
A question in Formal Lang Theory about Size of Desc of Languages.
(This post is inspired by me thinking more about this blog entry and this paper.)
Upper bounds on n are really O(n).
Lower bounds of f(n) are really Omega(f(n))
DPDA = Deterministic Push Down Automata
NDFA = Nondet. Finite Aut.
DFA = Det. Finite Aut.
It is known that FOR ALL n there is a lang Ln such that there is an NDFA of size n, but ANY DFA for Ln is of size at least 2n : Ln = (a,b)*a(a,b)n. for DFA-exactly 2n, NDFA- n+2. One can also get 2n and n.
It is known that FOR ALL n there is a lang Ln such that there is a DPDA of size n, but ANY NDFA for Ln is of size at least roughly 2n size: Ln={a2n }. (ADDED LATER TO CLARIFY- NOTE THAT
Ln is a one-element set, hence regular.)
Can we acheive both at the same time? Is the following true: for all n there exists Ln such that
1) There is a size n DPDA for Ln.
2) Any NDFA for Ln requires size 2n.
3) There IS an NDFA for Ln of size 2n.
4) Any DFA for Ln requires size 22n.
If we replace DPDA with PDA then { (a,b)*a(a,b)2n } works.
Subscribe to:
Post Comments (Atom)
L^n={a^2^n} isn't regular, so how can you talk about its NDFA size?
ReplyDeleteL_n is the one-elements set containing just the one very long
ReplyDeletestring a^{2^n}. You misread it as
L_n = {a^{2^n} | n\in N} which would not make sense since
n is being used in two places.
I think you can find a reasonable answer in the following paper:
ReplyDeleteAlbert R. Meyer, Michael J. Fischer:
Economy of Description by Automata, Grammars, and Formal Systems. SWAT (FOCS) 1971
http://dx.doi.org/10.1109/SWAT.1971.11
Take a look at Proposition 6. It gives you a regular language L_n such that the following conditions hold:
(1) L_n has a DPDA of size poly(n), and
(4) any DFA for L_n has size doubly exponential in n.
Now (4) => (2) any NFA for L_n has size exponential in n:
because from a smaller NFA you would get a smaller DFA.
Finally, (3) L_n has an NFA of size exponential in n:
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).
Does that make sense to you?
This example is not very tight, though: it has poly instead of n and so on.
Dmitry Chistikov
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)
ReplyDeleteI 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.
Anonymous, THanks
ReplyDeleteBruno- the lang you seek is in the paper Anonymous referenced