Posts

Showing posts with the label states

ARDEN'S THEOREM FOR REGULAR EXPRESSIONS

-
Image
    Identities for Regular Expression:- Given R, P, L, Q as regular expressions, the following identities hold − ∅* = ε ε* = ε RR* = R*R R*R* = R* (R*)* = R* RR* = R*R (PQ)*P =P(QP)* (a+b)* = (a*b*)* = (a*+b*)* = (a+b*)* = a*(ba*)* R + ∅ = ∅ + R = R   (The identity for union) R ε = ε R = R   (The identity for concatenation) ∅ L = L ∅ = ∅   (The annihilator for concatenation) R + R = R   (Idempotent law) L (M + N) = LM + LN   (Left distributive law) (M + N) L = ML + NL   (Right distributive law) ε + RR* = ε + R*R = R* 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. Statement  − Let  P  and  Q  be two 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 + RP)P  [After putting the value R = Q + RP] = Q + ...
Post a Comment
Read more

NON-DETERMINISTIC FINITE AUTOMATA (N.D.F.A.)

-
Image
  About N.D.F.A :- -->A nondeterministic finite automaton (NFA), or nondeterministic finite-state machine, does not need to obey these restrictions. In particular, every DFA is also an NFA. Sometimes the term NFA is used in a narrower sense, referring to an NFA that is  not  a DFA, but not in this article. Using the  subset construction algorithm , each NFA can be translated to an equivalent DFA; i.e., a DFA recognizing the same  formal language . Like DFAs, NFAs only recognize  regular languages . NFAs were introduced in 1959 by  Michael O. Rabin  and  Dana Scott ,  who also showed their equivalence to DFAs. NFAs are used in the implementation of  regular expressions :   Thompson's construction  is an algorithm for compiling a regular expression to an NFA that can efficiently perform pattern matching on strings. Conversely,  Kleene's algorithm  can be used to convert an NFA into...
Post a Comment
Read more