Original title: Dvoustranné automaty
Translated title: Biautomata
Authors: Klouček, Miloš ; Holub, Štěpán (advisor) ; Kozlík, Andrew (referee)
Document type: Bachelor's theses
Year: 2014
Language: cze
Abstract: [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)
Keywords: Biautomaton; Finite automaton; Piecewise testable languages; Simon's theorem; Syntactic automaton; Dvoustranný automat; Konečný automat; Po částech testovatelné jazyky; Simonova věta; Syntaktický automat

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/64008

Permalink: http://www.nusl.cz/ntk/nusl-333152


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Bachelor's theses