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

THEORY OF COMPUTATION

-
 
THEORY  OF  COMPUTATION(T.O.C.):-
Theory of computation is a branch of computer science which deals with how a problem can be solved in an efficient way using what algorithms or model of computations. Here we solve the problems with different computational models, from which we get different states. This is a branch which give us an info about how computations are occurs in computer system or deals with theoretical model behind every computations.

-For understanding completely about theory of computation, we have to deal with three main pillars of it i.e. L A G
Language:-
-It is a collection of all possible length of string of finite or infinite length.
For example:-  aab, aabb, aaaabbbb, ahhbbb etc. 
-The small unit of a language is known as 'symbol' or a language is a collection of more than one symbols.
For example:-  {a, b, c, ........ 1, 2, 3, ..... etc.}
-Finite set of symbols is known as 'alphabet' which is denoted by Sigma (Σ).
For example:-  {a, b} {a, b, c} etc.
-Collection or sequence of alphabets are known as 'string'.
For example:-  Σ(a, b) now made a string of length 2= {aa, ab, ba, bb}
-Language may be finite or infinite.
For example:- 
Σ(a, b)- construct a language of length 2 containing at most 2 'a'={aa, ab}->[finite]
Σ(a, b)- construct a language containing at least 1 'a'={a, aa, aaa, aab, aaaab, abbaaa, ....etc.}->[infinite] 
Automata:-
-This concept is use to represent a language in standard way.
-Concept of automata is a mathematical model or machine which help to find whether the input string is a part of a given language or not.
Power of sigma(Σ) in T.O.C. :-
It is denoted by Σ^n, means set of all strings with length 'n'.
For example:- 
-let say we have Σ={a, b}->[special case/important point]
Σ^0 means the set of all strings which have 0 length and that will be epsilon(ε)/lambda(λ) which is known as 'null string'.
-let take an another example Σ={0, 1}
Σ^3={000, 111, 010, 011, .........} i.e. the set of all string having length 3. 

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