Past exam question: 2082 Kartik (Back), Q2(a)(ii)
Open in the Padhaiko appObtain the regular expression for the given automata.
Solution
Automaton Formulation and Dead State Elimination: The given automaton has state set , alphabet , start state , and accept state (double circle):
- State has transitions and no outgoing transitions to any other state. Because is non-accepting and cannot reach the accept state , is a dead/trap state.
- Any path entering can never accept. Thus, state and all transitions entering ( and ) can be removed without altering the accepted language.
The active sub-automaton operates entirely on states :
| State | 1 | 0 |
|---|---|---|
| →*A | {B, C} | ∅ |
| B | ∅ | {C, D} |
| C | {D} | {A} |
| D | {D} | {D} |
- Machine-checked
- ✓ accepts ε
- ✓ accepts 10
- ✓ accepts 100
- ✓ accepts 1010
- ✓ accepts 10010
- ✓ accepts 10100
- ✓ rejects 0
- ✓ rejects 1
- ✓ rejects 00
- ✓ rejects 01
- ✓ rejects 11
- ✓ rejects 101
- ✓ rejects 1000
System of Equations and Solution via Arden's Theorem: We write the language equations for the set of strings leading from start state to each state:
- (since is the start state, it includes )
Now substitute this expression for into the equation for :
Arden's Theorem states that for any language equation of the form where , the unique solution is .
Here, and . Applying Arden's Theorem:
Since is the only accepting state, the regular expression for the language accepted by the automaton is:
Eliminating non-accepting trap state leaves paths between , , and . Formulating the language equations , , and yields . By Arden's Theorem, the regular expression is .