Regular Expressions, Arden's Theorem & State Elimination
“Arden's formula R = Q + RP => R = QP*, state elimination method, and Thompson's construction.”
1.Regular Expressions & Arden's Theorem
§ 1.1.A Regular Expression (RE) over alphabet \Sigma recursively denotes a regular language using base operations: \emptyset, \epsilon, symbols a \in \Sigma, union (R_1 + R_2), concatenation (R_1 R_2), and Kleene star (R^*).
Arden's Theorem:
Let P and Q be two regular expressions over \Sigma. If \epsilon \notin L(P) (i.e., P does not contain the empty string), then the linear equation:
$R = Q + RP$
has a UNIQUE solution given by:
$R = QP^*$
Application to Finite Automata:
For each state q_i in a DFA with transitions entering from q_j on symbol a:
$q_i = \sum_{j} q_j a + (\epsilon if q_i is start state)$
Solve the system of simultaneous linear equations by substitution and Arden's theorem until the accepting state expressions contain only alphabet symbols.
2. GATE Worked Numerical: Converting DFA to RE via Arden's Theorem
Ensure that equation is in R = Q + RP form (with R on the right of P, not PR!). If R = Q + PR, the solution is P*Q.
Problem: Consider a DFA with states {q1, q2}, start state q1, accepting state q2. Transitions:
delta(q1, 0) = q1, delta(q1, 1) = q2
delta(q2, 0) = q2, delta(q2, 1) = q1
Find the regular expression for the language accepted by this DFA.
Step 1: Formulate state equations:
q1 has incoming transitions from q1 on '0', from q2 on '1', and is start state:
q1 = q1(0) + q2(1) + epsilon.
q2 has incoming transitions from q1 on '1', and from q2 on '0':
q2 = q1(1) + q2(0).
Step 2: Apply Arden's Theorem to q2:
q2 = [q1(1)] + q2(0). Here Q = q1(1) and P = 0.
q2 = q1(1)(0)*.
Step 3: Substitute q2 into q1 equation:
q1 = q1(0) + [q1(1)(0)*](1) + epsilon
q1 = q1 [0 + 1(0)*1] + epsilon.
Step 4: Apply Arden's Theorem to q1:
q1 = epsilon [0 + 1(0)1] = [0 + 1(0)1]*.
Step 5: Substitute q1 back to find accepting state q2:
q2 = [0 + 1(0)1] 1(0)*.
The language accepted is: (0 + 1 0 1) 1 0*.
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.
Curated for clarity, rigorous numerical solving, and semester excellence:
GATE-focused with clear minimal DFA construction and language classification.
Exam-pattern oriented with closure table drilling and decidability proofs.
Mathematically rigorous treatment for high-rank GATE aspirants.