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.



at

5 comments:

  1. Anonymous11:25 AM, January 11, 2016

    L^n={a^2^n} isn't regular, so how can you talk about its NDFA size?

    ReplyDelete
  2. GASARCH11:39 AM, January 11, 2016

    L_n is the one-elements set containing just the one very long
    string 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.

    ReplyDelete
  3. Anonymous2:02 AM, January 12, 2016

    I think you can find a reasonable answer in the following paper:

    Albert 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

    ReplyDelete
  4. Bruno5:48 AM, January 12, 2016

    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)

    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.

    ReplyDelete
  5. GASARCH10:49 AM, January 13, 2016

    Anonymous, THanks
    Bruno- the lang you seek is in the paper Anonymous referenced

    ReplyDelete