Finite Automata: Types, Definitions, and Examples

UNIT I PART II FINITE AUTOMATA

Finite Automata Definition: A finite automaton (FA) is a simple idealized machine used to recognize patterns within input taken from some character set (or alphabet) . The job of an FA is to accept or reject an input depending on whether the pattern defined by the FA occurs in the input. Finite Automata(FA) is the simplest machine to recognize patterns. A Finite Automata consists of the following : Q : Finite set of states. : set of Input Symbols. q : Initial state. F : set of Final States. : Transition Function. Formal specification of machine is { Q, , q, F, }.

Types of FA FA is characterized into two types: 1) Deterministic Finite Automata (DFA) DFA consists of 5 tuples {Q, , q, F, }. Q : set of all states. : set of input symbols. ( Symbols which machine takes as input ) q : Initial state. ( Starting state of a machine ) F : set of final state. : Transition Function, defined as : Q X --> Q.

1. Deterministic Finite Automata(DFA) In a DFA, for a particular input character, the machine goes to one state only. A transition function is defined on every state for every input symbol. Also in DFA null (or ) move is not allowed, i.e., DFA cannot change state without any input character. For example, below DFA with = {0, 1} accepts all strings ending with 0. One important thing to note is, there can be many possible DFAs for a pattern. A DFA with minimum number of states is generally preferred.

2. Nondeterministic Finite Automata(NFA) NFA is similar to DFA except following additional features a) Null (or ) move is allowed i.e., it can move forward without reading symbols. b) Ability to transmit to any number of states for a particular input. However, these above features don t add any power to NFA. If we compare both in terms of power, both are equivalent. Due to above additional features, NFA has a different transition function, rest is same as DFA. : Transition Function : Q X ( U ) --> 2 ^ Q. As you can see in transition function is for any input including null (or ), NFA can go to any state number of states.

NFA For example, below DFA with = {0, 1} accepts all strings ending with 0. One important thing to note is, in NFA, if any path for an input string leads to a final state, then the input string accepted. For example, in above NFA, there are multiple paths for input string 00 . Since, one of the paths leads to a final state, 00 is accepted by above NFA.

Some Important Points: 1. Every DFA is NFA but not vice versa. Justification: Since all the tuples in DFA and NFA are the same except for one of the tuples, which is Transition Function ( ) In case of DFA : Q X --> Q In case of NFA : Q X --> 2Q Now if you observe you ll find out Q X > Q is part of Q X > 2Q. In the RHS side, Q is the subset of 2Qwhich indicates Q is contained in 2Qor Q is a part of 2Q, however, the reverse isn t true. So mathematically, we can conclude that every DFA is NFA but not vice-versa. Yet there is a way to convert an NFA to DFA, so there exists an equivalent DFA for every NFA. 2. Both NFA and DFA have same power and each NFA can be translated into a DFA. 3. There can be multiple final states in both DFA and NFA. 4. NFA is more of a theoretical concept. 5. DFA is used in Lexical Analysis in Compiler.

Applications of FA Finite automata is used for solving several common types of computer algorithms. Some of them are: 1) Design of digital circuit. 2) String matching 3) Communication protocols for information exchange. 4) Lexical analysis phase of compiler. 5) FA can work as an algorithm for regular language. It can be used for checking whether a string w L, where L is regular language.

Examples of DFA Example 1: Design a FA with = {0, 1} accepts those string which starts with 1 and ends with 0. Solution: The FA will have a start state q0 from which only the edge with input 1 will go to the next state. States/ symbols 0 1 q0 q1 q1 q2 q1 q2* q2 q1 Transition Diagram Transition Table

Examples of DFA Example 2: Design a FA with = {0, 1} accepts the only input 101. Solution: States/ symbols 0 1 q0 q1 q1 q2 q2 q3 q3*

Examples of DFA Example 3: Design FA with = {0, 1} accepts even number of 0's and even number of 1's. Solution: This FA will consider four different stages for input 0 and input 1. The stages could be: Here q0 is a start state and the final state also. Note carefully that a symmetry of 0's and 1's is maintained. We can associate meanings to each state as: q0: state of even number of 0's and even number of 1's. q1: state of odd number of 0's and even number of 1's. q2: state of odd number of 0's and odd number of 1's. q3: state of even number of 0's and odd number of 1's.

Examples of DFA Example 4: Design FA with = {0, 1} accepts the set of all strings with three consecutive 0's. Solution: The strings that will be generated for this particular languages are 000, 0001, 1000, 10001, .... in which 0 always appears in a clump of 3. The transition graph is as follows:

Examples of DFA Example 5: Design a DFA L(M) = {w | w {0, 1}*} and W is a string that does not contain consecutive 1's. Solution: When three consecutive 1's occur the DFA will be: Here two consecutive 1's or single 1 is acceptable, hence The stages q0, q1, q2 are the final states. The DFA will generate the strings that do not contain consecutive 1's like 10, 110, 101,..... etc.

Examples of DFA Example 6: Design a FA with = {0, 1} accepts the strings with an even number of 0's followed by single 1. Solution: The DFA can be shown by a transition diagram as:

Examples of DFA Example 7: Draw a DFA for the language accepting strings with substring 01 over input alphabets = {0, 1}

Examples of DFA Example 8: Draw a DFA for the language accepting strings ending with abb over input alphabets = {a, b}

Examples of DFA Example 9: Draw a DFA for the language accepting strings with substring 0011 over input alphabets = {0, 1}

Examples of NFA Example 1: Design an NFA with = {0, 1} accepts all string ending with 01. Solution: Hence, NFA would be:

Examples of NFA Example 2: Design an NFA with = {0, 1} in which double '1' is followed by double '0'. Solution: Now before double 1, there can be any string of 0 and 1. Similarly, after double 0, there can be any string of 0 and 1. Hence the NFA becomes:

Examples of NFA Example 3: Design an NFA in which all the string contain a substring 1110. Solution: The language consists of all the string containing substring 1010. The partial transition diagram can be: Now as 1010 could be the substring. Hence we will add the inputs 0's and 1's so that the substring 1010 of the language can be maintained. Hence the NFA becomes:

Examples of NFA Example 4: Design NFA which accepts any binary string that contains 00 or 11 as a substring. Solution: We have show 2 paths for 2 substrings . One for 00 substring and another for 11 substring. In above NFA, we have shown upper path for 00 substring and lower path for 11 substring.

Converting NFA to DFA The following steps are followed to convert a given NFA to a DFA- Step 1: Step 2: Add start state of the NFA to Q . Add transitions of the start state to the transition table T . If start state makes transition to multiple states for some input alphabet, then treat those multiple states as a single state in the DFA. In NFA, if the transition of start state over some input alphabet is null, then perform the transition of start state over that input alphabet to a dead state in the DFA. Step 3: If any new state is present in the transition table T , Add the new state in Q . Add transitions of that state in the transition table T . Step 4: Keep repeating Step 3 until no new state is present in the transition table T . Finally, the transition table T so obtained is the complete transition table of the required DFA. Let Q be a new set of states of the DFA. Q is null in the starting. Let T be a new transition table of the DFA.

Example: Convert the following Non-Deterministic Finite Automata (NFA) to Deterministic Finite Automata (DFA) Solution: State / Alphabet a b q0 q0 q0, q1 q1 *q2 *q2 Step 1: Let Q be a new set of states of the Deterministic Finite Automata (DFA). Let T be a new transition table of the DFA.

Step 2: Add transitions of start state q0 to the transition table T . Step 4: New state present in state Q is {q0, q1, q2}. Add transitions for set of states {q0, q1, q2} to the transition table T . State / Alphabet a b q0 q0 {q0, q1} Step 3: New state present in state Q is {q0, q1}. Add transitions for set of states {q0, q1} to the transition table T . State / Alphabet a b q0 q0 {q0, q1} {q0, q1} q0 {q0, q1, q2} {q0, q1, q2} q0 {q0, q1, q2} State / Alphabet a b q0 q0 {q0, q1} {q0, q1} q0 {q0, q1, q2}

Step 5: Since no new states are left to be added in the transition table T , so we stop. States containing q2 as its component are treated as final states of the DFA. Finally, Transition table for Deterministic Finite Automata (DFA) is- Now, Deterministic Finite Automata (DFA) may be drawn as- State / Alphabet a b q0 q0 {q0, q1} {q0, q1} q0 *{q0, q1, q2} *{q0, q1, q2} q0 *{q0, q1, q2}

NFA to DFA conversion Example: Convert the given NFA to DFA. Solution: For the given transition diagram we will first construct the transition table. State / Alphabet 0 1 q0 q0 q1 q1 {q1, q2} q1 *q2 q2 {q1, q2}

Transition table for DFA is State / Alphabet 0 1 [q0] [q0] [q1] [q1] [q1, q2] [q1] *[q2] [q2] [q1, q2] *[q1, q2] [q1, q2] [q1, q2] The Transition diagram will be:

NFA with Non-deterministic finite automata(NFA) is a finite automata where for some cases when a specific input is given to the current state, the machine goes to multiple states or more than 1 states. It can contain move. It can be represented as M = { Q, , , q0, F}. Where Q: finite set of states : finite set of the input symbol q0: initial state F: final state : Transition function NFA with move: If any FA contains transaction or move, the finite automata is called NFA with move. -closure: -closure for a given state A means a set of states which can be reached from the state A with only (null) move including the state A itself.

Steps for converting NFA with to DFA: Step 1: We will take the -closure for the starting state of NFA as a starting state of DFA. Step 2: Find the states for each input symbol that can be traversed from the present. That means the union of transition value and their closures for each state of NFA present in the current state of DFA. Step 3: If we found a new state, take it as current state and repeat step 2. Step 4: Repeat Step 2 and Step 3 until there is no new state present in the transition table of DFA. Step 5: Mark the states of DFA as a final state which contains the final state of NFA.

Example 1: Convert the given NFA into its equivalent DFA. Solution: Let us obtain the -closure of each state. -closure(q0) = {q0, q1, q2} -closure(q1) = {q1, q2} -closure(q2) = {q2} Now we will obtain ' transition. Let -closure(q0) = {q0, q1, q2} call it as state A. '(A, 0) = -closure{ ((q0, q1, q2), 0)} = -closure{ (q0, 0) (q1, 0) (q2, 0)} = -closure{q0} = {q0, q1, q2}

'(A, 1) = -closure{((q0, q1, q2), 1)} = -closure{ (q0, 1) (q1, 1) (q2, 1)} = -closure{q1} = {q1, q2} call it as state B '(A, 2) = -closure{ ((q0, q1, q2), 2)} = -closure{ (q0, 2) (q1, 2) (q2, 2)} = -closure{q2} = {q2} call it state C Thus we have obtained '(A, 0) = A '(A, 1) = B '(A, 2) = C The partial DFA will be:

Now we will find the transitions on states B and C for each input. Hence '(B, 0) = -closure{ ((q1, q2), 0)} = -closure{ (q1, 0) (q2, 0)} = -closure{ } = '(B, 1) = -closure{ ((q1, q2), 1)} = -closure{ (q1, 1) (q2, 1)} = -closure{q1} = {q1, q2} i.e. state B itself '(B, 2) = -closure{ ((q1, q2), 2)} = -closure{ (q1, 2) (q2, 2)} = -closure{q2} = {q2} i.e. state C itself Thus we have obtained '(B, 0) = '(B, 1) = B '(B, 2) = C

The partial transition diagram will be: '(C, 2) = -closure{ (q2, 2)} = {q2} Hence the DFA is: Now we will obtain transitions for C: '(C, 0) = -closure{ (q2, 0)} = -closure{ } = '(C, 1) = -closure{ (q2, 1)} = -closure{ } =

Example: Convert the NFA with into its equivalent DFA. Solution: Let us obtain -closure of each state. -closure {q0} = {q0, q1, q2} -closure {q1} = {q1} -closure {q2} = {q2} -closure {q3} = {q3} -closure {q4} = {q4}

Now, let -closure {q0} = {q0, q1, q2} be state A. Hence '(A, 0) = -closure { ((q0, q1, q2), 0) } = -closure { (q0, 0) (q1, 0) (q2, 0) } = -closure {q3} = {q3} call it as state B. '(A, 1) = -closure { ((q0, q1, q2), 1) } = -closure { ((q0, 1) (q1, 1) (q2, 1) } = -closure {q3} = {q3} = B. The partial DFA will be

Now, '(B, 0) = -closure { (q3, 0) } = '(B, 1) = -closure { (q3, 1) } = -closure {q4} = {q4} i.e. state C For state C: '(C, 0) = -closure { (q4, 0) } = '(C, 1) = -closure { (q4, 1) } = The DFA will be,

Minimization of DFA Minimization of DFA means reducing the number of states from given FA. Thus, we get the FSM(finite state machine) with redundant states after minimizing the FSM. We have to follow the various steps to minimize the DFA. These are as follows: Step 1: Remove all the states that are unreachable from the initial state via any set of the transition of DFA. Step 2: Draw the transition table for all pair of states. Step 3: Now split the transition table into two tables T1 and T2. T1 contains all final states, and T2 contains non-final states. Step 4: Find similar rows from T1 such that: 1. (q, a) = p 2. (r, a) = p That means, find the two states which have the same value of a and b and remove one of them. Step 5: Repeat step 3 until we find no similar rows available in the transition table T1. Step 6: Repeat step 3 and step 4 for table T2 also. Step 7: Now combine the reduced T1 and T2 tables. The combined transition table is the transition table of minimized DFA.

Example: Solution: Step 1: In the given DFA, q2 and q4 are the unreachable states so remove them. Step 2: Draw the transition table for the rest of the states. State\ Alphabet 0 1 q0 q1 q3 q1 q0 q3 *q3 q5 q5 q5 *q5 q5

Step 3: Now divide rows of transition table into two sets as: 1. One set contains those rows, which start from non-final states: State\Alphabet 0 1 q0 q1 q3 q1 q0 q3 2. Another set contains those rows, which starts from final states. State\Alphabet 0 1 q3 q5 q5 q5 q5 q5 Step 4: Set 1 has no similar rows so set 1 will be the same. Step 5: In set 2, row 1 and row 2 are similar since q3 and q5 transit to the same state on 0 and 1. So skip q5 and then replace q5 by q3 in the rest. State\Alphabet 0 1 q3 q3 q3

. Step 6: Now combine set 1 and set 2 as: State\Alphabet 0 1 q0 q1 q3 q1 q0 q3 *q3 q3 q3 Now it is the transition table of minimized DFA.

Moore Machine Moore machine is a finite state machine in which the next state is decided by the current state and current input symbol. The output symbol at a given time depends only on the present state of the machine. Moore 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 symbols O: output alphabet : transition function where Q Q : output function where Q O

Example 1: The state diagram for Moore Machine is Transition table for Moore Machine is: 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. Input: 010 Transition: (q0,0) => (q1,1) => (q1,0) => q2 Output: 1110(1 for q0, 1 for q1, again 1 for q1, 0 for q2)

Example 2: Design a Moore machine to generate 1's complement of a given binary number. Solution: To generate 1's complement of a given binary number the simple logic is that if the input is 0 then the output will be 1 and if the input is 1 then the output will be 0. That means there are three states. One state is start state. The second state is for taking 0's as input and produces output as 1. The third state is for taking 1's as input and producing output as 0.

Thus we get 00100 as 1's complement of 1011, we can neglect the initial 0 and the output which we get is 0100 which is 1's complement of 1011. The transaction table is as follows: Hence the Moore machine will be, For instance, take one binary number 1011 then Input 1 0 1 1 State q0 q2 q1 q2 q2 Thus Moore machine M = (Q, q0, , O, , ); where Q = {q0, q1, q2}, = {0, 1}, O = {0, 1}. the transition table shows the and functions. Output 0 0 1 0 0

Example 3: Construct a Moore machine that determines whether an input string contains an even or odd number of 1's. The machine should give 1 as output if an even number of 1's are in the string and 0 otherwise. Solution: The Moore machine will be: This is the required Moore machine. In this machine, state q1 accepts an odd number of 1's and state q0 accepts even number of 1's. There is no restriction on a number of zeros. Hence for 0 input, self-loop can be applied on both the states.

Mealy Machine A Mealy machine is a machine in which output symbol depends upon the present input symbol and present state of the machine. In the Mealy machine, the output is represented with each input symbol for each state separated by /. 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 to find 2 s complement of given number Solution: 2 s complement of a given number can be found by changing bits from right end till the first 1 and then complementing the remaining bits . E.g . 2 s complement of binary number 0101101000 is calculated as 0 1 0 1 1 0 1 0 0 0 1 0 1 0 0 1 1 0 0 0

Conversion from Mealy machine to Moore Machine Example 1: Convert the following Mealy machine into equivalent Moore machine. The state q1 has only one output. The state q2 and q3 have both output 0 and 1. So we will create two states for these states. For q2, two states will be q20(with output 0) and q21(with output 1). Similarly, for q3 two states will be q30(with output 0) and q31(with output 1). Transition table for Moore machine will be: Solution: Transition table for above Mealy machine is as follows:

Transition diagram for Moore machine will be: Transition Table for Moore machine will be: