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.

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


	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


	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:

Sentence

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

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