Automata

Finite automata and Regular Expressions

(Original Format is available in download tab)

PRELIMINARIES:

STRINGS, ALPHABETS AND LANGUAGES:

SYMBOL:

            Letters and digits are symbols.

STRING:

            String is a finite sequence of symbols.

            Example: a, b and c are symbols and abcb is a string.

LENGTH OF A STRING (w):

            It is denoted by |w|, is the number of symbols comparing the string.

            Example: abcb has length 4.

EMPTY STRING:

            Empty string is denoted by ε, is the string consisting of zero symbols. Therefore |ε|=0.

PREFIX:

            Prefix of a string is any number of leading symbols of that string.

            Example: For abc, ε, a, ab and abc are prefixes

SUFFIX:

            Suffix is any number of trailing symbols.

            Example: abc, has suffixes ε, c, bc and abc.

            A prefix or suffix of a string, other than the string itself, is called a proper prefix or suffix.

CONCATENATION:

            If x and y are strings, then xy is the string obtained by placing a copy of y immediately after a copy of x.

            X = a₁a₂…..a_i                                y = b₁b₂……b_j

             Xy = a₁a₂…..a_i b₁b₂……b_j

LANGUAGES:

            If Σ is an alphabet, and L is a subset of Σ* then L is a language.

            Example: 1. Set of legal English words.

                              2. Set of legal C program.

                           3. If Σ = {a,b} then Σ* = {ε, a, b, aa, ab, ba, bb,…}

                                    Then {ab, abab, aabb} is a language over Σ.

                                    Therefore its length is finite, it is a finite language.

                           4. L = {aⁿbⁿ : n≥0} is an infinite language, because it contains

                                an infinite string.

From the definition of languages, it is clear that it is a set. Operations like union, intersection and differences are true for this also.   

MATHEMATICAL INDUCTION:

ALPHABET:

            It is a finite set of symbols.

LANGUAGE:

            It is a set of strings of symbols from some one alphabet.

            Empty set φ and the set consisting of the empty string {ε} are languages.

1.                              The set of palindromes over the alphabet {0,1} is an infinite language.

Members are: ε, 0, 1, 00, 11, 010, 1101011, etc.

2.                              Set of all strings over a fined alphabet Σ which is denoted by Σ*.

If Σ = {a}

   Σ* = {ε, a, aa, aaa,…}

If Σ = {0,1}

   Σ* = {ε, 0, 1, 00, 11, 01, 10, 11, 000,…}

INDUCTIVE PROOFS:

            Consider we have a statement P(n) about a non-negative integer n.

                       

                                 

           

            The principle of mathematical induction is that P(G) follows from

·                                                         P(0) → basis

·                                                         P(n-1) => P(n) for n≥1 → Inductive step.

P(n-1) is called inductive hypothesis.

            Proof:

1)                                                      Substitute 0 for n in equation 1, we will get 0 on both sides.

2)                                                      Substitute n-1 for n in equation 1 and we have to prove equation 1. we must show for n≥1 that

         

SET NOTATION:

SET:

            It is a collection of objects. Finite set may be specified by listing their members between brackets.

            Example:

                 {0,1} denotes alphabet of symbols 0 and 1.

            Representation:

1.                                             {x / P(x)}             set of objects x such that P(x) is true.

2.                                             {x in A / P(x)}     set of x in set A such that P(x) is true.

Example:

    {i / i is an integer and their exists integer j such that i = 2j} is a way of specifying even integers.

A  B, since A is a member of B

A  B, since A is a member of B and A≠B, that is some member of B not in A.

OPERATIONS ON SETS:

1.                  A  B, Union: {x / x is in A or x is in B}

2.                  A ∩ B, Intersection: {x / x is in A and x is in B}

3.                  A – B, Difference: {x / x is in A and x is not in B}

4.                  A * B, Cartesian Product: Set of ordered pairs (a,b) such that a is in A and b is in B.

5.                  2^A, Powerset of A, is the set of all subsets of A.

Example:

            A = {1,2}               B = {2,3}

            A U B = {1,2,3}     A ∩ B = {2}    A – B = {1}

            A * B = {(1,2),(1,3),(2,2),(2,3)}

            2^A = {φ, {1},{2},{1,2}}

FINITE AUTOMATA AND REGULAR EXPRESSIONS:

FINITE STATE SYSTEMS:

AUTOMATON:

            Automata is the plural of the word ‘Automaton’ which simply means any machine.

DEFINITION:

            It is a black-bon into which some input is fed, and as a result some output comes out. The relationship between the input and the output depends on the particular machine in hand.

            The machine seems to comprise:

·                                                         Set of inputs

·                                                         Set of outputs

·                                                         Rules to produce output for the given input.

