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 + QP + RPP When we put the value of  R  recursively again and again, we get the following equatio
Post a Comment

SIMPLIFICATION OF CONTEXT-FREE GRAMMAR

-

 Simplification of Context Free Grammar

Context Free Grammar has recursive structure. The languages that are accepted with Context Free Grammar are called Context Free Languages. Context Free Grammar has one condition for production rules, i.e., on the left-hand side of each rule, there must be only single variable, and on the right-hand side, there may be combination of variables and terminals including ?.

In Context Free Grammar, sometimes all the productions rules and symbols are not needed for the derivation to solve. Some productions rules are never used during derivation of any string. Elimination of these types of productions or symbols is called Simplification of Context Free Grammar.

We will use the various simple methods to simplify the given context free grammar without changing the resulting language. The following types of productions rules are never used during derivation of any string from context free grammar:

  • Useless productions
  • Null productions
  • Unit productions 

How to eliminate useless productions?

To eliminate useless productions, we apply following two steps:
Step 1: In step1, we will construct a new grammar equivalent to given grammar. Every variable in new grammar derives some terminal string.
Step 2: In step2, we construct a new grammar equivalent to the grammar obtain in step1. Every symbol in new grammar appears in some sentential form.
Example:
S -> ABC|a
A -> b
B -> c
C -> d
E -> e
F -> f
G -> g
--In this grammar G, we have useless productions i.e.
E -> e
F -> f
G -> g
--After eliminating we have reduced grammar whose productions rules are:
S -> ABC|a
A -> b
B -> c
C -> d

Elimination of Null Productions/Removal of Null Production:

In Context Free Grammar, the productions of the form B -> ? are called null productions. It is not always possible to eliminate all null productions in context free grammar because sometimes eliminating all null productions may change the resulting language.
Example:
Consider the context free grammar, whose productions are
S -> aS
S -> aA
S -> ?
A -> ?
In these productions, we have two null productions
S -> ? and A -> ?. We can eliminate one production A -> ?, the resulting grammar G1 will be:
S -> aS
S -> aA
S -> ?
This does not change the language defined by given context free grammar. But if we delete S -> ?, then we will be unable to get the language
L (G1) = L (G) = {an | n>=0}
Thus, it is possible to eliminate production A -> ?, but if we eliminate S -> ?, we are unable to generate ? in L (G). We can eliminate all null productions in context free grammar, if ? is not derived by L (G). If ? is in L (G), then G must have some ? productions.
Elimination of Unit Productions/ Removal of unit Production:

If any given Context free Grammar production in the form of

A -> B

Where A and B are variables, then this type of production is called unit production (or chin rule).

Example:

If we have following set of production rules:
S -> B
B -> C
C -> D
D -> E
E -> F
F -> G
G -> 01
The language defined by grammar is L (G) = 01.
Solution:
Let us see the derivation of string 01 from given grammar.
S => B  => C
  => D
  => E
  => F
  => G
  => 01
All productions like
B -> C
C -> D
D -> E
E -> F
F -> G
G -> 01
Are useful for replacing B with G.
As G -> 01
L (G) = 01
We can write above productions as:
 S -> 01
L (G) = 01
Thus we have L (G1) =  L (G) = 0

Comments

Post a Comment

Popular posts from this blog

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  j  such that a i  and a j  end in the same state. From this state, b i  
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 + QP + RPP When we put the value of  R  recursively again and again, we get the following equatio
Read more

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 each input symbol. Step 2  
Read more