6

Question 1

Co je to deterministicky konečný automat

Answer 1

Nejjednodušší formální model počítače
Má konečný počet stavů ve kterých se může nacházet
Zpracovává posloupnost symbolů vybraných z množiny (abeceda automatu )
Nemá paměť
Pracuje v taktech

Question 2

Co je koncový stav

Answer 2

Stač ve kterém se musí automat na konci nacházet aby bylo vstupní slovo přijato

Question 3

Jak lze formálně zapsat konečný automat

Answer 3

Jako uspořádanou pětici Q I f q0 P
Q množina vnitřních stavů
I vstupní abeceda
f množina přechodových funkcí
q0 počáteční stav
P koncový stav

Question 4

Co je to mealyho automat

Answer 4

Podobný jak konečný ale má navíc od konečného automatu výstupní abecedu O
Takze při každém taktu může ale nemusí umístit na výstup jeden ze znaků výstupní abecedy
Výstup záleží na zpracovaném vstupním symbolu i na vnitřním stavu

Question 5

Co je to Mooruv automat

Answer 5

Stejný jako mealyho ale záleží u výstupu jen na aktuálním vnitřním stavu

Question 6

Co ne to zásobníkový automat

Answer 6

Je to rozšíření konečného automatu o teoreticky neomezenou paměť (zásobník )
Ze zásobníku je přístupný vždy pouze vrchní prvek pro zápis i čtení
Dívá se v každém taktu na svůj vnitřní stav, právě čtený symbol vstupního slova a na vrchol zásobníku , podle toho dal rozhodne další vnitřní stav.
Slovo přijme pokud po přečtení celého vstupního slova je v koncovém stavu nebo pokud je prázdný zásobník

Question 7

Co je to nedeterministický konečný automat

Answer 7

Na základě vnitřního stavu a čteném symbolu vstupního slova přejde do libovolné množiny stavů, vybere náhodně do jakého stavu přejde.
Počátečních stavů může být více automat vybere náhodně
Je tam i epsilon přechod

Question 8

Co ne to epsilon přechod

Answer 8

Přechod díky kterému může změnit automat svůj vnitřní stav, aniž by přečetl symbol vstupního slova.

Question 9

Co je to turinguv stroj

Answer 9

Jedná se o konečný automat s přístupem k externí paměti
Snaží se být co nejvíc univerzální
Turinguv stroj má čtecí hlavu teoreticky nekonečnou pásku a tabulku chování
Tabulka obsahuje m- konfigurace
Oproti konečnému stroji vstupní slovo může přijmout, zamítnou , nebo cyklit

Question 10

Co je to ekvivalence strojů

Answer 10

Stroje jsou ekvivalentní tehdy když pro stejne vstupní slovo mají stejný výsledek, i když na to přijdou jiným způsobem .
Turingovy a postovy stroje jsou ekvivalentní

Question 11

Jaké jsou typy použití turingových strojů

Answer 11

Akceptor vstupní slovo akceptuje nebo zamítne
Generátor běží v cyklovacim režimu a generuje pseudo náhodné řetězce
Algoritmus pokud je problém řešitelný ano ne může být tady

Question 12

Co je to postův stroj

Answer 12

Je to vývojový diagram s jednotnou proměnou typu fronta (FIFO)
Abeceda nad kterou pracuje obsahuje i prázdný symbol
Ma počáteční stav start, kdy je slovo zapsáno do fronty a koncové stavy přijímá a zamítá.
Obsahuje příkaz přiřazení který přidá symbol na konec fronty
Obsahuje logický příkaz který z leva fronty vezme jeden symbol a podle jeho hodnoty větví program
Vstupní slovo je tedy přijmuto nebo zamítnuto v ostatních stavech cykluje

Question 13

Co je to konečný stroj

Answer 13

Vývojový diagram podobný postovemu stroji ale ma proměnnou typu zásobník a čte hodnoty z vrchu zásobníku

Question 14

Co je to Rasp stroj

Answer 14

Je to stroj s přímým přístupem k paměti
Je stejně silný jak turinguv stroj ale je rychlejší pracuje s registry a řídící jednotkou má sadu instrukcí

Question 15

Co jsou to petriho sítě

Answer 15

Slouží k modelování paralelních systémů a systému s diskrétním časem
Slouží k verifikace a tvoření modelu systému

Question 16

Co jsou to C/E petriho sítě

Answer 16

Condition event
Model se skládá z události obdélník a podmínek kroužek

Question 17

Co jsou to P/T petriho sítě

Answer 17

Place transition jsou zde místa a přechody
Místo muže obsahovat víc tokenů
Místo má kapacitu a hrany mají váhu