Zwykły język nieakceptowany przez DFA mający co najwyżej trzy stany

Opisz zwykły język, którego nie może zaakceptować żaden DFA, który ma tylko trzy stany.

Nie jestem do końca pewien, od czego zacząć i zastanawiałem się, czy ktoś mógłby dać mi jakieś wskazówki lub porady. Rozumiem, że lematu pompującego można użyć do udowodnienia, że ​​język nie jest regularny, ale w tym przypadku powinien to być zwykły język. Jeśli ktoś ma jakieś przemyślenia, byłoby to mile widziane.

Można stwierdzić, że lemat pompowania uwzględnia liczbę stanów w DFA. Każdy język zaakceptowany przez DFA ze stanami p spełnia następujący lemat pompowania:$L$$p$

Każde słowo o długości co najmniej p może być podzielone jako w = x y z , gdzie | x y | ≤ p i | y | ≥ 1 , tak że $w$$p$$w=xyz$$|xy| \leq p$$|y| \geq 1$ dla wszystkich i ≥ 0 .$xy^iz \in L$$i \geq 0$

Możesz użyć tej charakterystyki, aby udowodnić, że język wymagastanów p + 1 .$\{0^p\}$$p+1$

Inną metodą jest użycie twierdzenia Myhill - Nerode. Dwa słowa są niejednoznaczne (w odniesieniu do jakiegoś języka L ), jeśli dla jakiegoś słowa z , albo x z ∈ L i y z or L, albo na odwrót. Myhill - Nerode Twierdzenie mówi, że jeśli istnieją p parami inequivalent słowa, to każda DFA dla L ma co najmniej p stany. Na przykład L = { 0 p } można znaleźć p + $x,y$$L$$z$$xz \in L$$yz \notin L$$p$$L$$p$$L = \{0^p\}$$p+1$pary nierówne słowa, a mianowicie .$\epsilon,0,\ldots,0^p$

Odpowiedź Yuvala jest świetna. Prostsze sformułowanie tego, co opisał, polega na tym, że automaty skończone nie mogą liczyć dowolnie wysokie, a kwota, na którą mogą liczyć, jest ograniczona stanami liczbowymi w automatach. Dokładniej, aby automaty mogły liczyć do , potrzebuje p $p$stanów 1 (jeden stan to 0 ).$p+1$$0$

Jest to w istocie cała idea lematu pompującego: jeśli struna jest naprawdę długa, skończone automaty muszą „zapomnieć”, jak wysoko się liczy i zacząć od nowa, pozwalając ci powtarzać sekcję bez końca. .

Dlatego żadnego zwykłego języka, który wymaga policzenia do 3, aby zweryfikować słowo w nim, nie można opisać za pomocą automatów skończonych o rozmiarze 3.

Czy potrafisz wymyślić taki język? (Twój profesor może również oczekiwać, że udowodnisz ten liczący się argument, chociaż w moim programie nauczania zrozumienie lematu pompowania było oczywiste)

$a^3 a^*$$a^3$

inny pomysł, diagonalizacja ! wyliczyć wszystkie 3-lub mniej-stanowe DFA, wziąć sumę wszystkich z nich, a następnie wziąć uzupełnienie. jest to DFA poprzez zwykłe zamknięcie operacji językowych. można to skonstruować za pomocą algorytmu, ale pytanie wymaga jedynie opisu .