Unacademy-TOC.pdf

 2 Finite Automata Chapter 2 2.1 FINITE AUTOMATA Definitions It is a mathematical model which contains a finite number of states and transitions...

 2 Finite Automata Chapter 2 2.1 FINITE AUTOMATA Definitions It is a mathematical model which contains a finite number of states and transitions among states in response to inputs. FINITE AUTOMATA Finite Finite automata automata without with output output Deterministic Non-Deterministic Epsilon Moore Mealy finite finite Non-Deterministic finite automata machine machine automata (DFA) automata (NFA) (∈-NFA) Finite automata without output: Input tape b a b a a a Head q0 b q1 a q2 b q3 Finite a control memory Finite Automata qn a qn–1 q4 Fig. 2.1 Diagram of Finite Automata 17 Chapter 2 Input tape: It consists of many cells where each cell can have only one symbol. Input tape contains a single string. Head: It reads one symbol at a time from an input string. Finite control memory: Memory which is having the finite number of states. 2.2 FINITE ACCEPTOR (FINITE AUTOMATA WITHOUT OUTPUT) Deterministic finite automata (DFA) y A DFA is set of 5 tuple and defined as: M = {Q, ∑ , δ , q0, F} Where Q : Finite set of states ∑ : Input alphabet δ : Transition function q0 : Initial State F : A finite set of final states Here δ : Transition function Q× ∑ → Q ↓ Next State {A, B, C} × {a, b} → Only deterministic output will come. (A,a) (A, b) A (B, a) B (B, b) C (C, a) (C, b) Fig. 2.2 y  FA is a finite Automata in which, from every state on every input D symbol, exactly one transition should exist. y DFA cannot use empty string transition. y In DFA, if any string terminates in a state which is different from accepting state, then DFA rejects that string. Finite Automata y All DFA are NFA. 18  Chapter 2 SOLVED EXAMPLES Q1 Language accepted by above Finite Automata? Sol: L = {a, aa, aaa, aaaa, ba, bbbba, bababaaaa,……………} = Set of all strings ends with ‘a’ over ∑ = {a, b} Q2 Language accepted by above Finite Automata? Sol: L = {ba, bab, baa, aba, abaa, abab, ………} = Set of all strings containing “ba” as a substring over ∑ = {a, b}. Rack Your Brain Finite Automata How many number of final state require to accept & in minimal finite automata? 19 Chapter 2 Minimal DFA: When all the states in a DFA are distinguishable, i.e. no two states in a final DFA are equivalent. The DFA is known as minimal DFA. SOLVED EXAMPLES Q1 Sol: L = {∈, a, b, aa, bb, ab, ba, aaa, ………………} DFA: Transition table: Q2 Sol: L = {a, b, ab, ba, aa, bb, ……….……………} DFA: Transition table: Finite Automata 20  Chapter 2 Q3 Sol: a, aa, aaa, aaaa,................   ab, aab    L = aba  abb       DFA: a, b q0 a q1 b Dead q2 State a,b y If any string starts with ‘a’, then it will be accepted by the DFA. Let’s consider an example. String w = aab d (q0, a) = q1 d (q1, a) = q1 d (q1, b) = q1 (accepted by DFA) y But if the string starts with ‘b’, it directly goes to the dead state and get rejected by the DFA. Let’s consider an example. String w = ba d (q0, b) = q2 d (q2, a) = q2 (Dead state) Thus, string ba is rejected (not accepted by DFA). Dead state: It is a rejecting state i.e a non final state from which there is no path to the final state. Finite Automata Once we reach to dead state, there is no way to reach the final state. 21 Chapter 2 Transition table: Q4 Sol: L = {ab, aab, abb, aaab, abab, aabb, ………….} DFA: a b a b q0 q1 q2 b a q3 a,b Transition table: Q5 Sol: L = {ab, aba, aab, ………….………….} DFA: b a a, b a b Finite Automata q0 q1 q2 22  Chapter 2 Q6 Sol: L = {a, aa, ba, aaa, aba, ………….………….} DFA: b a q0 a q1 b Q7 Sol: L = {ba, aba, bba, aaba, ………….………….} DFA: a b q0 b q1 a q2 b a Previous Years’ Question 1 (GATE 2009) 1 0 0 0 1 The above DFA accepts the set of all strings over {0, 1} that 1) Begin either with 0 or 1 2) End with 0 3) End with 00 4) Contain the substring 00 Sol: 3) Finite Automata 23 Chapter 2 Q8 Sol: L = {a, aa, aba, aaa, ………….………….} DFA: a b a b q2 q0 q1 a b q3 a,b Q9 Sol: L = {a, b, aaa, bbb, aba, bab, ………….………….} DFA: a b a q1 b q0 q2 a b b q3 b a q4 a Finite Automata 24  Chapter 2 Q10 Sol: L = {ab, ba, aab, abb, baa, ………….………….} DFA: a b q0 a b q1 q2 b a b q3 a b q4 a Q11 Sol: L = {aaaa, baaaa, aaaab, aaaaa, ………….………….} DFA: b a, b a a a q3 a q4 q0 q1 q2 b b b Finite Automata 25 Chapter 2 Q12 Sol: L = {aaa, baaa, abbb, bbba, ………….………….} DFA: a, b a q1 a q2 a q3 q0 b a b b a b q4 q5 b Q13 Sol: L= {∈, abab, abababab,.............aa,bb, aaa,.................................} DFA: b a b q0 a b q2 q1 b a q3 a Q14 Finite Automata 26  Chapter 2 Sol: L = {aaaab, baaab, …………………} DFA: a, b a,b a,b a,b a,b b q0 q1 q2 q3 q4 q5 a q6 a, b Q15 Sol: b b a a a b q0 q1 q2 q3 a b Q16 i) L ii) L iii) L Sol: i) Length of the string is exactly 2 i.e. |w| = 2 a, b a, b a, b a, b q0 q1 q2 q3 Finite Automata 27 Chapter 2 ii) Length of the string is atleast 2 i.e. |w| ≥ 2 a, b a, b a, b q0 q1 q2 iii) Length of the string is at most 2, i.e. |w| ≤ 2 a, b q0 a, b q1 a, b q2 a, b q3 Note: Rack Your Brain If L is a non-empty language such that any win L has length atleast n, then any DFA accepting L must have atleast n +1 states. this statement true (or) false? Q17 L L L Sol: i) All even length strings over ∑ = a,b { } Finite Automata |w| mod 2 = 0 L = { ∈ , aa, bb, ab, …………..} 28  Chapter 2 DFA: a, b q0 q1 a, b ii) All odd length strings over ∑ = a,b { } Odd length strings meSol: |w| mod 2 = 1 DFA: a, b q0 q1 a, b iii) { } All strings whose length is divisible by 3 over ∑ = a,b |w| mod 3 = 0 ∈, aaa, aaaaaa,..................    aab   L=       bbb     q0 a, b q1 a, b q2 a, b Note: Q18 Finite Automata 29 Chapter 2 Sol: i) L = {aa, baa, aba, aab, bbaa,…………….} DFA: b b b a, b a a a q0 q1 q2 q3 0 a's 1 a's 2 a's 3 a's ii) L = {aa, aba, aaa, aaab,…………….} DFA: b b a, b a a q0 q1 q2 iii) L = {∈, a, ab, aa, aba,…………….} DFA: b b b a, b a q1 a q2 a q0 q3 Note: d A A Finite Automata 30  Chapter 2 Grey Matter Alert! { } Number of states in minimal DFA which accepts all the strings over ∑ = a,b such that: a)  Number of a’s is ‘atleast m’ and number of b’s is ‘atleast n’ = (m + 1)(n + 1) b)  Number of a’s is ‘exactly m’ and number of b’s is ‘exactly n’ = (m + 1) (n + 1) + 1 (because of trap state, we require one more state). c)  Number of a’s is ‘atmost m’ and number of b’s is ‘atmost n’ = (m + 1)(n+1) + 1 Previous Years’ Question The minimum possible number of states of a deterministic finite automaton that accepts the regular language L= { { } w 1aw2 | w 1 , w2 ∈ a,b *,| w 1 |= } 2,| w2 | ≥ 3 is ________ Sol: Range: 8 to 8 (GATE 2017 (Set-2)) SOLVED EXAMPLES Q19 Sol: = L {a bn m | n,m ≥ 1} { } = ab, aab, abb, aabb,.................. DFA: a b a b b a Finite Automata a, b 31 Chapter 2 Q20 Sol: = L {a bn m | n,m ≥ 0 } { = ∈, a,b, ab, aa,bb,................... } DFA: a b a, b b a Q21 Sol: =L {a b c | n,m,l ≥ 1} n m l { = abc, aabc, abbc, abcc,.................... } a b c a b c c a b,c a,b a,b,c Q22 Sol: i) L= {a n n ≥ 0,n ≠ 3 } { = ∈, a, aa, aaaa,................. } Finite Automata 32  Chapter 2 a a a a a Not accepting 3a’s ii) L= {a n n ≥ 0,n ≠ 2,n ≠ 4 } { = ∈, a, aaa, aaaaa,................. } a a a a a a Not Not accepting accepting 2a’s 4a’s Rack Your Brain Construct the minimal DFA’s for the language L = (ab | n20) u (b’a | n21} SOLVED EXAMPLES Q1 Sol: Divisible by 2, so two remainders are DFA: 0 1 q0 1 q1 0 (101)2 = (5)10 = Not accepted by DFA: Finite Automata (110)2 = (6)10 = Accepted by DFA Transition table: 33 Chapter 2 Q2 0 Sol: Divisible by 3, so remainders are 1 2 DFA: 0 1 1 0 q0 q1 q2 1 0 Transition table: Q3 0 Sol: Divisible by 4, so remainders are 1 2 3 Finite Automata Transition table: 34  Chapter 2 Here, we can merge q1 and q3 states as one state. DFA: 0 1 1 0 q0 q13 q2 1 0 Q4 Sol: Transition table: Finite Automata ⇒ Here two rows cannot be merged. Since all are different. So, the minimum DFA will contain 7 states. 35 Chapter 2 Q5 Sol: This problem belongs to below NOTE (Case 3). Here n = 6 (even) but not in power of 2. n = 21 * 3 So, minimal DFA contains (1 + 3) = 4 states We can also prove it in descriptive way. Transition table: ⇒ Here, we can merge states q1 and q4 as q14. Similarly, we can merge states q2 and q5 as q25. Hence, transition Table will become: Note: Finite Automata 36  Chapter 2 SOLVED EXAMPLES Q1 Sol: Divisible by 4, so remainders are Input = {0, 1, 2} Transition table: 0 0 2 0 2 1 1 q0 q1 q2 q3 1 2 1 2 0 Operations on DFA: Union: DFA which accepts all strings starting and ending with different symbols { } over ∑ = a,b. L1 = {ab, aab, abb, ……………..} Starts with ‘a’ and ends with ‘b’. DFA: Finite Automata 37 Chapter 2 a b a b q0 q1 q2 b a q3 a,b L2 = {ba, baa, bba, ……………..} = Starts with b and ends with a DFA: b a b a q0 q1 q2 b a q3 a,b DFA for L 1 ∪ L2: a b q0 a q1 b q2 b a b q3 a b q4 Finite Automata a Concatenation: 38  Chapter 2 { } DFA that accepts all strings over ∑ = a,b which starts with a and ends with b. L1 = {Starting with a} = {a, aa, ab, aab, ……………………} a, b q0 a q1 b D a, b L2 = {Ending with b} = {b, ab, bb, aab, ……………………} a b q1 b q2 a Now DFA for L1.L2: a b a b q0 q1 q2 a b D a, b Finite Automata Cross product: 39 Chapter 2 SOLVED EXAMPLES Q1 Sol: L1 = {even number of a’s} = { ∈ , aa, baa, ……………..} DFA: b b a A B a L2 = {even number of b’s} = { ∈ , bb, abb, ……………..} DFA: a a b C D b Cross product: {A, B} × {C, D} = {AC, BC, AD, BD} Where final state = {AC} because A and C are both final states in respective DFA for L1 and L2. Initial State = {AC} because A and C are both initial states in respective DFA for L1 and L2. DFA for cross product: a AC BC a b b b b a AD BD a Finite Automata 40  Chapter 2 Q2 Sol: na(w) ≅ 0 mod 3 & nb(w) ≅ 0 mod 2 DFA: a a a b b b b b b a a a Total number of states = 3 × 2 = 6 Complementation: eg 1: L = set of all strings over ∑ = {a, b} of even length = { ∈, ab, aa, bb, aaaa, ……………………….} Sol: DFA: a, b A B a, b Now, L2 = set of all strings over ∑ ={a,b} of odd length = {a, b, aaa, aab, …………….} L= 2 L= 1 Complement of L 1 DFA for L2: Just complement the above DFA i.e. change the final state as Non-final state and Non-final state as Final State a, b A B Finite Automata a, b 41 Chapter 2 eg 2: L = Set of all strings over ∑ = {a, b} starting with ‘a’ = {a, aa, ab, ……………………………….} Sol: DFA: a, b a A B b C a, b L= 2 L= 1 Complement of L 1 = Set of all strings over ∑ ={a,b} not starting with ‘a’ = { ∈ , b, ba, …………………..} DFA for complement of L1: a, b a A B b C a, b Note: Finite Automata 42  Chapter 2 Previous Years’ Question { } Let L be the language represented by the regular expression ∑ *0011 ∑ * where ∑ = 0, 1 What is the minimum number of states in a DFA that recognizes L (complement of L)? (GATE 2015 SET 3) 1) 4 2) 5 3) 6 4) 8 Sol: 2) Reversal: Reversing a language meSol: reverse all strings present in the language. Steps: a) Draw the state as it is. b) Make final state as initial state and initial state as final state. c) Reverse the edges. d) Remove all the unreachable state and its transition from initial state. Note: DFA for the set of string over ∑ ={a,b} which start with ‘a’. L1 = {a, aa, ab, aab,……………..} DFA: a, b q0 a q1 b q2 a, b Now, Let L2 = Reversal of L1 = {a, aa, ba, baa, ………….} Finite Automata 43 Chapter 2 a, b q0 a q1 a, b q2 q0 a q1 a, b X Can never reach this state from Non-Deterministic initial state. Finite Automata (NFA) Fig 2.3 Previous Years’ Question Consider the following language: (GATE-2020) L = {x ∈ {a, b}*| number of a’s in x divisible by 2 but not divisible by 3} The minimum number of states in DFA that accepts L is ___________. Sol: Range = 6 to 6 Q1 Counting DFA: Number of 2-state DFA with designated initial state that can be constructed over ∑ = a,b.{ } Sol: q0 q1 y Final State can be : Zero state i.e. None of them final   : One state i.e. either q0 final state   or q1 final state   : Two states i.e. q0 and q1 both final state So, Total 2 = 4 possibility. 2 Finite Automata 44  Chapter 2 y q0 on ‘a’ can either go to the state q0 or q1. q0 on ‘b’ can either go to the state q0 or q1. y Similarly, q1 on ‘a’ can either go to the state q0 or q1. q1 on ‘b’ can either go to the state q0 or q1. Total number of ways to construct 2-state DFA with designated initial { } state over ∑ = a,b = 22 * 24 = 26 = 64 Q2 Number of 3-state DFA with designated initial state that can be constructed { } over ∑ = a,b. Sol: q0 q1 q2 y Final state can be: q0 q1 q2 0 final state q0 q1 q2 q0 q1 q2 1 final state q0 q1 q2 q0 q1 q2 2 final q0 q1 q2 state q0 q1 q2 Finite Automata q0 q1 q2 3- final state 45 Chapter 2 Total possibility = 23 = 8 possibility Total number of ways to construct 3-state DFA with a designated initial { } state over ∑ = a,b = 23 * 36 = 8 * 93 = 5832 Note: Given: | ∑ |=m |Q| = number of states = n y Number of ways, we can construct final states = 2n Total cells in δ = n × m =m×n and each cell can be filled in ‘n ways’ So, Total possibility = nm×n    Q × ∑ → 2Q Total number of ways to construct n-state DFA with a designated initial state over ∑ = {1, 2, …………m} containing m symbols Finite Automata = 2n × nm×n 46  Chapter 2 Q3 Number of 2-state DFA’s with a designated initial state accepting φ over { } ∑ = a, b Sol: Zero final state Since neither q0 nor q1 is final state. So, it accepts φ in 16 ways. Case 2: One final states 1) It accepts ∈. Thus, this cannot be the required case. 2) It can be the desired case but not all transition on it is desirable. a, b a, b q0 q1 a, b b a q0 q1 a, b 4 possibility a b q0 q1 a, b a, b q0 q1 Case 3: Two final states It cannot be the described case as it is accepting ∈. ∴ Overall total number of 2-state DFAs with designated initial state accepting φ. { } Over ∑ = a,b = (16 + 4) = 20 Finite Automata 47 Chapter 2 Q4 Number of 2-state DFA with a designated initial state accepting ∑ * (univer- sal language) over ∑ = a, b. { } Sol: Case 1: Zero final state q0 q1 It is not a favourable case as it accepts φ. It cannot accept ∑ *. Case 2: One final state 1) q0 q1 It will not accept ∈ which is part of ∑ *. Thus, it cannot accept ∑ *. Not favourable case. 2) q0 q1 It can be favourable case. a, b a, b q0 q1 a, b b q0 a q1 4 possibility a, b a q0 b q1 a, b q0 a, b q1 Case 3: 2 Final state q0 q1. When both q0 and q1 states are final states, then it will accept ∑ * in 16 possible ways. Finite Automata ∴ Overall, total number of 2–state DFA with designated initial state accepting ∑ * over ∑ ={a,b} = 4 + 16 = 20 48  Chapter 2 Minimization of DFA: Definitions Minimization of DFA meSol: trSol:forming a given DFA into an equivalent DFA that has a minimum number of states. i) Remove all the unreachable states (i.e. states which are not reachable from initial state). ii) Separate all final states in one set and all non-final states in another set. iii) Two states p and q of a DFA are called Indistinguishable if δ * (p, w) ∈ Final state ⇒ δ * (q, w) ∈Final State and δ * (p, w) ∉Final State ⇒ δ * (q, w) ∉Final State for all w ∈ ∑ * iv) On the other hand, if there exists some string w ∈ ∑ * such that δ * (p, w) ∈Final State and δ * (q, w) ∉Final State or vice-versa, then the states p and q are said to be distinguishable by a string ‘w’. v) Identify distinguishable states and use the logic known as seperating the states. It meSol: in each step if the two states in a set are distinguishable seperate them. vi) Stop the algorithm once find no change in partition. SOLVED EXAMPLES Q1 Sol: Finite Automata 49 Chapter 2 State equivalence method: Follow steps i) and step ii), separate all final states in one set and all non final states in another set. {( ) ( )} [0 equivalence class] π0 = A,B , C Let group 1 i.e. g1 = (A, B) and group 2 i.e. g2 = (C) Then, A on ‘a’ goes to the group g1 And B on ‘a’ goes to the group g1. d (A, a) = B (belongs to g1) d (B, a) = B (belongs to g1) A on ‘b’ goes to the group g2 B on ‘b’ goes to the group g2 d (A, b) = C (belongs to g2) d (B, b) = C (belongs to g2) So, A and B will be in same group(set). π1 =π0 [1 equivalence class] Q2 Finite Automata 50  Chapter 2 Sol: State equivalence method: For State B and C: { } π0 =(A), (B, C,D)         (A), (B, C), (D)  π1 =  So, B = C  g 1 g 2 g 3  π2 =π1 Q3 Finite Automata 51 Chapter 2 Sol: By state equivalence method:     π0 = (q , q  0 1 2 3, q , q ), (q ) 4   (g 1 ) (g2 )      π1 =(q0 , q1 , q2 ), (q3 ), (q4 )  (g 1 ) (g2 ) (g3 )  { π2 =(q0 , q2 ), (q1 ), (q3 ), (q4 ) } So, q0 = q2 π3 =π2 Finite Automata 52  Chapter 2 Q4 Sol: Remove states q , q , q , q 4 5 6 7 as these are unreachable states. State equivalence method: (q0 , q1 , q2 ), (q3 ) ∏0 =    g1 g 2  Finite Automata 53 Chapter 2 (q , q ), (q2 ), (q3 ) ∏ 1 = 0 1   g 1 g 2 g 3  { ∏2 =(q0 ), (q1 ), (q2 ), (q3 ) } ⇒ q0 ≠ q1 ∏3 =∏2 Minimized Deterministic Finite Automata (DFA) will contain 4 states. Rack Your Brain Given a regular language L, will its minimal DFA unique? Non-Deterministic finite automata (NFA) y In NFA, there can be 0 or 1 or more than one transition for any input symbol from any state. y A NFA is defined as: N = (Q, ∑, δ, q0 ,F ) where δ : Transition function a eg: A A a B i.e. state A on seeing input a, goes to more than one state which is A and B. { } Let Q = A,B and ∑ = a,b { } Finite Automata Q × ∑ → 2Q 54  Chapter 2 A, a φ {A} A, b {B} B, a {A,B} B, b Fig. 2.4 Note: SOLVED EXAMPLES Q1 Sol: L = {a, aa, ab, ……………………..} NFA: a, b q0 a q1 Q2 Sol: L = {a, aa, ba, ab, ……………………..} NFA: a, b a, b q0 a q1 Finite Automata 55 Chapter 2 Q3 Sol: L = {a, aa, ba, aba, ……………………..} NFA: a, b q0 a q1 Q4 Sol: L = {ab, aba, abb, ……………………..} NFA: a, b q0 a q1 b q2 Q5 Sol: L={ab, aab, bab , aba ,..........} NFA: a, b a, b q0 a q1 b q2 Q6 Sol: L = {aabb, aabba, aabbb, ……………………..} NFA: a, b q0 a q1 a q2 b q3 b q4 Finite Automata 56  Chapter 2 Q7 Sol: L = {a, aa, aba, ……………………..} NFA: a, b q0 a a q2 q1 a Q8 Sol: L = {a, b, aa, bb, aba, bab, ……………………..} NFA: a, b q0 a q1 a q2 a, b b b q3 a, b Q9 Sol: L = {ab, ba, aab, abb, ……………………..} NFA: a, b a q1 b q0 q2 b a q3 Finite Automata a, b 57 Chapter 2 Q10 l r Sol: L = {aaaab, baaab, ……………………..} NFA: a, b a, b q1 a, b q2 a, b q3 a, b q4 b q5 q0 Q11 r l Sol: L = {aaaaa, abbbb, ababb, baabab,…………………..} NFA: a, b a a, b a, b q3 a, b q4 a, b q5 q0 q1 q2 Q12 Sol: L = {aa, baa, aba, …………………..} NFA: b b b a q1 a q2 q0 Q13 Sol: L = {aa, aaa, aab, baa, baaa,…………………..} NFA: b b a, b a a q0 q1 q2 Finite Automata 58  Chapter 2 Q14 aaaa, aabb, aaba, abaa,.....................  Sol: L=  baaa,bbbb,......................................... NFA: a, b a, b a, b a, b q0 q1 q2 q3 q4 Q15 Sol: Length of string is atleast 4 meSol: |w| ³ 4. aaaa, aaaab,.......................................... L=  baaa,bbbbb,......................................... NFA: a, b a, b a, b a, b a, b q0 q1 q2 q3 q4 Q16 Sol: Length of string is atmost 4 meSol: |w| £ 4. L = { ∈ , a, b, aa, ab, ba, bb,…………………..} NFA: a, b a, b a, b a, b q0 q1 q2 q3 q4 Note: If the given NFA accept set of all the strings over ∑ = a,b , where { } Case I: Length of the string is exactly n Case II: Length of the string is atleast n Case III: Length of the string is atmost n Finite Automata In all these cases, minimum number of states in NFA = (n+1) states 59 Chapter 2 Q17 Sol: L = {a, b, aaaa, abab, …………………..} NFA: a, b a, b q0 q1 q2 a, b Rack Your Brain Draw NFA with 3 states that accepts the language L = {a” In 21}{ba Imzo,k 20} Previous Years’ Question Let N be an NFA with n states. Let K be the number of states of minimal DFA which is equivalent to N. Which of the following is necessarily True?  (GATE 2018) 1) K ≥ 2n 2) K ≥ n 3) K ≤ n2 4) K ≤ 2n Sol: 4) Rack Your Brain a a q1 q2 q3 a q0 a a q4 q5 Finite Automata a Let L be the language accepted by the above NFA. Construct an NFA that accepts LU {a”). 60  Chapter 2 2.2 COMPARISON OF DFA AND NFA ) ) ) ) Table 2.1 Conversion from NFA to DFA: Procedure: Let N = (Q, ∑ , δ , q0, F) → NFA M = (Q’, ∑ ’, δ ’, q0’, F’) → DFA i) There is no change in the initial state i.e. q0' = q0 ii) Start the construction of δ ' with initial state and continue it for every new state which will come under input column. Terminate this process when no more new state appears in the input column. iii) Every set which contains final state of NFA as subset, will be the final state for corresponding DFA. Note: Q1 Sol: { } L 1 = a, aa, ab,............ NFA: Finite Automata a, b q0 a q1 61 Chapter 2 Transition table for NFA: Corresponding transition Table for DFA obtained from above table: where D = Dead state (Introduced in DFA) DFA: a, b q0 a q1 b D a, b Q2 Sol: Finite Automata 62  Chapter 2 DFA diagram: a a b b q1 a q0 q1 b q1 q2 b q0q1q2 q0 a b a b a q2 Q3 Sol: { L = aa,ba,bab, aab,................ } NFA: a, b q0 a, b q1 a q2 Transition table for NFA: Corresponding transition Table for DFA obtained from above NFA table: Finite Automata Here ‘D’ is dead state. 63 Chapter 2 DFA diagram: a, b a, b a q2 q0 q1 b D a, b Q4 Sol: { L = aaaa, aaab,baab,babb,................} NFA: a, b q0 a q1 a, b q2 a, b q3 Transition table: Corresponding transition table for DFA obtained from above table: Finite Automata 64  Chapter 2 a b a q0 a q0q1 a q0 q1q2 b q0 q2q3 b q0q1q2 q3 b a a b a q0q2 q0q1q3 q0q3 b b a b Q5 Sol:  Since constructing NFA is easy, first Construct NFA where each string contain “101” as a substring NFA: 0, 1 0, 1 q0 1 q1 0 q2 1 q3 Finite Automata 65 Chapter 2 Conversion from NFA to DFA: DFA: 0 1 1 0 1 0 1 0 0 A B C D E F 1 0 1 Minimal DFA: { ∏0 =(A,B, C), (D,E,F) } ∏ 1 ={(A,B), (C), (D,E,F)} ∏2 = {(A), (B), (C), (D,E,F)} ∏3 =∏2 0 1 0, 1 1 0 1 A B C DEF 0 Now, complement the above DFA to get the minimal DFA that accepts all the { } strings over Σ = 0, 1 where each string “do not contain “101” as a substring.” 0 1 0, 1 Finite Automata 1 0 1 A B C DEF 0 66  Chapter 2 2.3 EPSILON NON-DETERMINISTIC FINTE AUTOMATA (Î Î-NFA) Specification of epsilon NFA: y ( ) Epsilon- NFA ∈ − NFA is the NFA which contains ∈ - moves/Null moves. y This automation allows ∈ as possible transition. y ∈ -NFA is defined as 5-tuple: (Q, ∑ , δ , q0, F) Where transition function: δ: {} Q × Σ ∪ ∈ → 2Q Q: finite set of states ∑: finite set of input symbols q0: Initial state F: set of final states Example: {an | n is even or divisible by 3} q0 ∈ ∈ q1 q3 a a a q4 a q2 a q5 ∈ -closure Definitions The ∈ -closure of the state q, is the set that contains q along with all states which can be reached by only getting any number of ∈ from state q. Finite Automata 67 Chapter 2 Rack Your Brain q0   q1 q2 a a  a q5 q3 a q2 a q4 Conversion from ∈ -NFA to NFA y Why need ∈–NFA, when already NFA is present? NFA: Easier to construct ∈–NFA: Even more easier to construct. Procedure: Let N1 = (Q', S', d', q0', F') is the ∈–NFA. N2 = (Q, S, d, q0, F) is the equivalent NFA. i) Initial state: q0 = q0' ii) d Construction: ∀i∈Σ ∀q∈Q δ(q, i) Î-closure [d' (Î-closure(q), i)] = iii) Final state: Find Î-closure of each state, if it contains any of the final state of N1, then those state(s) will be the final state(s) in equivalent NFA N2. SOLVED EXAMPLES Q1 Finite Automata 68  Chapter 2 Sol: ∈–closure (q0) = {q0, q1} ∈–closure (q1) = {q1} ∈* 0 ∈* q0 q0 q0 q0 0 q1 q1 φ ∈* 1 q0 q0 φ 1 ∈* q1 q1 q1 ∈* 0 q1 q1 φ ∈* 1 ∈* q1 q1 q1 q1 ∈ -NFA to NFA Transition table: NFA: 0 1 0, 1 q0 q1 Final states in the NFA: Find the ∈ -closure of each state, if it contains any of the final state, then include this state as part of final states of equivalent NFA. That’s why here q0 and q1 both are final states. Note: Finite Automata 69 Chapter 2 Q2 Sol: ∈ -closure A) = {A, B, D} ∈ -closure B) = {B, D} ∈ -closure C) = {C} ∈ -closure D) = {D} A ∈* 0 ∈* A A A, B, D 0 ∈* B C C D 0 D ∈* D ∈* 1 A A φ B 1 φ D 1 D ∈* D B ∈* 0 ∈* B C C 0 ∈* D D D ∈* 1 B B φ 1 ∈* D D D ∈* 0 C C φ ∈* 1 ∈* C C B B D ∈* 0 ∈* D D D D Finite Automata ∈* 1 ∈* D D D D 70  Chapter 2 ∈ -NFA to NFA: Transition table: NFA: 0,1 0 0,1 0 0,1 A B D 0 1 0 C 1 Q3 Sol: ∈ -closure (q0) = {q0, q1, q2} ∈ -closure (q1) = {q1, q2} ∈ -closure (q2) = {q2} q0 ∈* a ∈* q0 q0 q0 ,q,q 1 2 q1 a φ q2 a φ q0 ∈* b q0 φ b ∈* q1 q1 q1 ,q2 q2 b φ q0 ∈* c q0 φ Finite Automata q1 c φ q2 c q2 ∈* q2 71 Chapter 2 q1 ∈* a q1 φ q2 a φ q1 ∈* b q2 φ b ∈* q1 q1 q1,q2 q1 ∈* c q1 φ q2 c q2 ∈* q2 ∈* a q2 q2 φ ∈* b q2 q2 φ ∈* c ∈* q2 q2 q2 q2 ∈ -NFA to NFA Transition table: NFA: a b c a,b b,c q0 q1 q2 a,b,c Rack Your Brain Is the language preserved in all the steps while eliminating e-transition from a NFA? Finite Automata Note: 72  Chapter 2 Previous Years’ Question Let δ denote the transition function and δ̂ denotes the extended transition function of the ∈ -NFA whose transition table is given below:  (GATE-2017 Set-2) Then ˆδ (q2 , aba) is 1) f { } 2) q0 , q1 , q3 3) {q0 , q1 , q2 } 4) {q0 , q2 , q3 } Sol: 3) Conversion from epislon-NFA to DFA: Let = (Q ', ∑ ', δ ', q'0 ,F ') is the ∈-NFA. N' M = (Q, ∑, δ, q0 ,F) is the equivalent DFA i) Initial State: q0 = ( ) ∈ −closure q0' eg: 0 1 2 q0 ∈ q1 ∈ q2 ∈−closure (q0) = {q0, q1, q2} ii) δ Construction: Finite Automata   Start Constructing δ with initial state and continue for every new state that appears under the input column.   Terminate this process when no new state appears. 73 Chapter 2 iii) Final state: All states in equivalent DFA which contain final state of ∈ -NFA as a subset, is going to be the final state of DFA. SOLVED EXAMPLES Q1 Sol: ∈ – Closure (q0) = {q0,q1} = Initial state of DFA Transition Table for DFA: Every state which contains q1 will be the final state in DFA. DFA: a b q0q1 b q1 a D a,b Finite Automata 74  Chapter 2 Q2 Sol: ∈–closure (q0) = {q0, q1} We can construct the transition table for DFA as: Initial state q0q1 a q0,q1, q2 q0q1 b q1 q0q1q2 a q0 ,q1, q2 q0q1q2 b q1,q2 q1 a q1,q2 q1 b q1 q1q2 a q1,q2 q1q2 b q1,q2 DFA: a a, b q0 q1 a q0 qq b q1q2 1 2 b a Finite Automata q1 b 75 Chapter 2 Here, q0q1q2 and q1q2 are final states in DFA as it contains q2 which is final states for given ∈ -NFA. Note: Q3 Sol: ∈–closure (q0) = {q0, q1, q2} We can construct the transition table for DFA as: Initial state q0q1q2 a q0q1q2 q0q1q2 b q1q2 q0q1q2 c q2 q1q2 a Dead State ‘D’ q1q2 b q1,q2 q1q2 c q2 Finite Automata 76  Chapter 2 q2 a Dead State ‘D’ q2 b Dead State ‘D’ q2 c q2 D a Dead State ‘D’ D b Dead State ‘D’ D c Dead State ‘D’ DFA: c a b c q0q1q2 b q1q2 c q2 a a, b D a, b, c Note: Finite Automata 77 Chapter 2 Previous Years’ Question What is the complement of the language accepted by the NFA shown below? Assume {} Σ = a and ∈ is the empty string.  (GATE-2012) a ∈ ∈ 1) φ 2) {∈} 3) a* 4) {a,∈} Sol: 2) Note: 2.4 FINITE TRSol:DUCER Definitions Finite state trSol:ducer is a finite state automaton which produces output on reading any input. y  finite state trSol:ducer (FST) can be thought of as trSol:lator or relator A between strings in a set. y It is very useful in parsing. Moore machines Definitions Finite Automata Moore Machines are finite state machines with output value associated with states. 78  Chapter 2 It can be defined as – (Q, Σ, δ, q0 , ∆, λ ) where Q: Finite set of states Σ: Input alphabets δ: Transition function Q×Σ → Q q0 Initial state ∆: output alphabets λ : output function which maps Q → ∆ eg: a b q0, 1 b q1, 0 a Input: ab a b q0 q0 q1 1 1 0 Note: SOLVED EXAMPLES Q1 Sol: Whenever see ‘ab’ print ‘1’ as output Finite Automata =Σ {a,b= } ∆ {0, 1} 79 Chapter 2 b a a b A, 0 B, 0 C, 1 a b Take example and verify it: Input1: ab a b A B C 0 0 1 (Output) Input2: abab a b a b A B C B C 0 0 1 0 1 Q2 Sol: ∑ ={a,b} Take D = {0, 1} a b A, 0 b B, 0 a C, 0 a D, 1 b b a Take example and verify it Input: abaa A a A b B a C a D 0 0 0 0 1 Finite Automata 80  Chapter 2 Q3 Sol: ∑ ={0, 1} ∆ = {A, B, C} 0 1 1 1 q0, C q1, C q2,B 0 1 0 0 q3,A Take example and verify it: 1 1 Input 1: 11 q0 q1 q2 C C B 1 1 0 Input 2: 110 q0 q1 q2 q3 C C B A Q4 0 Sol: ∑ ={0, 1} Remainder: Binary number %3 1 2 ∆ ={0, 1, 2} Represents states equal to the number of remainders when any binary number Finite Automata divisible by 3 81 Chapter 2 0 0 1 1 0 q0, 0 q1, 1 q2,2 1 Rack Your Brain Construct a moore machine that takes base 4 numbers as input and produces ‘reakdus modulo 6 output? Mealy machine: Definitions Mealy machines are finite state machines, where output depends upon the present input symbol and present state of the machine. y ( It can be defined as: Q, Σ, δ, q0 , ∆, λ , ) where Q: Finite set of states Σ : Input alphabets δ : Transition function Q×Σ → Q q0 : Initial state ∆ : Output alphabet l: Output function Q × ∑ → ∆ a/1 b/0 b/0 eg: q0 q1 a/1 Input: ab a b q1 q0 q0 Finite Automata 1 0 (output) 82  Chapter 2 Note: SOLVED EXAMPLES Sol: ∑ ={0, 1} { } ∆ = 0, 1 To calculate: 2’s complement of binary number 1011 1’s complement of this number = 0100 0 100 2’s complement of this number = +1 0 10 1 Observation: From LSB whenever you see 0, leave it as it is, whenever you see 1st 1, leave as it is. After this, whatever digits come, just complement it, will give 2’s complement 0/0 0/1 1/1 q1 q0 1/0 Rack Your Brain Construct a mealy machine that takes binary umber as input and produces 1’s complement of that number as output Finite Automata 83 Chapter 2 Previous Years’ Question The finite state machine described by the following state diagram with A as starting state, where an arc label is x/y and x stands for 1-bit input and y stands for 2-bit output (GATE-CS-2002) 1) Outputs the sum of the present and the previous bits of the input. 2) Outputs 01 whenever the input sequence contains 11 3) Outputs 00 whenever the input sequence contains 10 4) None of the above Sol: 1) Rack Your Brain Construct a mealy machine that takes binary umber as input and produces output = (input)2 mod 3. Conversion of Moore machine to Mealy machine SOLVED EXAMPLES Q1 Sol:  We have to construct a Moore machine which counts the number of a’s is divisible by 3. b b b a a Finite Automata q0, 0 q1 , 1 q 2, 2 a 84  Chapter 2 When convert moore to mealy, then q0 state on input a goes to q1 states and output associated with state q1 is 1 so, it will go onto the transition in equivalent mealy machine. Apply similar concepts for every state. Transition: Diagram for mealy machine: b/0 b/1 b/2 a/1 a/2 q0 q1 q2 a/0 Rack Your Brain Convert the following given Moore machine to Mealy machine: y x x y q0 , 0 q1, 0 q 2, 1 x y Finite Automata 85 Chapter 2 Conversion from mealy to moore machine: SOLVED EXAMPLES Q1 Sol: i)  State q1 on getting input 0 goes to state q2 and the output present in this transition gets associated with states q2 in the corresponding equivalent moore machine. ii) State q1 on getting input 1 goes to state q3 and the output present in this transition i.e. ‘z1’ gets associated with state q3 in the corresponding equivalent moore machine. iii) We will follow this above procedure for other states as well as the new states we are getting. Finite Automata 86  Chapter 2 Rack Your Brain Convert the following given M Mealy m machine to equivalent Mooremmachine. x/1 x/1 y/1 y/0 x/1, y/1 x/0 A B C D y/1 Finite Automata 87 Chapter 2 Chapter Summary y Finite Automata: Finite automata is a mathematical model which involves states an