Models for Regular
Languages
Proof is based
on the previous algorithm.
Theorem: For every RE r, there is an FA M
such that L(r) = L(M).
Proof: See page 210 in [Meduna:
Automata and Languages]
Theorem: For every FA M, there is an RE r
such
that L(M) = L(r).
Conclusion: The fundamental models for
regular languages are
1) Regular expressions
2) Finite Automata
29/29