Bakalářská práce

Efektivní implementace algoritmů z teorie formálních jazyků

Effective implementation of Formal Language Theory Algorithms

Matej Lobodáš
Anotace

Táto práca sa zaoberá vytvorením java balíka, ktorý implemetuje štruktúry a algoritmy pre reprezentácie regulárnych jazykov. Konkrétne to sú konečný automat(deterministický, nedeterministický,s epsilon-krokmi), regulárny výraz a regulárna gramatika. Implementované sú metódy na ich načítavanie, výpis, modifikáciu a uchovávanie v formáte XML. Ďalej sa venujeme prevodu medzi jednotlivými reprezentáciami …více

Abstract

The aim of this thesis is to creat java package, which implements structures and alogrithm for regular languages. Namely it is finites state automatun, regular grammar and regular expresion. Implemented are methods for reading, writening, modifiing and storing in XML. In addition there are methods for transformation of representation of regular languages, minimization,kanonization and comparing of regular languages.

Klíčová slova
regulárny jazyk regulárna gramatika rgeulárny výraz konečný stavový automat ekvivalencia automatov Java
Zadání práce
Cílem práce je vytvořit java balík efektivně implementující struktury a algoritmy pro konečné reprezentace regulárních jazyků. Jmenovitě se jedná o implementaci konečných automatů (deterministických, nedeterministických, s epsilon-kroky), regulárních gramatik a regulárních výrazů a funkcí, které umožní jejich načtení, výpis, modifikaci a uložení do souboru (v XML i běžně čitelném formátu - formát odpovědníků). Balík bude také obsahovat funkce pro převod mezi jednotlivými reprezentacemi, algoritmy pro minimalizaci a kanonizaci konečných automatů, pro odstranění nedosažitelných stavů automatu, pro zjištění prázdnosti reprezentovaného jazyka, pro výpočet slova minimální délky v reprezentovaném jazyku, funkce pro sjednocení, průnik a komplement reprezentovaných jazyků. Dále bude balík obsahovat algoritmus pro efektivní zjištění ekvivalence dvou konečných automatů (zdrojem v tomto případě bude článek M. Almeida, N. Moreira, R. Reis: Testing the Equivalence of Regular Languages, DCFS 2010). Součástí práce také bude porovnání efektivity (na malých automatech do 15 stavů) tohoto algoritmu s klasickým algoritmem využívajícím minimalizaci (implementovanou dle algoritmu z článku A. Valmari, P. Lehtinen: Efficient Minimization of DFAs with Partial Transition Functions, STACS 2008) a převod do kanonické formy.
Administrativní informace
Práce zkontrolována:
30. 1. 2011 22:39, prof. RNDr. Jan Strejček, Ph.D., učo 3366
Plný text práce
233,7 KB / soubor PDF
Jazyk práce
slovenština slovenština
Termín obhajoby
24. 6. 2011
Práce nebyla obhájena
Student v rámci svého studia bakalářskou práci obhájil 30. 1. 2012.

Vedoucí

prof. RNDr. Jan Strejček, Ph.D., učo 3366
KTP FI MU

Oponent

prof. RNDr. Jiří Barnat, Ph.D., učo 3496
KTP FI MU
Citovat tuto práci
Masarykova univerzita Fakulta informatiky
Studijní program
Aplikovaná informatika
Obor

Práce na příbuzné téma

Seznam prací, které mají shodná klíčová slova.

Podobné práce
 
Název
Vložil
Vloženo
Práva
Archiv závěrečné práce Matej Lobodáš FI B-AP BcAP uo2b7/7
Lobodáš, M.
4. 1. 2011
Složky
Soubory
Anotace anglicky annotation_english.txt
Lobodáš, M.
4. 1. 2011
Anotace česky annotation.txt
Lobodáš, M.
4. 1. 2011
bc.pdf
Lobodáš, M.
4. 1. 2011
Klíčová slova keywords.txt
Lobodáš, M.
4. 1. 2011
posudek_oponenta.pdf posudek_oponenta.pdf
Barnat, J.
21. 1. 2011
priloha.zip
Lobodáš, M.
4. 1. 2011

  • Přidání souboru

    Soubor nebo složku lze nahrát pomocí tlačítka Přidat.

  • Další operace se soubory

    Podrobnosti lze zjistit označením příslušného řádku.

  • Pohled pro experty

    Pro častou práci je možné zvolit režim Více možností.

  • Vyhledávání souborů

    Vyhledávaný výraz můžete zadat přímo do adresního řádku.

  • Rychlý přístup k souborům

    Pomocí funkce Nedávné je možné se rychle vrátit k právě prohlíženým souborům. Oblíbené soubory je také možné označit Hvězdičkou.