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

PUMPING LEMMA AND CLOSURE PROPERTIES OF REGULAR LANGUAGES

-
 
PUMPING LEMMA:-
In the theory of formal languages, the pumping lemma may refer to:
->Pumping lemma for regular languages, the fact that all sufficiently long strings in such a language have a substring that can be repeated arbitrarily many times, usually used to prove that certain languages are not regular.
->Pumping lemma for context-free languages, the fact that all sufficiently long strings in such a language have a pair of substrings that can be repeated arbitrarily many times, usually used to prove that certain languages are not context-free.
->Pumping Lemma is used as a proof for irregularity of a language. Thus, if a language is regular, it always satisfies pumping lemma. If there exists at least one string made from pumping which is not in L, then L is surely not regular.
The opposite of this may not always be true. That is, if Pumping Lemma holds, it does not mean that the language is regular.
->It states that if 'L' is an infinite language then there exists some positive integer 'n' (pumping length) such that any string say W ∈ L has greater than or equal to 'n' is |W|>=n, then W can be divided into three parts let say 'xyz' satisfy following condition:-
i) for each 'i>0', ((xy)^i)(z) ∈ L
ii) |y|>0
iii) |xy|<=n
Example:-
Prove that L = {aibi | i ≥ 0} is not regular.

Solution −

  1. At first, we assume that L is regular and n is the number of states.
  2. Let w = anbn. Thus |w| = 2n ≥ n.
  3. By pumping lemma, let w = xyz, where |xy| ≤ n.
  4. Let x = ap, y = aq, and z = arbn, where p + q + r = n, p ≠ 0, q ≠ 0, r ≠ 0. Thus |y| ≠ 0.
  5. Let k = 2. Then xy2z = apa2qarbn.
  6. Number of as = (p + 2q + r) = (p + q + r) + q = n + q
  7. Hence, xy2z = an+q bn. Since q ≠ 0, xy2z is not of the form anbn.
  8. Thus, xy2z is not in L. Hence L is not regular.
CLOSURE PROPERTIES :-
  1. Kleen Closure:
    RS is a regular expression whose language is L, M. R* is a regular expression whose language is L*.
  2. Positive closure:
    RS is a regular expression whose language is L, M. R^+ is a regular expression whose language is L^+.
  3. Complement:
    The complement of a language L (with respect to an alphabet E such that E^* contains L) is E^*–L. Since E^* is surely regular, the complement of a regular language is always regular.
  4. Reverse Operator:
    Given language L, L^R is the set of strings whose reversal is in L.
    Example: L = {0, 01, 100};
    L^R ={0, 10, 001}.
    Proof: Let E be a regular expression for L. We show how to reverse E, to provide a regular expression E^R for L^R.
  5. Complement:
    The complement of a language L (with respect to an alphabet E such that E^* contains L) is E^*–L. Since E^* is surely regular, the complement of a regular language is always regular.
  6. Union:
    Let L and M be the languages of regular expressions R and S, respectively.Then R+S is a regular expression whose language is(L U M).
  7. Intersection:
    Let L and M be the languages of regular expressions R and S, respectively then it a regular expression whose language is L intersection M.
    proof: Let A and B be DFA’s whose languages are L and M, respectively. Construct C, the product automaton of A and B make the final states of C be the pairs consisting of final states of both A and B.
  8. Set Difference operator:
    If L and M are regular languages, then so is L – M = strings in L but not M.

    Proof: Let A and B be DFA’s whose languages are L and M, respectively. Construct C, the product automaton of A and B make the final states of C be the pairs, where A-state is final but B-state is not.

  9. Homomorphism:
    A homomorphism on an alphabet is a function that gives a string for each symbol in that alphabet. Example: h(0) = ab; h(1) = E. Extend to strings by h(a1…an) =h(a1)…h(an). Example: h(01010) = ababab.

    If L is a regular language, and h is a homomorphism on its alphabet, then h(L)= {h(w) | w is in L} is also a regular language.
    Proof: Let E be a regular expression for L. Apply h to each symbol in E. Language of resulting R, E is h(L).

  10. Inverse Homomorphism : Let h be a homomorphism and L a language whose alphabet is the output language of h. h^-1 (L) = {w | h(w) is in L}.

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