search

nicki-krizek / tul-szz-it-nv

Otazky ke SZZ TUL NV IT 2015/2016
27 stars 21 forks source link

Okruh 8 - Konečné automaty #11

Closed nicki-krizek closed 7 years ago

nicki-krizek commented 8 years ago

8. - Konečné automaty

Autor Reviewer Stav
@tomaskrizek :eyes:

TODO

nicki-krizek commented 8 years ago

Hotovo, může se dělat review.

johnymachine commented 8 years ago

neprohlížel jsem to uplne dokladne, ale v jedne ze tech dvou otazke by asi jeste mohla byt definice jazyka

johnymachine commented 8 years ago

Jeste by na zacatku mohlo co to je a k cemu to je:

NA wiki je to celkem dobre tak to nejak pokratit

Konečný automat (KA, též FSM z anglického finite state machine, či DFA z anglického deterministic finite automaton) je teoretický výpočetní model používaný v informatice pro studium formálních jazyků. Popisuje velice jednoduchý počítač, který může být v jednom z několika stavů, mezi kterými přechází na základě symbolů, které čte ze vstupu. Množina stavů je konečná (odtud název), konečný automat nemá žádnou další paměť, kromě informace o aktuálním stavu. Konečný automat je velice jednoduchý výpočetní model, dokáže rozpoznávat pouze regulární jazyky. Konečné automaty se používají při vyhodnocování regulárních výrazů, např. jako součást lexikálního analyzátoru v překladačích. V informatice se rozlišuje kromě základního deterministického či nedeterministického automatu také automat Mealyho a Mooreův.

johnymachine commented 8 years ago

Zde také pěkně http://www.matematika.cz/konecny-automat

johnymachine commented 8 years ago

co jsou to ty uzávěrové vlastnosti bud bych to tam dal nebo bych to promazl =)

jeste tu je takovy pekny uvod clanek: http://www.matematika.cz/formalni-jazyky

nicki-krizek commented 8 years ago

Uzaverove vlasnosti jsem pridal. Shrnuti KA se mi nechce vymyslet, kdyztak tam neco dej :)

johnymachine commented 8 years ago

JJ planuji to nějak projet a trochu upravit... =)

johnymachine commented 8 years ago

Ty vlastnosti se určitě naučím. =)

Ps jak to fungovalo, sestavím několik jednodušších KA a pak je spojím skrze Start stav? Tím vznikne NKA a pak ho převedu na DKA?

nicki-krizek commented 8 years ago

To spojeni muze byt ruzne. Pokud mas jazyky L1 a L2 a chces aby vysledny automat rozeznaval slova z L1 nebo z L2, potom je spojis pres start stav. Pokud ale chces rozpoznavat takovy slova, ktera zacinaji slovem z L1 a konci slovem z L2, potom je spojis za sebe, tzn koncove stavy prvniho automatu bys privedl do pocatecniho stavu druheho automatu.

johnymachine commented 8 years ago

JJ dik, nejak jsem to poopravil a doplnil. Nakonec mi to přišlo vlastne dobre

johnymachine commented 8 years ago

trochu jsem přemýšlel nad pravdivostí toho automatu "rozeznává sudý počet nul" najednou si však nejsem jistý a nula mi přijde sudá (i podle dalších zdrojů), pokud je to tak, tak to ten automat neumí ne? =)

edit: už to vidím, jen ten obrázek není úplně přesný