Search for notes by fellow students, in your own course and all over the country.
Browse our notes for titles which look like what you need, you can preview any of the notes via a sample of the contents. After you're happy these are the notes you're after simply pop them into your shopping cart.
Title: Automata (theory of computation)
Description: ardens theorem one of the important for automata.
Description: ardens theorem one of the important for automata.
Document Preview
Extracts from the notes are below, to see the PDF you'll receive please use the links above
ARDEN'S THEOREM
http://www
...
com/automata_theory/ardens_theorem
...
com
Arden's Theorem
In order to find out a regular expression of a Finite Automaton, we use Arden’s Theorem along with
the properties of regular expressions
...
If P does not contain null string, then R = Q + RP has a unique solution that is R =
QP*
Proof −
R = Q + Q + RPP [After putting the value R = Q + RP]
= Q + QP + RPP
When we put the value of R recursively again and again, we get the following equation −
R = Q + QP + QP2 + QP3 …
...
)
R = QP* [As P* represents (ε + P + P2 + P3 + …
...
Assumptions for Applying Arden’s Theorem −
The transition diagram must not have NULL transitions
It must have only one initial state
Method
Step 1 − Create equations as the following form for all the states of the DFA having n states with
initial state q1
...
The equations for the three states q1 , q2 , and q
3
q1 = q1 a + q3 a + ε
are as follows −
(ε move is because q1 is the initial state0
q2 = q1 b + q2 b + q3 b
q3 = q2 a
Now, we will solve these three equations −
q2 = q1 b + q2 b + q3 b
= q1 b + q2 b + (q2 a)b
(Substituting value of q3 )
= q1 b + q2 b + ab
= q1 b b + ab*
ApplyingArden ′ sTheorem
q1 = q1 a + q3 a + ε
= q1 a + q2 aa + ε
= q1 a + q1 b(b + ab*)aa + ε
(Substituting value of q3 )
(Substituting value of q2 )
= q1 a + b(b + ab*aa) + ε
= ε a + b(b + ab*aa)*
= a + b(b + ab*aa)*
Hence, the regular expression is a + b(b + ab*aa)*
...
Loading [MathJax]/jax/output/HTML-CSS/jax
Title: Automata (theory of computation)
Description: ardens theorem one of the important for automata.
Description: ardens theorem one of the important for automata.