Historie: • 10-pos

Umístění: home » mgr-szz » in-pos » 10-pos

Toto je starší verze dokumentu! —-

Obsah

IN-POS 10. Konečné automaty (FA) a logiky nad slovy

IN-POS 10. Konečné automaty (FA) a logiky nad slovy

Zadání

Logika 1.řádu (FOL) a monadická logika 2.řádu (MSOL):
- syntax a sémantika FOL a MSOL,
- principy převoditelnosti mezi FA a formulemi MSOL.
Automaty nad nekonečnými slovy a omega-regulární jazyky.

IA006

Vypracování

Logika prvního řádu (FOL) nad slovy

FOL obecně je zpracována v jiné otázce:
http://statnice.dqd.cz/home:inf:ap14

Syntax


	pozice
	unární predikát značící, že na pozici je písmeno `a`
	pozice je před
$\wedge , ∨ , ¬$	logické spojky
$\forall x, \exists x$	kvantifikace
	+ rovnost

Monadická logika druhého řádu (MSO) nad slovy

Syntax


	pozice
	unární predikát značící, že na pozici je písmeno `a`
	pozice je před
$\wedge , ∨ , ¬$	logické spojky
$\forall x, \exists x$	kvantifikace
	množiny pozic
$x \in X$	leží v
$\forall X, \exists X$	kvantifikace nad množinami pozic

Proměnné ve formuli mohou být:

vázané pomocí kvantifikátoru
volné (zpravidla píšeme za jméno formule)

Sentence

sentence = uzavřená formule = formule bez volných proměnných

Jazyky zadané sentencí MSO

Sentence MSO $\phi$ = vlastnost slov
Slovo $w \in \Sigma^{\star}$ vlastnost $\phi$ :
- má: $\phi$
- nemá: $\phi$
$L(\phi) := \lbrace w \in \Sigma^{star} | w$ $\phi \rbrace$

Valuace formulí

Valuace přiřazuje hodnotu volným proměnným.

Vztah FA a formulí MSOL

Regulární jazyky = jazyky definovatelné MSO.

Převod NFA na formuli MSO

Automaty nad nekonečnými slovy a omega-regulární jazyky

Zdroje

slidy: V. Brožek: Logika a regulární jazyky

mgr-szz/in-pos/10-pos.1560240712.txt.gz · Poslední úprava: 2020/04/12 16:56 (upraveno mimo DokuWiki)

Nahoru

CC Attribution-Noncommercial-Share Alike 4.0 International