1
Unit-2 Contents
UNIT-2 Fundamentals of Regular Languages
Introduction to Regular Expressions (RE)
Finite Automata and Regular Expressions
Regular Expressions Applications
Laws of Algebraic for Regular Expressions
The Arden‘s Theorem
Using Arden‘s theorem to construct RE from FA
Pumping Lemma for RLs
Pumping Lemma Applications
Uniformity of Two FAs
Uniformity of Two REs
Construction of Regular Grammar from RE
Constructing FA from Regular Grammar
Closure properties of RLs, Applications of REs and FAs
2
Converting DFA to Regular Expressions
The Arden‘s Theorem**
Arden’s theorem state that:
“If P and Q are two regular expressions over ∑, and if P does not contain
ε , then the following equation in R given by
R = Q + RP has an unique solution i.e., R = QP*.”
That means, whenever we get any equation in the form of R = Q + RP,
then we can directly replaced by R = QP*.
So, here first we will prove that R = QP* is the solution of this equation
and then we will also prove that it is the unique solution of this equation.
Arden’s Theorem Conditions and Steps
Conditions:-
To use Arden’s Theorem, following conditions must be satisfied-
The transition diagram must not have any ∈ transitions.
There must be only a single initial state.
Steps:-To convert a given DFA to its regular expression using Arden’s Theorem, following steps
are followed-
Step-01:
Form a equation for each state considering the transitions which comes towards that state.
Add ‘∈’ in the equation of initial state.
Step-02:
Bring final state in the form R = Q + RP to get the required regular expression.
Points to Remember:-
Note-01:-
Arden’s Theorem can be used to find a regular expression for both DFA and
NFA.
Note-02:-
• If there exists multiple final states, then-
• Write a regular expression for each final state separately.
• Add all the regular expressions to get the final regular expression.
Problems Using Arden’s Theorem
Problem-01: Find regular expression for the following DFA using Arden’s
Theorem-
Arden’s theorem states that R = Q + RP = QP*
Step-01:Form a equation for each state-
A = ∈ + B.1 ……(1)
B = A.0 ……(2)
Step-02:
Substitute (1) in (2) to
B= (∈ + B.1 ).0
B=(0+B10) ( where ∈R=R ∈=R)
Conti….
B=0+B10 ( Now this equation is in the form of R=Q+RP which can be
expressed as R=QP* )
From the above comparison R=B, Q=0, P=10
If R=Q+RP and equivalent expression is R=QP*
Then the above expression can be written as
B=0(10)*….. (3)
Substitute equation (3) in (1) Now Expression (1) becomes
A= ∈ +0(10)*.1
As final state is B write the Regular Expression for state B
B=0(10)*
Problem-02: Find regular expression for the following DFA using Arden’s
Theorem
Arden’s theorem states that R = Q + RP = QP*
Step-01:Form a equation for each state-
q1 = ∈ ……(1)
q2 = q1.a ……(2)
q3=q1b+q2a+q3a ……(3)
Substitute (2) in (3) Now (3) becomes
q3= q1b+q1aa+q3a
q3=q1(b+aa)+q3a …..(4)
Substitute (1) in (4)
q3=q1(b+aa)+q3a …..(4) (∈R=R ∈=R)
Now (4) becomes
q3=(b+aa)+q3a ( Compare this with R=Q+RP which is equivalent with
R=QP*)
R=q3, Q=(b+aa) and P=a
Now the expression q3 becomes
q3=(b+aa)a*
Hence the q3 is final state the RE for the above FA becomes the expression
for q3
Practice Problems to Construct the RE using Arden’s
Theorem
Problem-03:
Find regular expression for the following DFA using Arden’s Theorem-
Problem-04:-
Find regular expression for the following DFA using Arden’s Theorem
Problem5:-Find regular expression for the following DFA using Arden’s
Theorem
References
Arden’s Theorem and Problems on Arden’s Theorem to construct the
Regular Expression
https://www.geeksforgeeks.org/ardens-theorem-in-theory-of-computation/
https://www.gatevidyalay.com/dfa-to-regular-expression-ardens-theorem/
https://www.javatpoint.com/ardens-theorem
Stay Home and Stay Safe and Stay Happy
Health Tip
