Formální jazyk L je v matematice, logice a informatice množina konečných posloupností prvků odvozených ze zadané konečné množiny A symbolů. Mezi běžnějšími možnostmi, které se vyskytují v aplikacích, může být formální jazyk považován za analogický (1) sbírce slov nebo (2) sbírce vět. V případě 1 se množina A nazývá abeceda L, jejíž prvky se nazývají slova. V případě 2 se množina A nazývá lexikon nebo slovní zásoba L, jejíž prvky se pak nazývají věty. V každém případě matematická teorie, která zachází s formálními jazyky obecně, je známá jako teorie formálního jazyka.
Ačkoli je běžné slyšet termín formální jazyk používaný v jiných kontextech pro označení způsobu vyjadřování, který je disciplinovanější nebo přesnější než každodenní řeč, smysl formálního jazyka diskutovaný v tomto článku je omezen na jeho význam v teorii formálního jazyka.
Abeceda může být , A řetězec nad tím, že abeceda může být .
Typický jazyk nad touto abecedou, obsahující tento řetězec, by byla množina všech řetězců, které obsahují stejný počet symbolů a .
Prázdné slovo (tj. length-zero string) je povoleno a často je označeno , nebo . Zatímco abeceda je konečná množina a každý řetězec má konečnou délku, jazyk může mít nekonečně mnoho členských řetězců (protože délka slov v něm může být neomezená).
Otázka často kladená ohledně formálních jazyků je „jak obtížné je rozhodnout, zda dané slovo patří do určitého jazyka?“
To je doména teorie vyčíslitelnosti a teorie složitosti.
Formální jazyk může být specifikován mnoha různými způsoby, například:
Několik operací může být použito k vytvoření nových jazyků z daných. Předpokládejme a jsou jazyky nad nějakou běžnou abecedou.
Automaty, jazyky a programování.