Regulární výrazy (RV): Definice
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*
2/29
Myšlenka: Jsou to výrazy s operátory ., + a *, které značí v tomto pořadí konkatenaci, sjednocení a iteraci