FINITE AUTOMATON:

            It is a mathematical model of a system with discrete inputs, discrete outputs and a finite number of memory configurations called states.

            It is used as a model for

·                                                         Software for designing digital circuits

·                                                         Lexical analyzer of a compiler

·                                                         Searching for keywords in a file or on the web

FINITE STATE SYSTEMS:

            The finite automation is a mathematical model of a system, with discrete inputs and outputs.

Commonly used programs such as text editors and the lexical analysers found in most compilers are often designed as finite state system.

DEFINITION:

            A finite automation (FA) consists of a finite set of states and a set of transitions from state to state that occur on input symbols chosen from an alphabet Σ.

            Initial state is denoted by q0. Transition diagram (directed graph) is associated with FA.

            Vertices represent states of FA.

 

Example:

                                 
 

                                    Fig: Transition diagram of a finite automation

·                                   Final state is indicated by double circle

·                                   Each 0 input causes control to cross the horizontal line a – b iff the input seen so far contains an even number of 0’s similarly 1-input causes control to cross the vertical line

     c – d.

·                                   Control is at q0, iff there are both an even number of 0’s and even number of 1’s in the output.

           

Example: 1. switching circuit on/off switch

                      Push

                                        Push

Example: 2. Computer itself

                                        State: is a CPU at any time is one of a very large but finite number of states.

DEFINITION:

            For each input symbol, if there is exactly one transition from each state, then the finite automata is said to be DFA. Otherwise it is called NFA.

REPRESENTATION:

                                        →

FINITE CONTROL:

              It is a black-bon of FA, contains all the transition states either deterministic or non-deterministic.

              DFA has an input tape of cells, a reading head and finite control.

                            Input tape

0

1

1

0

0

0

1

1

0

0

1

1

1

0

0

       Read Head

                                                        cells

                       

            In one move, the FSA in state q and scanning the symbol ‘a’ enters δ(q,a) and moves its head one symbol to the right. If δ(q,a) is an accepting state, then FSA is said to have accepted the string on its input tape.

REPRESENTATION:

            FA is denoted by a 5-tuple (Q, Σ, δ, q₀, F)

   Q = Finite set of states

   Σ = Finite input alphabet

   q₀ in Q = Initial state

   F is a subset of Q = Set of final states

   δ = Transition function mapping Q* Σ → Q

            That is δ(q,a) is a state for each state q and input symbol.

   Example:

       Consider the above transition diagram. Here FA is denoted by M = (Q, Σ, δ, q₀, F) where

Q = {q₀,q₁,q₂,q_­3}

 Σ = {0,1}

 F = {q₀}

δ is shown below.

            

               

                                   

    

    

                                              Fig 2: δ(q,a) for the FA.

DETERMINISTIC FINITE AUTOMATA (DFA):

               For a given input string w and state q, there will be exactly one path labeled w starting at q.

NON-DETERMINISTIC FINITE AUTOMATA (NFA):

                   If the finite automata model allows zero, one or more transitions from a state on the same input symbol, then that model is called NFA.

                   A transition diagram for a NFA is shown in the following figure.

TRANSITION DIAGRAM:

                   A transition diagram associated with DFA is a directed graph whose vertices are the states of DFA.

* The edges of the graph are the transitions from one state to another state.

* Initial q₀ by start.

* Final state by double circle.

Example:

                   M = (Q = {q₀,q₁,q₂}, Σ = {a,b}, q₀, δ, F = {q₂}); where δ is defined as

                   δ(q₀,a) = q₁

                   δ(q₁,a) = q₂

                   δ(q₂,b) = q₁

REGULAR LANGUAGES:

·                                  A string n is accepted by FSA, M if δ(q₀,x) = p for some P F.

·                                  The language accepted by M denoted by L(M) is the set

     {x : δ(q₀,x)  F}.

·                                  L(M) is said to be regular if it is accepted by FSA.

TRANSITION TABLE:

                   The table which represents the list of transition rules (functions) of a FA is called transition table.

          Example: Find the language accepted by the DFA given in figure

                                                           

                                                            

                     δ(q0,11)= δ(δ(q0,1),1) = δ(q1,1) = q0.

                           Hence 11 € L(M). Similarly we find,

                           δ(q0,1010) = q0

                           δ(q0,110101) = q0

         Fig 3: The transition diagram for NFA

·                                                   In this example, there are two edges labeled 0 out of state q₀ , one going back to state q₀ and one going to state q₃.

·                                                   An input sequence a₁, a₂ ,…an is accepted by a NFA if there exists a sequence of transitions, comparing to the input sequence, that leads from the initial state to some final state.

·                                                   For example, 01001 is accepted by above NFA, because there is a sequence of transitions through the states q₀,q₀,q₃,q₄,q₄ labelled 0,1,0,0,1.

