Master's thesis

Description of regular languages using predicate logic

Popis regulárních jazyků pomocí predikátové logiky

Bc. Martin Jonáš, UČO 359542
Abstract

Tato diplomová práce se zabývá souvislostí formálních jazyků a predikátové logiky. Je v ní nejprve představen způsob, jakým popisovat formální jazyky pomocí predikátové logiky. Poté je dokázán Büchiho slavný výsledek, podle kterého je libovolný jazyk regulární právě tehdy, když je možné ho popsat monadickou logikou druhého řádu s relacemi „následuje“ a „bezprostředně následuje.“ Dále je dokázán podobný …more

Abstract

The thesis deals with connection between formal languages and predicate logic. First, the way to define a formal language using predicate logic is described. Then the famous result of Büchi, which states that the class of regular languages is equal to the class of languages definable by monadic second order logic with "greater than" and "successor" relations, is proven. Then we prove similar theorem …more

Keywords
formální jazyky regulární jazyky predikátová logika monadická logika druhého řádu monadic second order logic star-free Ehrenfeucht-Fraïsse lokálně prahově testovatelné jazyky locally treshold testable languages
Thesis description
Přehledně prezentujte základní výsledky o použití monadické logiky druhého řádu a jejích fragmentů k popisu regulárních jazyků. Všechny dokázané výsledky ilustrujte na příkladech.
Administrative information
The thesis has been checked:
27/5/2014 05:31, doc. Mgr. Michal Kunc, Ph.D., UČO 2906
Full text of thesis
522,7 KB / file PDF
Language used
Czech Czech
Defence date
24/6/2014
The thesis was defended successfully

Supervisor

doc. Mgr. Michal Kunc, Ph.D., UČO 2906
ÚMS Ústavy PřF MU

Reader

doc. RNDr. Petr Novotný, Ph.D., UČO 172743
KTP FI MU

Literature

  • STRAUBING, Howard. Finite automata, formal logic, and circuit complexity. Boston: Birkhäuser, 1994, xii, 226. ISBN 3764337192.
  • DIEKERT, Volker and Paul GASTIN. First-order definable languages. Amsterdam University Press, 2008, p. 261-306. ISBN 978-90-5356-576-6.
Cite this text
Masaryk University Faculty of Informatics
Programme
Informatics
Field of Study

Theses on a related topic

List of theses with an identical keyword.

Similar documents

  • 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.