Matematické Fórum

Nejprve sestrojme automat pro jazyk, který nemusí odpovídat danému regexpu, ale splňuje druhou podmínku (slova v jazyku jsou binárně zapsané součty dělitelné 541, nadbytečná znaménka + přitom ignorujeme). Za množinu stavů zvolíme množinu dvojic (a,b) celých čísel od 0 do 540. Číslo a bude rovno zbytku aktuálně načítaného sčítance mod 541, číslo b bude odpovídat součtu předchozích sčítanců mod 541. Počáteční stav je (0,0).

Ze stavu (a,b) se načtením nuly automat dostane do stavu (2a mod 541,b), načtením jedničky do stavu (2a+1 mod 541,b), načtením plusu do stavu (0,a+b mod 541). Přijímající budou ty stavy (a,b), pro které je a+b dělitelné 541.

Nyní tento automat upravíme tak, aby akceptoval pouze korektně  zapsané vstupy. S každým stavem (a,b) do něj přidáme stav (a,b)', který odpovídá tomu, že další znak musí být číslo. Navíc přidáme stav FAIL, do kterého automat spadne, pokud se na vstupu objeví něco nekorektního. Počáteční stav nyní bude (0,0)', přechodovou funkci snadno domyslíš.

↑ Padawancs:Představuj si, že píšeš program na rozpoznání toho jazyka, který musí odpovědět "patří"/"nepatří" hned když načte slovo. Ten program bude mít tři proměnné: int a = součet předchozích sčítanců mod 541, int b =aktuální sčítanec mod 541, bool x=pravdivostní hodnota výroku "další znak musí být cifra".
1) Z významu těchto proměnných plyne, jak se budou měnit (pro proměnné a,b jsem to popsal výše, proměnná x je na začátku true, s načtením cifry se mění na false a s načtením + na true).
2) Pokud máme konečně mnoho proměnných a každá nabývá konečně mnoho hodnot, stačí nám automat s konečným počtem stavů, kde každý stav odpovídá trojici hodnot proměnných.

Která z částí 1) a 2) není jasná a proč?