Save
TC
regular expressions
equivalence between finite automata and REs
Save
Share
Learn
Content
Leaderboard
Learn
Created by
Francisca Portugal
Visit profile
Cards (12)
FROM REs TO FINITE AUTOMATA
Theorem:
Every language defined by a regular expression R is also defined by
a-NFA
E.
Thompson
method
BASIS
STEP
INDUCTION
STEP
EXAMPLE
EXAMPLE (
cont.
)
FROM FINITE AUTOMATA TO REs
Construction of paths
(has many repetitions, is onerous, and may provide long/complex REs if we dont simplify them)
State elimination
(will study only this one)
NORMALIZING
e-NFAs
EXAMPLE
STATE ELIMINATION
Given a
noramlized
e-NFA:
STATE
ELIMINATION
(cont.)
STATE
ELIMINATION
(cont.)
STATE
ELIMINATION
(cont.)