Formálne jazyky a automaty

1.

FORMÁLNE JAZYKY A AUTOMATY
prednášky: doc. RNDr. Gabriela Lovászová, PhD.
cvičenie: RNDr. Júlia Tomanová, PhD.

2.

ÚVOD
Čo majú spoločné tieto problémy?
preložiť text z jedného do druhého jazyka
vyhľadať reťazec v texte
navrhnúť logický obvod
interpretovať počítačový program
modelovať rast rastlín
dokázať nevypočítateľnosť funkcie
2

3.

SYNTAX VETY
veta
podmetová
časť
prívlastok
Malá
prísudková
časť
podmet
Ema
prísudok
číta
predmetová
časť
prívlastok
historický
predmet
román.
3

4.

SYNTAX ARITMETICKÉHO VÝRAZU
30 – (5 * 4 + 8)
-
+
30
*
5
8
4
4

5.

VÝHERNÝ AUTOMAT
Výhra: padne PPPP alebo ZZPP
5

6.

MODELOVANIE RASTU RASTLÍN
6

7.

FORMALIZÁCIA JAZYKA
Automat – rozpoznáva jazyk (analýza), návod ako
určiť, či ľubovoľné slovo patrí alebo nepatrí do
jazyka
Gramatika – generuje jazyk (syntéza), návod ako
vygenerovať všetky slová jazyka a žiadne iné
7

8.

NOAM CHOMSKY (1928)
americký matematik, lingvista, filozof
zaoberal sa formalizáciou jazyka (angl.)
8

9.

ALAN TURING (1912-1954)
britský matematik
rozlúštil šifru Enigma
zaoberal sa vypočítateľnosťou funkcií,
formalizáciou pojmu algoritmus
9

10.

JAZYK
Abeceda – ľubovoľná konečná množina symbolov.
Slovo – ľubovoľná konečná postupnosť symbolov abecedy.
– prázdne slovo
Zreťazenie slov x, y je slovo xy.
V* – množina všetkých slov zo symbolov abecedy V.
V+ – množina všetkých neprázdnych slov zo symbolov abecedy V.
Jazyk – ľubovoľná množina slov.
10

11.

OPERÁCIE S JAZYKMI
Zjednotenie jazykov
L M = {s | s L alebo s M}
Zreťazenie jazykov
L M = {st |s L a t M}