Posts

Showing posts with the label strings

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

DETERMINISTIC FINITE AUTOMATA (D.F.A)

-
Image
About D.F.A :- ->In the  theory of computation , a branch of  theoretical computer science , a  deterministic finite automaton  ( DFA )—also known as  deterministic finite acceptor  ( DFA ),  deterministic finite-state machine  ( DFSM ), or  deterministic finite-state automaton  ( DFSA )—is a  finite-state machine  that accepts or rejects a given  string  of symbols, by running through a state sequence uniquely determined by the string.   Deterministic  refers to the uniqueness of the computation run. In search of the simplest models to capture finite-state machines,  Warren McCulloch  and  Walter Pitts  were among the first researchers to introduce a concept similar to finite automata in 1943. ->It is defined as a five tuple consisting with- {Q,  Σ,  δ ,  q 0 ,  F } - a finite set of states 'Q' - a finite set of input symbols called alphabet  Σ - a transi...
Post a Comment
Read more