2. Regulární jazyky

Formální jazyk je regulární právě tehdy, když jej lze generovat regulární gramatikou. Pro regulární jazyky dále platí, že je lze

• přijmout (ne)deterministickým konečným automatem,
• popsat regulárním výrazem.

Tato třída jazyků je uzavřená pro všechny námi definované operace (sjednocení, průnik, rozdíl, doplněk, zřetězení, iterace).

Konečný jazyk

Konečný jazyk (jazyk obsahující konečné množství řetězců) je vždy regulární. Obrácené tvrzení neplatí! Regulární jazyky obsahují i jazyky nekonečné.