Formální jazyky

Formální jazyk je v matematice, logice a informatice libovolná množina posloupností konečné délky nad určitou abecedou. Místo výrazu „posloupnost“ se často používá výraz „slovo“.

Abeceda je obvykle značena symbolem Σ. Zápis Σ* pak označuje jazyk, obsahující všechna slova nad danou abecedou, včetně prázdného slova. Každý jazyk L nad určitou abecedou Σ je pak podmnožinou jazyka Σ*.

Konečné automaty

Konečný automat je teoretický výpočetní model používaný v informatice pro studium formálních jazyků. Popisuje velice jednoduchý počítač, který může být v jednom z několika stavů, mezi kterými přechází na základě symbolů, které čte ze vstupu. Množina stavů je konečná, konečný automat nemá žádnou další paměť, kromě informace o aktuálním stavu. Slovo přijaté automatem je taková posloupnost symbolů ze vstupní abecedy, pro kterou automat skončí v koncovém stavu. Konečný automat dokáže rozpoznávat pouze regulární jazyky. Konečné automaty se používají například v překladačích. V informatice se rozlišuje kromě základního deterministického či nedeterministického automatu také automat Mealyho a Mooreův.

Regulární jazyky

O regulárních jazycích lze dokázat řadu tvrzení. Např. formální jazyk je regulární, právě když:

- je akceptovaný nějakým deterministickým či nedeterministickým konečným automatem,
- může být popsán regulárním výrazem nebo
- může být vygenerován regulární gramatikou

Všechny konečné jazyky, a mnohé jiné, jsou regulární. Například jazyk nad abecedou {a, b} končící na lichý počet symbolů a je regulární.