Musimy udowodnic, ze re = \Sigma^*.
Regexp mozemy reprezentowac w postaci NFA w liniowej pamieci (Lemma 1.29, example 1.30, example 1.31, Sipser).