Definice: Nechť S je abeceda. Regulární výrazy nad abecedou
S a jazyky, které značí, jsou definovány následovně:
• Æ je RV značící
prázdnou množinu (prázdný jazyk)
• e je RV značící
jazyk {e}
• a, kde a Î S, je RV značící
jazyk {a}
• Nechť r a s jsou regulární výrazy značící po řadě
jazyky Lr a Ls, potom:
• (r.s) je RV značící jazyk L = Lr Ls
• (r + s) je RV značící jazyk L = Lr È Ls
• (r*) je RV značící jazyk L = Lr*