·                                                   Formally NFA is denoted by 5-tuple (Q, Σ, δ, q₀, F) as in DFA, but δ is a map from Q* Σ to 2^Q.

·                                                   The function δ for the NFA of above figure is given below:

 

                              

                                    

                                                                        

                              

                 Fig 4 : The mapping δ for the NFA of Fig 3

             Thus, 1010  L(M). So L(M) is the set of all strings with an even number of 0’s and 1’s.

Example 2:

            Describe the language accepted by DFA M whose transition diagram is given below:

 

                            

           

            Solution:

                    δ(q₀,0) = q₃, non accepting state

                        δ(q₀,10) = δ(q₁,0) = q₃, non accepting state

                        δ(q₀,11) = q₂, accepting state

                        δ(q₀,110*) = q₂, accepting state

                        δ(q₀,110*1*) = q₂, accepting state

Hence the strings of 0 and 1 that begins with two 1’s are accepted by M.

Example 3:

            Design a DFA that accepts the strings having

i)                                Even no. of a’s

ii)                              Exactly one b over the input set {a,b}

          Solution:

              

     i)                 

                      

                 

                        Let Q = {q₀, q₁}

                               Σ = {a,b}

                               F = {q₀}

ii)

                   

           

                        Let Q = {q₀, q₁}

                               Σ = {a, b}

                               F = {q₁}

·                                                         Let the input be 01001

            δ(q₀,0) = {q₀,q₃}

          δ(q₀,01) = δ(δ(q₀,0),1)

                            = δ({q₀,q₃},1)

                            = δ(q₀,1) U δ(q₃,1)

                            = {q₀, q₁}

·                                                         Similarly we compute

             δ(q₀,010) = {q₀,q₃}

              δ(q₀,0100) = {q₀,q₃,q₄}

              δ(q₀,01001) = {q₀,q₁,q₄}

EQUIVALENCE OF DFA’S AND NFA’S:

            For every NFA, we can construct an equivalent DFA. The constructed DFA keeps track in its finite control of all states that the NFA could be in after reading the same input as the DFA has read.

THEOREM:

            Let L be a set accepted by a NFA. Then there exits a DFA that accepts L.

PROOF:

            Let M = (Q, Σ, δ, q0, F) be an NFA accepting L. Define a DFA,

M’ = (Q’, Σ, δ’, q₀’, F’), as follows states of M’ are all the subsets of the set of states of M.

            That is, Q’ = 2^Q

            M’ will keep track in its state of all the states could be in at any given time. F’ is the set of all states in Q’ containing a final state of M.

            An element of Q’ will be denoted by [q₁, q₂,..q_i], where q₁,q₂,…q_i are in Q. [q₁,q₂,…q_i] is a single state of the DFA corresponding to a set of states of the NFA. Note that q₀’ = [q₀].

NFA:

            δ(q₀,a) = {P₁, P₂,…..Pn} is that the non-deterministic machine, when in state q and scanning the symbol a, moves right and chooses any one of

P₁, P₂,…..Pn as its next state.

DEFINITION:

·                                                         A NFA m is a 5-tuple (Q, Σ, δ, q₀, F)

Q = finite set of states

 Σ = finite set of input symbols

 q₀  Q = initial state

                              δ = mapping of Q* Σ into 2^Q

                                      F is a subset of Q = set of final states.

·                                                         A language is accepted by M if there exists some state in both F and δ(q₀,w).

·                                                         That is T(M) = {w / δ(q₀,w) ∩ F ≠ φ}

BASIS STEPS:

            We define

                δ ’([q₁,q₂,…qi],a) = [P₁,P₂,….P_j]

            iff

                δ({q₁,q₂,…q_i},a) = {P₁,P₂,….P_j}

            That is, δ’ applied to an element [q₁,q₂,…qi] of Q’ is computed by applying δ to each state of Q represented by [q₁,q₂,…qi]. On applying δ to each of q₁,q₂,…qi had taking the union, we get some new set of states, P₁,P₂,….P_j. This new set of states has a representative [P₁,P₂,….P_j] in Q’, and that element is the value of δ’([q₁,q₂,…qi],a).

            It is easy to show by induction on the length of the input string x such that

            δ’(q₀’,x) = [q₁,q₂,…qi]

     iff δ(q₀,x) = {q₁,q₂,…qi}

INDUCTION:

            Suppose that the hypothesis is true for inputs of length m or less. Let xa be a string of length m+1 with a in Σ.

            Then δ’(q₀’,xa) = δ’(δ’(q₀’,x),a)

            By the inductive hypothesis,

                        δ’(q₀’,x) = [P₁,P₂,….P_j]

                iff δ(q₀,x) = {P₁,P₂,….P_j}

            But by definition of δ’,

                        δ’([P₁,P₂,….P_j],a) = [r₁,r₂,…r_k]

                iff δ({P₁,P₂,….P_j},a) = {r₁,r₂,...r_k}

            Thus,

                        δ’(q₀’,xa) = [r₁,r₂,…r_k]

                  iff δ(q₀,xa) = {r₁,r₂,…r_k},

            which establishes the inductive hypothesis.

EXAMPLE:

            Let  M = ({q₀,q₁}, {0,1}, δ, q₀, {q₁}) be an NFA where δ(q₀,0) = {q₀,q₁}, δ(q₀,1) = {q₁}, δ(q₁,0) = φ, δ(q₁,1) = {q₀,q₁}.

DFA:

            M’ = (Q’,{0,1}, δ’, [q₀], F’)

      Where, Q = {q₀, q₁} and denoting elements by [q₀],[q₁],[q₀,q₁] and φ.

Therefore, δ(q₀,0) = {q₀,q₁}, we have

            δ’([q₀],0) = [q₀,q₁]

Likewise,

            δ’([q₀],1) = [q₁],

            δ’([q₁],0) = φ

            δ’([q₁],1) = [q₀,q₁]

Naturally, δ’(φ,0) = δ’(φ,1) = φ.

Lastly, δ’([q₀,q₁],0) = [q₀,q₁]

Since, δ({q₀,q₁},0) = δ(q₀,0) δ(q₁,0)

                                     = {q₀, q₁}  φ     = {q₀, q₁}.

And δ’([q₀,q₁],1) = [q₀,q₁]

Therefore, δ({q₀,q₁},1) = δ(q₀,1)  δ(q₁,1)

                                     = {q₁}  {q₀, q₁}.

                                     = {q₀, q₁}.

The set F’ of final states is { [q₁], [q₀,q₁]}.

FINITE AUTOMATA WITH ε-MOVES:

            NFA model can be extended to include transitions on the empty input ε. The transition disagram of such an NFA which consists of any number of 0’s, followed by any number of 1’s followed by any number of 2’s is given in the following figure.

Fig 5: Finite automaton with ε-moves.

            Here, edges labeled ε may be included in the path, although the ε’s do not appear explicitly in the string w.

            Example:

       The word 002 is accepted by the NFA of figure by the path   q₀, q₀, q₀, q₁, q₂, q₂ with arcs labeled 0, 0, ε, ε, 2.

                        Formally, NFA with ε-moves is defined to be a quintuple

          (Q, Σ, δ, q₀, F) with all components maps Q*(Σ U {ε}) to 2^Q.

           

            TRANSITION FUNCTION OF FIGURE:

 

                      States       0         1          2           ε

                        q 0       {q0}      φ          φ        {q1}

                        q 1          φ       {q1}      φ        {q2}

                        q 2          φ       φ          {q2}        φ

                 Fig: δ(q,a) for the NFA of fig 5.

                  

        Now, we extend the transition function δ to a function ŝ that maps Q×Σ* to 2^Q.

                  Our expectation is that ŝ(q,w) will be all states P such that one can go from q to P along a path labeled w, including edge labeled ε.

                   In constructing  it will be important to compute the set of states reachable from a given state q using ε transitions only. We use ε-closure(q) to denote the set of all vertices P such that there is a path from q to P labeled ε.

                        For example, in figure 5,

                                    Ε-closure(q₀) = {q₀,q₁,q₂}

                            That is, q₀ to q₀ with all arcs labeled ε.

                                           q₀ to q₁ with all arcs labeled ε.

                                           q₀, q₁, q₂ with all arcs labeled ε.

            Let ε-closure(P), whose P is a set of states, be U_q in P ε-closure(q). Now, we define  as follows:

1. (q, ε) = ε-closure(q).

2. For w in Σ* and a in Σ,  (q, wa) = ε-closure(P), where P = {P / for some r in (q, w), P is in δ(r,a)}.

3. (R,a) = U_q in R (q, a)

4. (R, w) = U_q in R (q, w) for set of states R.

REGULAR EXPRESSIONS:

            The languages accepted by finite automata are easily described by simple expressions called regular expressions.

            Operations on sets of strings:

·         Let Σ be a finite set of symbols.

·         Let L, L₁ and L₂ be set of strings from Σ*.

·         Concatenation of L₁ and L₂ : L₁L₂ is the set  

     {xy / x is in L₁ and y is in L₂}

Example:

L₁ = {10,1} and L2 = {011,11}

L₁L₂ = {10011,1011,111} [in all possible combinations]

·         Define L⁰ = {ε} and Lⁱ = LL^i-1 for i≥1 kleene closure of L that is L*, is the set

                   

L* =  Lⁱ = L⁰  L¹  L² ……

           

Example:

L* {10,11}* = {ε,10,11,1010,1011,1110,1111..}

·               Positive closure of L, L⁺ is the set

       L⁺ =  Lⁱ = L* - L⁰ = L* - {ε}

{10,11}⁺ = {10,11,1010,1011,1110,1111…}

DEFINITION:

            Let Σ be an alphabet. The regular expressions over Σ and the sets that they denote are defined recursively as follows:

i)              φ is a regular expression and denotes the empty set.

ii)            Ε is a regular expression and denotes the set {ε}.

iii)          For each a € Σ, ‘a’ is a regular expression and denotes the set {a}.

iv)          If ‘r’ and ‘s’ are regular expressions denoting the languages R and S, then

(r+s) denotes the set R  S

(rs) denotes the set RS

(r*) denotes the set R^*

PRECEDENCE:

                                    High

                                                      *

                                                   concatenation

                                                      +

                                    Low    

               Example: 01*+0 ó ((0(1^*)) + 0)

EXAMPLE:

1.      (0 + 1)*: all strings of 0’s and 1’s. ie.  010101….

2.      (0 + 1)* 00 (0 + 1)*: all strings of 0’s and 1’s with atleast two consecutive 0’s.

3.      (1 + 10)*: al strings of 0’s and 1’s beginning with 1 and not having two consecutive 0’s. ie.110..

4.      0* 1* 2*: any number of 0’s, followed by any number of 1’s followed by any number of 2’s.

5.      00* 11* 22* 0⁺ 1⁺ 2⁺: like 0* 1* 2* with atleast one of each symbol.

EXAMPLE:

            Construct a NFA for the regular expression 01* + 1.

Solution:

·         It is of the form r₁ + r₂

r₁ = 01*

r₂ = 1

·         Automation for r₂ is

                    

·         We express r₁ = 01*

                  = r₃ r₄*

              Where, r₃ = 0

                           r₄ = 1*

·         Automaton for r₃ is

                                                                                             

·         Now r₄ = r₅* where r₅=1

·         Automation for r₅ is

                  

·         r₅* is

                                                       ε                                                                       

                                                     ε 

·         r₁ = r₃ r₄*

          = r₃ r₅*                                                                                      ε 

             

                                                                                                          ε 

·         r = r₁ + r₂

                             

TWO WAY FINITE AUTOMATA:

            Allow the tape head to move left as well as right.

           

            A two-way deterministic finite automaton (2 DFA) is a quintuple M = (Q, Σ, F, δ, q₀), where Q, Σ, F and q₀ are as before, and δ is a map from a×Σ to Q×{L,R}.

            If δ(q,a) = (P,L), then in state q, scanning input symbol a, the 2 DFA enters state P and moves its head left one square.

            Same for δ(q,a) = (P,R)

INSTANTANEOUS DESCRIPTION (ID) OF A 2 DFA:

            This describes the input string, current state and current position of the input head.

            The relation ├_m on ID’s such that I₁ ├_m I₂ iff M can go grom the ID₁ to ID₂ in one move.

            In ID of M is a string in Σ* Q Σ*.

Example:

            wqx, where w and n are in Σ* and q is in Q.

i)              wn is the input string.

ii)            q is the current state.

iii)          The input head is scanning the first symbol of x.

If x = ε, then the input head has moved off the right end of the output.

We define the relation ├_m of just Г if M is understood, by

1.      a₁ a₂….a_i-1 q a_i…a_n ├ a₁ a₂….a_i-1 P a_{i-1 ….} a_n  whenever δ(q,a_i) = (P,R) and

2.  a1 a2….a_i-2 q a_i…a_n ├ a1 a2….a_i-2 P a_{i-1 ….} a_n whenever δ(q,a_i) = (P,L) and i>1.

·         i>1 prevents moving off to the left end of the tape.

·         We define L(M) = {w / q0w├^* wp for some p in F}

                                       ├^* reflexive / transitive closure of ├.

            W is accepted by M if, starting in state q0 with w on the input tape and the head at the left end of w, M eventually enters a final state at the same time it falls off the right end of the input tape.

MOORE MACHINE AND MEALY MACHINE

           

            Consider the automaton in which the output is chosen from some other alphabet.

If the output function depends only on the present state, the automaton is called Moore machine.

            If the output function depends only on the present state and present input, the automaton is called mealy machine.

MOORE MACHINE:

            A Moore machine M = (Q, Σ, O, f, δ, q0)

Q - Finite set of states

Σ - Input alphabet

O - Output alphabet

δ - Q* Σ à Q is the transition function

f - Output function mapping f: Q à O

q₀ - Initial state

EXAMPLE

            Consider the machine defined by the table

PRESENT STATE	NEXT STATE		OUTPUT
	After i/p a	After i/p b
q 0 q 1 q 2 q 3	q 1 q 3 q 0 q 3	q 3 q 1 q 3 q 2	1 0 0 1

            The transition graph is given by

                                

Transition of states:

 Let w = abab be the input string

·         The machine starts with q₀ whose output is 1

·         If ‘a’ is the input, the machine moves to q₁ with output 0.

·         Then, if ‘b’ is the next input the machine remains in state q₁ itself with output 0.

·         If ‘a’ is an input the machine reads ‘a’ and moves to q₃ producing an input 1.

·         Next input is ‘b’. it moves from q₂ and the output is 0.

·         The traced states are

                q₀             q₁        q₁         q₃         q₂

MEALY MACHINE:

 A mealy machine M is represented by 6 tuple M = (Q, Σ, O, f, δ, q₀)

Q - Finite set of states

Σ - Input alphabet

O - Output alphabet

δ - Q*Σ à Q is the transition function

f - Output function mapping f: Σ *Q à O

q₀ - Initial state

EXAMPLE

            Consider the machine defined by the table

PRESENT STATE	NEXT STATE
	After i/p a		After i/p b
	State	o/p	State	o/p
q0 q1 q2 q3	q3 q2 q3 q0	0             1 1 1	q1 q3               q3 q3	0 1 0 1

            The transition graph is given by

Let w=bbbaa

·         The machine starts with q₀. If ‘b’ is the input symbol, machine moves to q₁ with output 0.

·         If again ‘b’ is the i/p symbol, the machine moves to q₃ with output 1.

·         If ‘b’ is the i/p given, machine moves to itself with output 1.

·         If ‘a’ is i/p machine moves to q₀ with o/p 1.

·         If ‘a’ is the i/p, machine moves to q₃ with o/p 0.

·         Hence the o/p string is 01110.

NOTE:

·               In a mealy machine the number of characters in the o/p string is same to the number of letters in    i/p string.

·               In a moore machine the length of the o/p string is one more than the length of the input string.

THEOREM 1:

If M₁ = (Q, Σ, O, f, δ, q₀) is a Moore machine, then there is a Mealy machine M₂ equivalent to M₁

Proof:

        Let M₂ = (Q, Σ, O, f ’, δ, q₀) and defined f ’(q,a) = f(δ(q,a)) for all states q and input symbol ‘a’.

      Then, M₁ and M₂ enter the same sequence of states on the same input, and with each transition M₂ emits the O/P that M₁ associates with the states entered.

Example:

 

 Construct mealy machine equivalent to Moore machine given below

PRESENT STATE	NEXT STATE		OUTPUT
	0	1
q0 q1 q2 q3	q1 q3 q2 q0	q2 q2 q1 q3	1 0 1 1

Solution :

 

   From theorem proof f ‘(q,a) = f(δ(q,a))

   Present states and output is given as

              q₀         1

              q₁         0

              q₂         1

              q₃         1

Therefore mealy machine table will be

PRESENT STATE	NEXT STATE
	0		1
	State	O/P	State	O/P
q0 q1 q2 q3	q1 q3 q2 q0	0 1 1 1	q2 q2 q1 q3	1               1 0 1

THEOREM 2:

If M₁ = (Q, Σ, O, f, δ, q₀) is a Mealy machine, then there is a Moore machine M₂ equivalent to M₁

Proof:

     Let M₂ = (Q*O, Σ, O, f ‘, δ ‘, [q₀, b₀]), where b₀ is an arbitrarily selected member of ‘O’. i.e., the states of M₂ are pairs [q, b] consisting of a state of M₁ and an output symbol. Define

                                     δ‘([q, b],a) = [δ[q, a], f(q, a)] and f ‘([q, a]) = b

If M₁ enters states q₀ , q₁,…… q_n on input a₁,a₂…..a_n and produces output b₁,b₂…b_n then M₂ enters states [q₀,b₀], [q₁,b₁]……….[q_n,b_n] and produces outputs b₀,b₁……b_n.

EXAMPLE :

             Construct moore machine equivalent to mealy machine given below

Consider the mealy machine

PRESENT STATE	NEXT STATE
	0		1
	State	o/p	State	o/p
q1 q2 q3 q4	q3 q1              q2 q4	0 1 1 1	q2 q4 q1 q3	0              0 1               0

·    The states of Moore machine are Q*O

[q1, 1]   [q1, 0]

[q2, 1]   [q2, 0]

[q3, 1]   [q3, 0]

[q4, 1]   [q4, 0]

    

·    From the proof

                 

     δ‘([q, b],a) = [δ[q, a], f(q, a)]

Present states	Next states	Output
	a = 0               a = 1
[q1,1] [q1,0] [q2,1] [q2,0] [q3,1] [q3,0] [q4,1] [q4,0]	[q3,0]              [q2,0] [q3,0]              [q2,0] [q1,1]              [q4,0] [q1,1]              [q4,0] [q2,1]              [q1,1] [q2,1]              [q1,1] [q4,1]              [q3,1] [q4,1]              [q3,0]	1 0 1 0 1 0 1 0

EQUIVALENCE OF NFA’S WITH AND WITHOUT ε-moves

THEOREM 3:

      If L is accepted by a NFA with ε-transition, then L is accepted by an NFA without ε-transition.

Proof:

        Let M = (Q, Σ, O, F, δ, q₀) be an NFA with ε-transition.

Let M‘= (Q, Σ, O, F‘, δ ‘, q₀)

 

                           F U {q₀} if ε-closure(q₀) contains a state in F

Where, F’ =       

                           F         otherwise

δ‘(q, a) = (q, a), q  Q, a  Σ

·                     Then M’ has no ε-transition. Note that δ‘ and ’ are same but δ and  are not same.

·                     We show by induction that

            δ‘{q₀,w} = (q₀,w) for any string w. Note that w = ε ,

δ‘(q₀, ε) = {q₀} and {q₀, ε } = ε-closure{q₀}. So, δ‘(q₀, ε) ≠ (q₀, ε)

So, the induction is not true for the string having length 0. We start our induction for the string having length 1.

BASICS STEPS:

  Let ‘a’ be a string of length 1. i.e., aΣ δ‘{q0,a} = (q0,a) by definition of δ ‘.

INDUCTION:

     Assume that δ‘(q₀, x) = (q₀,x) for any string x of length  n. Assume w is a string of length n+1. Let w = xa for some symbol a  Σ. Then,

        δ‘(q₀, w) = δ‘(q₀, xa)

                         = δ‘(δ‘(q₀, x), a)

                         = δ‘( (q₀, x), a)

                         = δ‘(p, a)

  Where p =  (q₀,x) say

  We must show that

          

             δ‘(p, a) = (q0,xa)

  but δ‘(p, a) = U δ‘(q, a)  =  U (q, a)

                             qp                 qp

                            = ((q₀, x), a)

                            = (q₀, xa)

                            = (q₀, w)

Hence δ‘(q₀, w) = (q₀, w)

·                     Lastly we show that δ‘(q₀, w) contains a state of F’. If (q₀, w) and only if contains the state of F’. If w = ε then,

   δ‘{q₀, ε} = {q₀} and (q₀, ε) = ε-closure{q₀}.

·                     Note that ε-closure{q₀} contains a state (possibly q₀) in F. Hence (q₀, ε) contains a state in F. Converse is clear from definition of F’.

·                     If w ≠ ε, then w = xa for some symbol ‘a’. If (q₀, w) contains the same state in F’. Conversely, If δ‘(q₀, w) contains the state in F’ other than q₀, q₀  F, then = ε-closure (δ((q₀,x),a) the state in ε-closure(q₀).

THEOREM 4: (CONVERSION OF REGULAR EXPRESSION TO FSA)

    For every regular expression ‘r’ there exists a NFA with ε-transition that    accepts L(r).

Proof:

 

    We prove by induction on the number of operators in the regular expression r* that there is an NFA. M with ε-transition having on final state and no transition out of this final states such that T(M) = L(r).

Basics steps:

 

          Suppose ‘r’ is ε, φ or a for some a  Σ. Then NFA in figure clearly satisfies condition.

      r = ε                                               r = φ                                          r = a  

Induction steps:

  

   Assume the theorem is true for ‘r’ having fewer than i operators, i  1. Let ‘r’ have i operators. We discuss three case on the form of ‘r’.

Case1:

    

·                     Let r = r₁ + r₂. Both r₁ and r₂ must have fewer than i operators. Thus, there are NFA’s

                   M₁ = (Q₁, Σ₁, {f₁}, δ₁, q₁) and   

                   M2 = (Q₂, Σ₂, {f₂}, δ₂, q₂) with T(M₁) = L(r₁) and T(M₂) = L(r₂).

·                     Assume Q₁ and Q₂ are disjoint. Let q₀ be a new initial state and f₀ a new final state. Construct

                    M = (Q₁ U Q₂ U {q₀, f₀}, Σ1 U Σ2, δ, q₀, {f₀})

    Where δ is defined by

 1.     δ{q₀, ε } = {q₁,q₂}

 2.     δ{q, a } = δ₁{q, a} if q  Q₁ – {f₁}, aΣ₁ U {ε}

                      = δ₂ {q, a} if q  Q2 – {f2}, a  Σ₂ U {ε}

3.         δ1(f₁, ε) = δ₂(f₂, ε) = {f₀}

·                     All the moves of M₁ and M₂ are present in M. The construction of M is depicted in figure. Any path in the transition diagram of M from q₀ to f₀ must be going to either q₁ or q₂ on ε and follow any path in M₁ or in M₂ corresponding by and reaches f₀ along the path ε.

·                     These are the only paths from q₀ to f₀. There is a path labeled x in M from q₀ to f₀ if and only if there is a path labeled x in M₁ from q₁ to f₁ or a path in M₂, from q₂ to f₂. Hence T(M) = T(M₁) U T(M₂).

    Case 2:

·                     r = r₁r₂. Let M₁ and M₂ be as in case 1. Construct

        M = (Q₁ U Q₂, Σ₁U Σ₂, δ, {q₁}, {f₂})

 Where δ is given by

1.  δ{q, a } = δ₁{q, a } if q  Q₁ – {f₁}, a € Σ₁- {ε}

2.  δ₁(f₁, ε) = {q₂}

3.  δ{q, a } = δ₂{q, a } if qQ₂, a  Σ₂U{ε}

·                     Every path in M from q₁ to f₂ is a path labeled by some string x from q₁ to f₁ followed by the edge from f₁ to q₂ labeled ε, followed by a path labeled by some string y from q₂ to f₂.

·                     T(M) = {xy : x  T(M₁), y  T(M₂) } Hence

·                     T(M) = T(M₁)T(M₂)

 Case 3:

 

·                     r =( r₁)*. Let M₁ = (Q₁, Σ₁, {f₁}, δ₁, q₁) and T(M₁) = r₁. Construct

M = (Q₁ U {q₀, f₀}, Σ, δ, q₀, {f₀})

Where δ is given by

1.      δ{q₀, ε } = δ{f₁, ε } = {q₁,fo}

2.      δ{q, a} = δ₁{q, a}  for q  Q₁ – {f₁}, a  Σ₁ U { ε }

 

·                     Any path from q₀ to f₀ consists either of a path from q₀ to f₀ on ε or a path from q₀ to q₁ on ε followed by some number of paths from q₁ to f₁, then back to q₁ on ε. There is a path in M from q₀ to f₀ labeled x if and only if we write x = x₁, x₁,…….x_j for some jc such that xT(M1). Hence T(M) = T(M₁)*.

APPLICATIONS:

·                     All though we stress the abstract and mathematical nature of formal languages and automata, these concepts have wide spread applications in computer science.

·                     Formal languages and grammars are used widely in connection with programming languages.

·                     In most of our programming, we work with more or less intuitive understanding of the language in which we write though it is unfamiliar, we refer to description such as syntax diagrams.

·                     If we wrote a compiler on to reason about correctness of program, a precise description of the languages needed at almost every step.

·                     Among the ways in which programming languages can be defined precisely, grammars are perhaps the most widely used.

Example:

	0	1
0	0                                        No carry	1 No carry
1	1 No carry	0 carry

·                     A binary adder is an integral of any general purpose computer. Such an adder takes two bit strings representing numbers and produces their sum as output.

·                     Let us assume that we are dealing only with the integers and that we use a representation in which

              X = a₀a₁……a_n

         Stands for the integer

                       n 

           V(x) = Σ   ai 2ⁱ

                    λ=0    

      This is the usual binary representation in reverse.

·                     A serial adder processes two numbers. X = a₀a₁….a_n and y=b₀b₁….b_n, bit by bit. Starting at the left end each bit addition creates a digit for the sum as well as a carry digit for the next higher position. A binary addition table in figure summarizes the process.

·                     The figure tells us that an adder is a box that accepts two bits and produces their sum bit and the possible carry.

·                     It describes what an adder does and explains about its internal working. An automaton can makes this much more explicit.                                                                                                                                                                                                   

                               

                                                                   CARRY

Example 2:

·   The input to the transducer are the list pairs (ai,l,i), the output will be the sum list di.

·   Again we represent the automation by a graph, now labeling the edges (ai,bi)/di.

·   The carry from one step to two internal states labeled “Carry” & “no carry”.

·   Initially, the transducer will be in state “no carry”.

·   It will remain in this state until a but pair (1, 1) is encountered.

·   This will generate a carry is then taken into account when it takes the automation into “carry state”.

·   The presence of a carry is thn taken into account when the next but pair is read.

·   As this example (2) indicates, the automation serves as a bridge between the very high-level, functional description of a circuit and its logical implementation through transistors, gates & flip flops.

·   The automation clearly shows (ex 2) the decision logic, yet it is formal enough to lend itself to precise mathematical manipulation.

·   For this reason, digital design methods rely heavily on concepts from automata theory.