Stav > a b c d X Y _ q0 "(q0, >, R)" "(q1, a, R)" "(qrej, -, -)" "(qrej, -, -)" "(qrej, -, -)" -- -- "(qrej, -, -)" q1 -- "(q1, a, R)" "(q2, b, R)" "(qrej, -, -)" "(qrej, -, -)" -- -- "(qrej, -, -)" q2 -- "(qrej, -, -)" "(q2, b, R)" "(q3, c, R)" "(qrej, -, -)" -- -- "(qrej, -, -)" q3 -- "(qrej, -, -)" "(qrej, -, -)" "(q3, c, R)" "(q4, d, R)" -- -- "(qrej, -, -)" q4 -- "(qrej, -, -)" "(qrej, -, -)" "(qrej, -, -)" "(q4, d, R)" -- -- "(qret, _, L)" qret "(q00, >, R)" "(qret, a, L)" "(qret, b, L)" "(qret, c, L)" "(qret, d, L)" "(qret, X, L)" "(qret, Y, L)" -- q00 -- "(q11, X, R)" "(q12, Y, R)" "(qrej, -, -)" "(qrej, -, -)" "(q00, X, R)" "(q00, Y, R)" "(qacc, -, -)" q11 -- "(q11, a, R)" "(q12, Y, R)" "(qret, X, L)" "(qrej, -, -)" "(q11, X, R)" "(q11, Y, R)" "(qrej, -, -)" q12 -- -- "(q12, b, R)" "(q13, X, R)" "(qret, Y, L)" "(q12, X, R)" "(q12, Y, R)" "(qrej, -, -)" q13 -- -- -- "(q13, c, R)" "(qret, Y, L)" "(q13, X, R)" "(q13, Y, R)" "(qrej, -, -)" > X X Y Y Y X X Y Y Y d _ q00 ##### Sheet/List 2 ##### Stav > 0 1 _ q0 "(q0, >, R)" "(q1, 0, R)" "(q2, 1, R)" "(qacc, -, -)" q1 -- "(q1, 0, R)" "(q2, 1, R)" "(qacc, -, -)" q2 -- "(q3, 0, R)" "(q2, 1, R)" "(qacc, -, -)" q3 "(q3, 0, R)" "(q3, 1, R)" "(q3, _, R)" ##### Sheet/List 3 ##### Stav "(>, >, >)" "(a, _, _)" "(b, _, _)" "(_, _, _)" "(_, X, X)" "(_, >, >)" "(_, X, >)" "(_, >, X)" q0 "(q0, ([>, R], [>, R], [>, R]))" "(q0, ([a, R], [X, R], [_, S]))" "(q0, ([b, R], [_, S], [X, R]))" "(q1, ([_, S], [_, L], [_, L]))" -- -- -- -- q1 -- -- -- "(q1, ([_, S], [X, L], [X, L]))" qacc qrej qrej ##### Sheet/List 4 ##### Stav "(>, >)" "(a, >)" "(b, >)" "(c, >)" "(_, >)" "(c, _)" "(b, _)" "(b, X)" "(a, X)" "(>, X)" "(Y, X)" "(Y, >)" q0 "(q0, ([>, R], [>, S]))" "(q1, ([a, R], [>, S]))" "(qrej, -, -)" "(qrej, -, -)" "(qrej, -, -)" -- -- -- -- -- q1 -- "(q1, ([a, R], [>, S]))" "(q2, ([b, R], [>, S]))" "(qrej, -, -)" "(qrej, -, -)" -- -- -- -- -- q2 -- "(qrej, -, -)" "(q2, ([b, R], [>, S]))" "(q3, ([c, R], [>, S]))" "(qrej, -, -)" -- -- -- -- -- q3 -- "(qrej, -, -)" "(qrej, -, -)" "(q3, ([c, R], [>, S]))" "(qret, ([_, L], [>, R]))" -- -- -- -- -- qret "(qfin, ([>, R], [>, S]))" "(qret, ([a, L], [>, S]))" "(qret, ([c, L], [X, R]))" "(qret, ([b, L], [_, L]))" "(qret, ([b, L], [X, S]))" "(qret, ([a, L], [X, S]))" "(qfw, ([>, R], [X, S]))" "(qret, ([Y, L), [X, S]))" "(qret, ([Y, L], [>, S]))" qfw "(qrej, -, -)" "(qret, ([Y, L], [>, S]))" "(qrej, -, -)" "(qret, ([Y, L], [X, S]))" "(qfw, ([a, R], [eps, L]))" "(qfw, ([Y, R], [X, S]))" "(qfw, ([Y, R], [>, S]))" qfin "(qfin, ([a, R], [>, S]))" "(qrej, -, -)" "(qacc, -, -)" "(qfin, ([Y, R], [>, S]))" > a a Y b c c c _ > _ _ _ qfw ##### Sheet/List 5 ##### Stav "(>, >)" "(a, _)" "(b, _)" "(_, _)" "(a, X)" "(b, X)" "(a, >)" "(b, >)" "(a, a)" "(a, b)" "(b, a)" "(b, b)" q0 "(q0, ([>, R], [>, R]))" "(q1, ([a, R], [X, R]))" "(q1, ([b, R], [X, R]))" "(qret1, ([_, L), [_, L]))" -- -- -- -- -- -- -- -- q1 -- "(q0, ([a, R], [_, S]))" "(q0, ([b, R], [_, S]))" "(qrej, -, -)" -- -- -- -- -- -- -- -- qret1 "(qfw1, ([>, R], [>, R]))" -- -- -- "(qret1, ([a, L), [X, L]))" "(qret1, ([b, L), [X, L]))" "(qret1, ([a, L), [>, S]))" "(qret1, ([b, L), [>, S]))" -- -- -- -- qfw1 -- "(qret2, ([a, S), [_, L]))" "(qret2, ([b, S), [_, L]))" -- "(qfw1, ([a, R], [a, R]))" "(qfw1, ([b, R], [b, R]))" -- -- -- -- -- -- qret2 -- -- -- -- -- -- "(qfw2, ([a, S], [>, R]))" "(qfw2, ([b, S], [>, R]))" "(qret2, ([a, S), [a, L]))" "(qret2, ([a, S), [b, L]))" "(qret2, ([b, S), [a, L]))" "(qret2, ([b, S), [b, L]))" qfw2 -- -- -- "(qacc, -, -)" -- -- -- -- "(qfw2, ([a, R], [a, R]))" "(qrej, -, -)" "(qrej, -, -)" "(qfw2, ([b, R], [b, R]))" ##### Sheet/List 6 ##### Stav "(>, >)" "(a, _)" "(_, _)" "(a, >)" "(a, X)" "(a, 2)" "(a, 1)" "(_, >)" "(_, 1)" "(_, 2)" "(_, X)" q0 "(q0, ([>, R], [>, R]))" "(q1, ([a, R], [_, S]))" "(qacc, -, -)" -- -- -- -- -- -- -- -- q1 -- "(q2, ([a, R], [1, R]))" "(qacc, -, -)" -- -- -- -- -- -- -- -- q2 -- "(q3, ([a, R], [_, S]))" "(qrej, -, -)" -- -- -- -- -- -- -- -- q3 -- "(qs, ([a, R], [2, R]))" "(qrej, -, -)" -- -- -- -- -- -- -- -- qs -- "(ql, ([a, R], [_, S]))" "(qacc, -, -)" -- -- -- -- -- -- -- -- ql -- "(qs, ([a, R], [X, R]))" "(qret, ([_, L], [_, L]))" -- -- -- -- -- -- -- -- qret "(qfw, ([>, R], [>, R]))" -- -- "(qret, ([a, L], [>, S]))" "(qret, ([a, L], [X, L]))" "(qret, ([a, L], [2, L]))" "(qret, ([a, L], [1, L]))" -- -- -- -- qfw -- "(qbw, ([a, S], [_, L]))" "(qacc, -, -)" -- "(qfw, ([a, R], [X, R]))" "(qfw, ([a, R], [2, R]))" "(qfw, ([a, R], [1, R]))" -- "(qret2, ([_, L], [1, L]))" "(qret2, ([_, L], [2, L]))" "(qret2, ([_, L], [X, L]))" qbw -- -- -- "(qfw, ([a, S], [>, R]))" "(qbw, ([a, R], [X, L]))" "(qbw, ([a, R], [2, L]))" "(qbw, ([a, R], [1, L]))" "(qacc, -, -)" "(qret2, ([_, L], [1, L]))" "(qret2, ([_, L], [2, L]))" "(qret2, ([_, L], [X, L]))" qret2 "(qdelfw, ([>, R], [>, R]))" -- -- "(qret2, ([a, L], [>, S]))" "(qret2, ([a, L], [1, L]))" "(qret2, ([a, L], [2, L]))" "(qret2, ([a, L], [X, L]))" -- -- -- -- qdelfw -- "(qdel, ([a, S], [_, L]))" -- -- "(qdelfw, ([a, S], [X, R]))" "(qdelfw, ([a, S], [2, R]))" "(qdelfw, ([a, S], [1, R]))" -- -- -- -- qdel -- -- -- -- "(qdelbw, ([a, S], [_, L]))" "(qrej, -, -)" -- -- -- -- -- qdelbw -- -- -- "(qfw, ([a, S], [>, R]))" "(qdelbw, ([a, S], [X, L]))" "(qdelbw, ([a, S], [2, L]))" "(qdelbw, ([a, S], [1, L]))" -- -- -- -- > a a a a a a a a a > 1 2 X X q0 "Nulový počet áček, 0 není prvočíslo, přijmi" q1 "Je-li #a(w)=1, přijmi, 1 není prvočíslo, pokud pokračujeme v načítání áček, zapiš 1 na prac. pásku" q2 "Je-li #a(w)=2, nepřijmi, 2 je prvočíslo" q3 "Je-li #a(w)=3, nepřijmi, 3 je prvočíslo, je-li na vstupu další áčko, přepni se do stavu qs (sudý počet áček) a zapiš 2 na prac. pásku" qs "#a(w)=2k, dalším áčkem se přepni do ql, prázdné políčko = #a(w) je dělitelný 2, tudíž w není prvočíslo -> přijmi" ql "#a(w)=2k+1, dalším áčkem se přepni do qs a zapiš X na prac. pásku, prázdné políčko = návrat na začátek obou pásek" qret "Prošli jsme celé slovo na vstupu, zapsali jsme 1, 2, X, X, … při každé dvojici áček a v tomto stavu se vracíme na začátek obou pásek" qfw "S každým symbolem na prac. pásce se posouváme i na vstupní pásce, jsme-li na konci prac. pásky, přepínáme se do qbw" qbw "Na prac. pásce se posouváme dozadu až k >, na vstupní pásce pořád dopředu; jsme-li na začátku prac. pásky, přepínáme do qfw" "Jsme-li na konci vstupu a zároveň na začátku či na konci prac. pásky, znamená to, že #a(w) je dělitelný aktuálním počtem symbolů na prac. pásce -> w není prvočíslo" "Jakýkoliv jiný případ znamená, že se přepneme do stavu qret2" qret2 "Vracíme se na začátek obou pásek, abychom se následně mohli přepnout do stavu qdelfw" qdelfw "Na vstupu (první a) stojíme, na prac. pásce jdeme na její konec (první prázdné pole), poté se přepínáme do stavu qdel a jdeme o jedno pole doleva" qdel "Mažeme poslední neprázdný symbol na prac. pásce a přepínáme se do stavu qdelbw, je-li to č. 2, zamítáme -> #a(w) není dělitelný čísly většími než 2, dělitelnost 2 nebyla prokázána na začátku (stavy q0, …, qs, ql)" qdelbw "Vracíme se na začátek prac. pásky, abychom mohli pokračovat v ověření dělitelnosti nižším číslem" ##### Sheet/List 7 ##### Stav > a X 0 1 _ q "(q, >, R)" "(qa, a, R)" -- "(qacc, -, -)" "(qrej, -, -)" "(qrej, -, -)" qa -- "(qa, a, R)" -- "(qrej, -, -)" "(qb, 1, L)" "(qrej, -, -)" qb "(q0, >, R)" "(qb, a, L)" -- -- -- -- q0 "(q0, >, R)" "(q1, X, R)" "(q0, X, R)" "(q0, 0, R)" "(q0, 1, R)" "(q00, _, L)" q1 -- "(q0, a, R)" "(q1, X, R)" "(q1, 0, R)" "(q1, 1, R)" "(q11, _, L)" q2 "(q0, >, R)" "(q2, a, L)" "(q2, X, L)" "(q2, 0, L)" "(q2, 1, L)" -- q00 "(qrej, -, -)" "(qa, a, R)" "(qacc, -, -)" "(q2, _, L)" "(qrej, -, -)" -- q11 -- "(qa, a, R)" "(qrej, -, -)" "(qrej, -, -)" "(q2, _, L)" -- a a a a 0 0 0 q0 X a X a 0 0 q0 X X X X 0 "q, qa, qb" "Kontrola správného tvaru, povolujeme slovo 0, či posloupnost áček následovaná 1, nepovolujeme posloupnost áček následovanou 0, či prázdné slovo" q0 "Sudý počet áček, tj. áčko na vstupu necháváme" q1 "Lichý počet áček, tj. áčko na vstupu přepisujeme X" q00 "Načetli jsme sudý počet áček, tj. zbytek je 0. První symbol před _ musí být 0." q11 "Načetli jsme lichý počet áček, tj. zbytek je 1. První symbol před _ musí být 1." q2 Návratový stav