Posts

Showing posts with the label minimization

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

MINIMIZATION OF D.F.A.

-
Image
  -> In  automata theory   (a branch of  theoretical computer science ),  DFA minimization  is the task of transforming a given  deterministic finite automaton   (DFA) into an equivalent DFA that has a minimum number of states. Here, two DFAs are called equivalent if they recognize the same  regular language . Several different algorithms accomplishing this task are known and described in standard textbooks on automata theory. -> Minimal D.F.A. -  For each regular language, there also exists a   minimal automaton   that accepts it, that is, a DFA with a minimum number of states and this DFA is unique (except that states can be given different names).   The minimal DFA ensures minimal computational cost for tasks such as   pattern matching . There are two classes of states that can be removed or merged from the original DFA without affecting the language it accepts. ->Unreachable states   are the stat...
Post a Comment
Read more