Posts

Showing posts with the label NDFA

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

N.D.F.A TO D.F.A. CONVERSION

-
Image
  Difference between D.F.A. and N.D.F. Each transition leads to exactly one state called as deterministic A transition leads to a subset of states i.e. some transitions can be non-deterministic. Accepts input if the last state is in Final Accepts input if one of the last states is in Final. Backtracking is allowed in DFA. Backtracking is not always possible. Requires more space. Requires less space. Empty string transitions are not seen in DFA. Permits empty string transition. For a given state, on a given input we reach a deterministic and unique state. For a given state, on a given input we reach more than one state. DFA is a subset of NFA. Need to convert NFA to DFA in the design of a compiler. δ : Q × Σ → Q For example − δ(q0,a)={q1} δ : Q × Σ → 2 Q For example − δ(q0,a)={q1,q2} DFA is more difficult to construct. NFA is easier to construct. DFA is understood as one machine. NFA is understood as multiple small machines computing at the same time. Steps for converting N.D.F.A. t...
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