Regular_Operations_flashcards
What are the three core regular operations?
Union, Concatenation, and Kleene Star.
What is the definition of union in formal language theory?
L ∪ M = { w | w ∈ L or w ∈ M }
What is the definition of concatenation in regular languages?
LM = { uv | u ∈ L, v ∈ M }
What is the definition of the Kleene star?
L* = { w₁w₂…wₙ | n ≥ 0, wᵢ ∈ L }
If L and M are regular, what can we say about L ∪ M, LM, and L*?
They are also regular — regular languages are closed under union, concatenation, and star.
How do we prove closure under union for regular languages?
Construct an NFA with a new start state that has ε-transitions to the start states of both NFAs for L and M.
How do we construct an NFA for LM (concatenation)?
Add ε-transitions from accepting states of NFA for L to the start state of NFA for M, and make the old accepting states non-accepting.
How do we construct an NFA for L* (Kleene star)?
Add a new accepting start state with ε-transitions to the original start and from accepting states back to it.
What does the product construction do for DFA union?
Creates a DFA with states Q₁ × Q₂, simulating both automata in parallel.
What is the accepting condition for union in DFA product construction?
Accept if q₁ ∈ F₁ or q₂ ∈ F₂.
What is the accepting condition for intersection in DFA product construction?
Accept if q₁ ∈ F₁ and q₂ ∈ F₂.
How do we construct the complement of a DFA language?
Flip accepting and non-accepting states: F’ = Q \ F.
Are regular languages closed under complement?
Yes — because the complement of a DFA is also a DFA.
Are regular languages closed under intersection?
Yes — either via product construction or using De Morgan’s Laws.
How can you compute intersection using De Morgan’s Laws?
L ∩ M = ¬(¬L ∪ ¬M)
What is the state count in DFA product construction?
The number of states is |Q₁| × |Q₂|.
Why do we use ε-transitions in NFA constructions for union, concatenation, and star?
To allow non-consuming transitions between components without reading input.
