(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 L

_{n}such that there is an NDFA of size n, but ANY DFA for L

_{n}is of size at least 2

^{n}: L

_{n}= (a,b)

^{*}a(a,b)

^{n}. for DFA-exactly 2

^{n}, NDFA- n+2. One can also get 2

^{n}and n.

It is known that FOR ALL n there is a lang L

_{n}such that there is a DPDA of size n, but ANY NDFA for L

^{n}is of size at least roughly 2

^{n}size: L

^{n}={a

^{2n }}. (ADDED LATER TO CLARIFY- NOTE THAT

L

^{n}is a one-element set, hence regular.)

Can we acheive both at the same time? Is the following true: for all n there exists L

_{n}such that

1) There is a size n DPDA for L

_{n}.

2) Any NDFA for L

_{n}requires size 2

^{n}.

3) There IS an NDFA for L

_{n}of size 2

^{n}.

4) Any DFA for L

_{n}requires size 2

^{2n.}

If we replace DPDA with PDA then { (a,b)*a(a,b)

^{2n}} works.

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