Název: Dvoustranné automaty
Překlad názvu: Biautomata
Autoři: Klouček, Miloš ; Holub, Štěpán (vedoucí práce) ; Kozlík, Andrew (oponent)
Typ dokumentu: Bakalářské práce
Rok: 2014
Jazyk: cze
Abstrakt: [cze] [eng]
Práce se zabývá konečnými automaty a jejich schopností popisovat zajímavé třídy regulárních jazyků. Nejdříve je zavedena základní terminologie konečných automatů a formulovány jejich základní vlastnosti. Poté je pozornost věnována možnosti konečný automat rozšířit na dvoustranný automat přidáním zpětné přechodové funkce a zkoumání vlastností takto rozšířeného automatu. Důraz je kladen především na srovnání obdobných vlastností dvoustranných a konečných automatů. V druhé části práce je užitečnost nabytých poznatků demonstrována v podobě jednoduššího důkazu slavné Simonovy věty charakterizující po částech testovatelné jazyky. Tento důkaz je lehce modifikovaným výsledkem O. Klímy a L. Poláka. Powered by TCPDF (www.tcpdf.org) This paper is focused on finite automata and their ability to recognize certain significant classes of regular languages. First of all we define core terms of the theory of finite automata, then we proceed to provide an overview of their properties. Thereafter we focus on extending finite automata into biautomata by equipping them by an extra "backwards" transformation function and on examining properties of such structures. While doing so we especially focus on comparing similar properties of automata and biautomata. In the second part of this paper we demonstrate the utility of biautomata by providing an improved proof of famous Simon's theorem, which characterizes piecewise testable languages. This proof is a slightly modified version of the result of O. Klíma a L. Polák. Powered by TCPDF (www.tcpdf.org)
Klíčová slova: Dvoustranný automat; Konečný automat; Po částech testovatelné jazyky; Simonova věta; Syntaktický automat; Biautomaton; Finite automaton; Piecewise testable languages; Simon's theorem; Syntactic automaton

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/64008

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-333152


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Bakalářské práce