Regulární výrazy
Regulární výraz je textový řetězec, který umožňuje popsat nějakou množinu slov. Regulární výrazy také můžeme chápat jako jednoduchý způsob, jak popsat konečný automat umožňující generovat všechna možná slova patřící do daného jazyka. Pomocí regulárních výrazů můžeme definovat regulární jazyky. Regulární jazyk je takový jazyk, který je přijímán nějakým konečným automatem.
V regulárních výrazech využíváme znaky abecedy a symboly pro sjednocení, zřetězení a iterace regulárních výrazů. Za regulární výraz se považuje i samotný znak abecedy (např. a) stejně jako prázdné slovo ε a prázdný jazyk ∅.
Definice bezkontextové gramatiky 
Regulární výrazy popisující jazyky nad abecedou Σ:
∅, ε, a (kde a ∈ Σ) jsou regulární výrazy:
∅ . . . označuje prázdný jazyk
ε . . . označuje jazyk {ε}
a . . . označuje jazyk {a}
Jestliže α, β jsou regulární výrazy, pak i (α + β), (α · β), (α∗) jsou regulární výrazy:
(α + β) . . . označuje sjednocení jazyků označených α a β
(α · β) . . . označuje zřetězení jazyků označených α a β
(α∗) . . . označuje iteraci jazyka označeného α
(a + b) = { a, b } ... sjednocení => vrací a nebo b
(a • b) = ab = { ab } ... zřetězení (píše se taky bez puntíků) slepí jednotlivé výrazy k sobě
a* = { ε, a, aa, aaa, aaaa, aaaaa, ... } ... iterace - opakuje výraz nula až nekonečno krát
Příklady: ve všech případech Σ = {0, 1}
(0 + 1) • 0* = { 0, 1, 00, 10, 000, 100, 0000, 1000, ...}
(0 + 1)∗00 = {000, 100, 0000, 0100, 1000, 1100, ...} jazyk tvořený všemi slovy končícími 00
(0 + 1)∗1(0 + 1)∗ = {1,01,10,11, 001, ...} jazyk tvořený všemi slovy obsahujícími alespoň jeden symbol 1