Seminární práce: Úvod do teorie konečných automatů a formálních jazyků

Přehled základních pojmů
Konečný automat (KA) je abstraktní (virtuální) systém s konečným počtem stavů, na jehož vstup přicházejí symboly vstupní abecedy a KA na jejich příchod reaguje přechodem do následujícího stavu. KA pracuje v diskrétním čase. Je možno jej považovat za abstraktní obraz konkrétního systému, který např. rozpozná řetězec patřící do nějakého formálního jazyka, či nahlásí „poruchový“ stav v případě, že sleduje sekvenci symbolů na svém vstupu a ocitne se v tzv. koncovém stavu.
Později uvedeme stručné definice jednotlivých automatů.
Teorii konečných automatů a formálních jazyků je možno chápat jako součást teorie počítačů (teorie programování, návrh překladačů programovacích jazyků, návrh a specifikace komunikačních protokolů, návrh sekvenčních obvodů počítačových systémů atd.). Teorie konečných automatů je disciplinou teoretické (matematické) informatiky.
Dále je uveden stručný přehled nejzákladnějších pojmů, které mají vztah k problematice zpracované v tomto dokumentu.
Množina je soubor prvků. Zápis množiny provádíme výčtem prvků: {a; b, c, …} nebo zápisem
X = {x; P(x)} nebo X = {x| P(x)}, kde X je množina prvků x, které mají vlastnost P; takových prvků, že výrok P(x) je pravdivý. Množiny zde značíme kapitálkami, prvky verzálkami.
a je prvkem množiny A zapisujeme: a Î A;
b není prvkem množiny B zapisujeme: b Ï B.
Komplikovanější výroky lze specifikovat známým způsobem s využitím funktorů (logických spojek) a kvantifikátorů ve výrazech.

Zápis A Í B vyjadřuje vztah mezi A a B: A je podmnožinou B. Když A Í B a zároveň $x takové, že x Î B a x Ï A, jedná se o vlastní podmnožinu. Zapisujeme A Ì B. U množin nezáleží na pořadí zapsaných prvků. V teorii konečných automatů však často používáme objekty, které se skládají z prvků a na pořadí záleží. Setkáváme se tak s pojmem uspořádané množiny. Pokud záleží na pořadí prvků hovoříme o posloupnostech. Ty zapisujeme do závorek, buď okrouhlých (a1, a2, …, an) jako v tomto dokumentu, nebo úhlových <a1, a2, …, an>. Důležitý druh posloupností, zde užívaných, jsou uspořádané dvojice, tj. posloupnosti o dvou prvcích. Prvky nějaké množiny mohou vstupovat mezi sebou, či s prvky jiných množin v jisté relace.