FSA to REGEX Flashcards
What does Lecture 7 aim to prove?
That regular expressions and finite automata are equivalent in expressive power.
What is the key theorem of Lecture 7?
A language is regular if and only if it can be described by a regular expression.
What is the hard direction of the equivalence proof?
Every DFA/NFA can be converted into a regular expression.
What is a GNFA (generalized NFA)?
An automaton where transitions are labeled by regular expressions, not just single symbols or ε.
What is the general method for converting a DFA to a regex?
Turn the DFA into a GNFA, then eliminate states until one edge remains between the start and accepting states.
What must be true of the start state in a GNFA?
It must have no incoming edges.
What must be true of the accepting state in a GNFA?
It must have no outgoing edges.
Why do we add a new start and accept state during preprocessing?
To ensure only one start state and one accepting state with the required structure.
What do we do if a state has multiple arrows between two states?
Merge them into a single transition using the union operator (e.g., a ∪ b).
During state elimination
what expression is added from j → k via i with loop γ?
What happens to existing transitions when adding new paths during state elimination?
They are combined using the union operator with the new expression.
What do we do after removing all intermediate states?
The remaining edge from the start to accepting state is the final regular expression.
What does the final expression from the GNFA represent?
It represents the same language as the original finite automaton.
What does the β expression represent in the example?
β := a(b ∪ aa)*ab ∪ b
What does the γ expression represent in the example?
γ := bb ∪ ((a ∪ ba)(b ∪ aa)*ab)
What does the δ expression represent in the example?
δ := ε ∪ (a ∪ ba)(b ∪ aa)*
What is the final regular expression after eliminating all states?
α := a(b ∪ aa)* ∪ βγ*δ
Why is the DFA-to-regex construction important?
It shows that regular languages can be expressed as patterns — used in compilers, search, and verification.
