Original title: Výpočetní historie Turingových strojů a jejich generování gramatikami s rozptýleným kontextem
Translated title: Computational Histories of Turing Machines and Their Generation by Scattered Context Grammars
Authors: Kajan, Dušan ; Soukup, Ondřej (referee) ; Meduna, Alexandr (advisor)
Document type: Master’s theses
Year: 2015
Language: cze
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [cze] [eng]
Cílem této diplomové práce je navrhnout metodu , která by na vstupu očekávala Turingův stroj a na výstupu by byla propagujucí gramatika s roptýleným kontextem . Jazyk výstupní gramatiky by byl tvořený množinou řetězců reprezentující všechny validní výpočetní historie stroje na vstupu . Následně se tato práce zabývá otázkami , které z existence takového algoritmu vystávají , zejména ve vztahu k předpokladům , které dosud o výpočetní síle propagujících gramatik s rozptýleným kontextem existují . Názorné ukázky práce s těmito gramatikami a implementace představeného algoritmu v jazyce Haskell jsou také součástí této diplomové práce . The purpose of this thesis is to show a method, that would transform given Turing machine into propagating scattered context grammar, which language contains all valid computational histories of that particular Turing machine. Afterwards this thesis deals with questions arising from existence of such algorithm, especially in regards to the current knowledge about power of propagating scattered context grammars. Practical examples and implementation of proposed algorithm is also part of this thesis.
Keywords: algorithm; computational history; Haskell; propagating scattered context grammars; scattered context grammars; theory of computation; Turing machine; algoritmus; Haskell; propagujíci gramatiky s rozptýleným kontextem; teoretická informatika; Turingův stroj; výpočetní historie; { gramatiky s rozptýleným kontextem

Institution: Brno University of Technology (web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library.
Original record: http://hdl.handle.net/11012/64036

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


The record appears in these collections:
Universities and colleges > Public universities > Brno University of Technology
Academic theses (ETDs) > Master’s theses