PadhaikoAll subjects

Past exam question: 2082 Kartik (Back), Q2(a)(ii)

Theory of Computation · 3 marks

Open in the Padhaiko app

Topic: Regular Expressions & Equivalence with Finite Automata

Question

Obtain 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):

The active sub-automaton operates entirely on states :

Active NFANFA
Active NFA 0, 1 1 1 0 0 0 1 A B C D
State10
→*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:

  1. (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:

Answer:

Eliminating non-accepting trap state leaves paths between , , and . Formulating the language equations , , and yields . By Arden's Theorem, the regular expression is .

All past exam questions for Theory of Computation