Jaka liczba języków jest akceptowana przez DFA o rozmiarze

Pytanie jest proste i bezpośrednie: w przypadku ustalonego , ile (różnych) języków jest akceptowanych przez DFA o rozmiarze (tj. stanów)? Formalnie stwierdzę to: $n$ $n$ $n$

Zdefiniuj DFA jako , gdzie wszystko jest jak zwykle, a jest funkcją (być może częściową). Musimy to ustalić, ponieważ czasami tylko całkowite funkcje są uważane za prawidłowe. $(Q,\Sigma,\delta,q_0,F)$ $\delta:Q\times\Sigma\to Q$

Dla każdego zdefiniuj relację (równoważność) na zbiorze wszystkich DFA jako: jeżeli i . $n\geq 1$ $\sim_n$ $\mathcal{A}\sim_n\mathcal{B}$ $|\mathcal{A}|=|\mathcal{B}|=n$ $L(\mathcal{A})=L(\mathcal{B})$

Pytanie brzmi zatem: dla danego , jaki jest indeks ? To znaczy, jaki jest rozmiar zestawu ? $n$ $\sim_n$ $\{L(\mathcal{A})\mid\mathcal{A}\textrm{ is a DFA of size }n\}$

Nawet gdy jest funkcją całkowitą, nie wydaje się to łatwe (przynajmniej dla mnie). Wykres może nie być połączony, a stany w podłączonym składniku zawierające stan początkowy mogą być wszystkie akceptowalne, więc na przykład istnieje wiele wykresów o rozmiarze akceptującym . To samo z innymi trywialnymi kombinacjami dla pustego języka i innych języków, których minimalny DFA ma mniej niż stanów. $\delta$ $n$ $\Sigma^*$ $n$

(Naiwna) rekurencja też nie działa. Jeśli weźmiemy DFA o rozmiarze i dodamy nowy stan, to jeśli chcemy zachować determinizm i połączyć nowy wykres (aby uniknąć trywialnych przypadków), musimy usunąć przejście, aby połączyć nowy stan, ale w takim przypadku możemy utracić oryginalny język. $k$

jakieś pomysły?

Uwaga. Ponownie zaktualizowałem pytanie, formalnym oświadczeniem i bez poprzednich elementów rozpraszających uwagę.

— Janoma
źródło

Wyjaśnij: czy masz na myśli „ile różnych języków można zdefiniować za pomocą

stanów?”, Gdzie język definiuje się za pomocą

stanów, jeśli istnieje DFA z

stanami, które je akceptują. Ponadto w przypadku wyrażeń regularnych wyrażenie regularne „a * aaaaaa” z pewnością ma> 1 konkatenacje, ale DFA potrzebuje tylko jednego stanu (dwa, jeśli potrzebujesz osobnego ujścia), prawda?

n

$n$

n

$n$

n

$n$

— Evgenij Thorstensen

Przepraszamy: Na przykład wyrażenia regularnego powinna to być „a a a a a *”, ponieważ pozwala to na dowolną liczbę.

— Evgenij Thorstensen

Definicja

wydaje się bardzo powiązana z pojęciem „głębokości kropek”, z tym wyjątkiem, że pojęcie to zwykle stosuje się do języków bez gwiazd (prawdopodobnie z powodów, które przedstawił @Evgenij Thorstensen).

c (r)

$c(r)$

— mhum,

Trywialna obserwacja: stanów

można użyć do zdefiniowania co najmniej

różnych języków.

n + 1

$n+1$

2^{n}

$2^n$

— Evgenij Thorstensen

Możemy uzyskać trochę więcej, więc

wydaje się OK. Ale liczba automatów n-stanowych wynosi około

(przy założeniu

). Czy możemy uzyskać

2^{Ω (n)}

$2^{\Omega(n)}$

n^{c n} 2^{n} = 2^{c n \log n + n} = 2^{Θ (n \log n)}

$n^{cn}2^n=2^{cn\log n+n} = 2^{\Theta(n\log n)}$

| Σ | = c

$|\Sigma|=c$

2^{ω (n)}

$2^{\omega(n)}$

— Kaveh

Myślę, że to pytanie zostało zbadane wcześniej. Mike Domaratzki napisał ankietę na temat badań w tej dziedzinie: „Wyliczenie języków formalnych”, Bull. EATCS, vol. 89 (czerwiec 2006), 113-133: http://www.eatcs.org/images/bulletin/beatcs89.pdf

— Hermann Gruber
źródło

Artykuł dotyczy dokładnie zadanego pytania, od strony 120 i kolejnych. Jest to funkcja

, a papier daje raczej ciasne ograniczenia (zbliżone do tego, co Kaveh wspomina powyżej), chociaż nie wdychałem wszystkich szczegółów.

g_{k} (n)

$g_k(n)$

— Evgenij Thorstensen

W rzeczy samej. To, czego chcemy, to

lub, według podanej zależności,

, która jest liczbą par nieizomorficznych minimalnych DFA z

stanami nad

alfabetem. Nie przyjrzałem się temu też szczegółowo, ale wydaje się, że znane są tylko granice, a nie dokładne ilości.

g_{k} (n)

$g_k(n)$

f_{k} (n)

$f_k(n)$

n

$n$

k

$k$

— Janoma

I od tego samego autora mamy artykuł na temat liczby odrębnych języków akceptowanych przez automat skończony z n stanami , który podaje nawet wyraźne obliczenia dla

(

)

(

g_{1} (n)

$g_1(n)$

1 \leq n \leq 10

$1\leq n\leq 10$

g_{2} (n)

$g_2(n)$

1 \leq n \leq 6

$1\leq n\leq 6$

g_{3} (n)

$g_3(n)$

1 \leq n \leq 4

$1\leq n\leq 4$

— Janoma