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

MOORE MACHINE AND MEALY MACHINE

-
 About Moore Machine:-
->In the theory of computation, a Moore machine is a finite-state machine whose output values are determined only by its current state. This is in contrast to a Mealy machine, whose output values are determined both by its current state and by the values of its inputs. The Moore machine is named after Edward F. Moore, who
presented the concept in a 1956 paper, “Gedanken-experiments on Sequential Machines.
->It can be defined as (Q, q0, ∑, O, δ, λ) where:
Q is finite set of states.
q0 is the initial state.
∑ is the input alphabet.
O is the output alphabet.
δ is transition function which maps Q×∑ → Q.
λ is the output function which maps Q → O.
->Example:- The state diagram for Moore Machine is
Moore Machine
--->Transition table for Moore Machine is:
Moore Machine
In the above Moore machine, the output is represented with each input state separated by /. The output length for a Moore machine is greater than input by 1.
About Mealy Machine:-
->In the theory of computation, a Mealy machine is a finite-state machine whose output values are determined both by its current state and the current inputs. This is in contrast to a Moore machine, whose (Moore) output values are determined solely by its current state. A Mealy machine is a deterministic finite-state transducer: for each state and input, at most one transition is possible.
->The Mealy machine can be described by 6 tuples (Q, q0, ∑, O, δ, λ') where
Q: finite set of states  
q0: initial state of machine  
∑: finite set of input alphabet  
O: output alphabet  
δ: transition function where Q × ∑ → Q  
λ': output function where Q × ∑ →O  
->Example:-
Design a Mealy machine for a binary input sequence such that if it has a substring 101, the machine output A, if the input has substring 110, it outputs B otherwise it outputs C.
--> For designing such a machine, we will check two conditions, and those are 101 and 110. If we get 101, the output will be A. If we recognize 110, the output will be B. For other strings the output will be C. The partial diagram will be:
Mealy Machine

Now we will insert the possibilities of 0's and 1's for each state. Thus the Mealy machine becomes:

Mealy Machine

Comments

Post a Comment

Popular posts from this blog

EQUIVALENCE OF TWO FINITE AUTOMATAs

-
Image
An Automaton is a machine that has a finite number of states. Any Two Automaton is said to be equivalent if both accept exactly the same set of input strings.  Two Automaton are equivalent if they satisfy the following conditions :  1. The initial and final states of both the automatons must be same. 2. Every pair of states chosen is from a different automaton only. 3. While combining the states with the input alphabets, the pair results must be either both final states or intermediate states.(i.e both should lie either in the final state or in the non-final state). 4. If the resultant pair has different types of states, then it will be non-equivalent. (i.e. One lies in the final state and the other lies in the intermediate state). Method The method for comparing two FA’s is explained below − Let M and M1 be the two FA’s and Σ be a set of input strings. Step 1  − Construct a transition table that has pairwise entries (q, q 1 ) where q ∈ M and q 1  ∈ M 1  for eac...
Read more

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 + ...
Read more

PIGEONHOLE PRINCIPLE AND APPLICATIONS OF PUMPING LEMMA

-
Image
  Pigeonhole principle for regular language:- a hole or small recess for pigeons to nest a small open compartment (as in a desk or cabinet) for keeping letters or documents a neat category which usu. fails to reflect actual complexities. pigeonhole principle:   if  n  objects are put into  m  containers, where  n  >  m , then at least one container must hold more than one object. The pigeonhole can be used to prove that certain infinite languages are not regular. (Remember, any finite language  is  regular.) As we have informally observed, dfas "can't count." This can be shown formally by using the pigeonhole principle. As an example , we show that L = {a b :  n  > 0} is not regular. The proof is by contradiction. Suppose L is regular. There are an infinite number of values of  n  but M(L) has only a finite number of states. By the pigeonhole principle, there must be distinct values of  i  and...
Read more