All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

Related Documents

Share

Description

Ardens theorem

Transcript

Presentation on :
Presented by:- Gaurav Gupta 20/05 IInd B.Tech I.T.
“ARDEN’S THEOREM”
CONSRTRUCTION OF REGULAR
EXPRESSION FROM DFA
The regular expression is mathematical expression for a given regular language.
We know that for every regular language there exist a DFA.
We can conclude that for regular expression, regular language for that regular expression and DFA for that regular language are similar things in different representation.
So we can construct regular expression for every Deterministic Automata.
ARDEN’S THEOREM
is one means to implement it.
RDEN’S THEOREM
Let P and Q be two regular expression over alphabet
Σ
. If P does not contain NULL STRING (
ε
), then :
R = Q + RP
Has a unique solution that is :
R = QP*
Now lets have a look at its mathematical proof…
MATHEMATICAL PROOF
It can be understood as :
R = Q + R P
Put the value of R in R.H.S.
R = Q + (Q + RP) P = Q +QP + RP
2
When we put the value of R again and again we get the following
equation:
R = Q + QP + QP
2
+ QP
3
…
R = Q ( 1 + P + P
2
+ P
3
…)
R = Q (
ε
+ P + P
2
+ P
3
… )
R = QP*
-(By the definition of closure operation for regular expression.)

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks