Lõpliku automaadi animaator

Selle lehe paarsusautomaadil on kaks olekut ja see loeb jada 101101 — kuus sümbolit —, vajamata kunagi kolmandat. Sööda sellele kuus miljonit sümbolit ja see vajab ikka kahte. Mis on siis see, mida fikseeritud olekute arvuga automaat teha ei suuda? Ja kuidas tõestada, et automaati ei ole olemas, mitte lihtsalt seda, et seda ei õnnestunud leida?

1. Jälgi olemasolevat automaati. Paarsus algab olekus e ja iga 1 vahetab seda. Kuus sümbolit hiljem on see tagasi olekus e ja sisend võetakse vastu. Teel ei kogunenud midagi: automaat on kuuenda sümboli juures täpselt samas seisundis, milles see oleks võinud olla esimese sümboli juures.

   $$e\stackrel{1}{\to }o\stackrel{0}{\to }o\stackrel{1}{\to }e\stackrel{1}{\to }o\stackrel{0}{\to }o\stackrel{1}{\to }e$$

2. See ongi kogu ressurss. DFA mälu on olek, milles see viibib, ja ei midagi muud. Ei loendurit, ei pinu ega linti, kuhu kirjutada. Pärast mis tahes prefiksi lugemist on kõik, mida automaat selle prefiksi kohta teab, see, millises oma k olekust see parajasti asub.

   $$|Q|=k⟹\text{at most }k\text{ distinguishable pasts}$$

3. Nii et leia midagi, mis vajab selgelt rohkem. Võta sõned, mis koosnevad mingist arvust nullidest, millele järgneb täpselt sama palju ühtesid. 01 on selline, 0011 on selline, 001 ei ole ja ka 0110 ei ole.

   $$L=\{0^n{1}^n:n\ge 0\}$$

4. Oleta, et k olekuga DFA tuvastab selle. Ära küsi, milline automaat välja näeb — seda ei öelda sulle kunagi. Sööda sellele lihtsalt k+1 prefiksit, mis koosnevad 0 kuni k nullist, ja pane tähele, kuhu igaüks neist selle jätab.

   $$0^0,0^1,\dots ,0^k⟶k+1\text{ strings into }k\text{ states}$$

5. Dirichlet' printsiip. Prefikseid on rohkem kui olekuid, seega sattuvad kaks neist samasse kohta. Nimetagem neid 0ⁱ ja 0ʲ, kus i on väiksem kui j. Alates sellest hetkest ei suuda automaat neil vahet teha, ja mitte sellepärast, et see oleks halvasti kavandatud. Olek on ainus, mis tal on, ja need kaks sõnet viisid selle samasse olekusse.

   $${\delta }^{\ast }(q_0,0^i)={\delta }^{\ast }(q_0,0^j),i<j\le k$$

6. Nüüd sööda mõlemale jätkule sama asja: i ühte. Sama algolek, samad sümbolid, seega sama lõppolek ja seega sama otsus. Automaadil pole võimalust teha midagi muud.

   $${\delta }^{\ast }(q_0,0^i{1}^i)={\delta }^{\ast }(q_0,0^j{1}^i)$$

7. Ja need kaks otsust peavad erinema. 0ⁱ1ⁱ omab kattuvat arvu ja kuulub hulka; 0ʲ1ⁱ mitte, sest j ei ole i. Üks tuleb vastu võtta ja teine tagasi lükata, kuid automaat annab neile sama vastuse. See, mis murdub, on eeldus, et see oli olemas.

   $$0^i{1}^i\in L,0^j{1}^i\notin L$$

8. Loe argumenti uuesti ja pane tähele, mida selles kunagi ei ilmunud: k väärtust. Kaks — paarsusautomaadi enda suurus — või kaks miljardit: k+1 prefiksit on igal juhul rohkem kui k olekut. Seades aga n-ile ülempiiri, muutub keel kohe lõplike olekutega keeleks: kuni N-i vastavusse viimiseks on vaja 2N+2 olekut, seega 22 olekut N = 10 korral ja 202 olekut N = 100 korral.

   $$\{0^n{1}^n:n\le N\}\text{needs}2N+2\text{states}$$