Documents

7164901 Arden s Theorem Tafl

Categories
Published
of 18
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