Question? Leave a message!




Finite Automata

Finite Automata
Dr.SamuelHunt Profile Pic
Dr.SamuelHunt,United Arab Emirates,Teacher
Published Date:21-07-2017
Website URL
Comment
Finite AutomataOutline • Deterministic finite automata (DFA) – How a DFA works – How to construct a DFA • Non-deterministic finite automata (NFA) – How an NFA works – How to construct an NFA • Equivalence of DFA and NFA • Closure properties of the class of languages accepted by FA Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 2Finite Automata (FA) Finite set of states is in exactly one state at a time CONTROL Start state UNIT Final state(s) TAPE Move to the right one cell HEAD at a time INPUT TAPE Store input of the DFA Can be of any length Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 3What does an FA do? • Read an input string from tape • Determine if the input string is in a language • Determine if the answer for the problem is “YES” or “NO” for the given input on the tape Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 4How does an FA work? • At the beginning, – an FA is in the start state (initial state) – its tape head points at the first cell • For each move, FA – reads the symbol under its tape head – changes its state (according to the transition function) to the next state determined by the symbol read from the tape and its current state – move its tape head to the right one cell Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 5When does an FA stop working? • When it reads all symbols on the tape • Then, it gives an answer if the input is in the specific language: – Answer “YES” if its last state is a final state – Answer “NO” if its last state is not a final state Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 6Example of a DFA 0 1 q a(q,a) 0 s s 0 s f s 1 f 1 Transition diagram f 0 f f 1 s Transition function Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 7How to define a DFA • a 5-tuple (Q, , , s, F), where That’s why it’s called a finite automaton. – a set of states Q is a finite set – an alphabet  is a finite, non-empty set – a start state s in Q – a set of final states F contained in Q – a transition function  is a function Q  Q • See formal definition Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 8How an FA works 0 1 0 s f 1 Input: 001101 ACCEPT 0 0 1 1 0 1 REJECT Input: 01001 0 1 0 0 1 Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 9Configurations Definition Let M =(Q, , , s, F ) be a deterministic finite automaton.  A configuration of M is an element of Q   Current state Unread input string 0 1 0 configurations of M (s, ), (s, 00), s f (s, 01101), (f, ), 1 (f, 0011011001), (f, 1111), (f, 011110) Transition diagram of M Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 10Yielding next configuration Definition • Let M = (Q, , , s, F ) be a deterministic finite automaton, and (q ,  ) and (q ,  ) be two configurations of M. 0 0 1 1 • We say (q ,  ) yields (q ,  ) in one step, denoted by (q ,  ) 0 0 1 1 0 0  (q ,  ), if (q , a) = q , and  =a  , for some a . M 1 1 0 1 0 1 • When a configuration yields another configuration, the first symbol of the string is read and discarded from the configuration. • Once a symbol in an input string is read, it does not effect how the DFA works in the future. Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 11Example: yielding next configuration 0 1 0 (s, 001101)  (s, 01101) M s f  (s, 1101) M  (f, 101) M 1  (s, 01) M  (s, 1) M 0 0 1 1 0 1  (f, ) M Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 12Yield in zero step or more Definition • Let M = (Q, , , s, F) be a DFA, and (q ,  ) and 0 0 (q ,  ) be two configurations of M. (q ,  ) yields 1 1 0 0 (q ,  ) in zero step or more, denoted by (q ,  ) 1 1 0 0  (q ,  ), if M 1 1 – q = q and  =  , or 0 1 0 1 – (q ,  )  (q ,  ) and (q ,  )  (q ,  ) for 0 0 M 2 2 2 2 M 1 1 some q and  . 2 2 This definition is an inductive definition, and it is often used to prove properties of DFA’s. Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 13Example: Yield in zero step or more 0 1 0 s f 1 (s, 01001) (s, 001101)  (f, 001)  (f, 101) M M  (f, 001)  (s, 01) M M  (f, 1) M  (f, ) M  (s, ) M  (f, ) M Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 14Accepting a string Definition • Let M = (Q, , , s, F) be a DFA, and   . We say M accepts  if (s, )  (f, ), when f M  F. Otherwise, we say M rejects . (s, 001101)  (f, )  M accepts 001101 M (s, 01001)  (s, )  M rejects 01001 M Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 15Language accepted by a DFA Let M = (Q, , , s, F ) be a DFA. The language accepted by M, denoted by L(M ) is the set of strings accepted by M. That is, L(M) = (s, )  (f, ) for some f  F M Example: • L(M) = x 0,1 the number of 1’s in x is odd. 0 1 0 s f 1 Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 16Example 0 0, 1 0 0 1 1 0 s 0 1 1 0, 1 1 1 1 0 0 Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 17How to construct a DFA • Determine what a DFA need to memorize in order to recognize strings in the language. – Hint: the property of the strings in the language • Determine how many states are required to memorize what we want. – final state(s) memorizes the property of the strings in the language. • Find out how the thing we memorize is changed once the next input symbol is read. – From this change, we get the transition function. Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 18Constructing a DFA: Example • Consider L= 0,1 has both 00 and 11 as substrings. • Step 1: decide what a DFA need to memorize • Step 2: how many states do we need? • Step 3: construct the transition diagram Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 19Example Got 00 Got 00 and 11 Got 00 as and got 1 as substrings substring 0 0, 1 0 Got 0 as substring 0 1 1 0 s 0 1 1 0, 1 1 1 Got nothing 1 0 0 Got 1 as substring Got 11 as Got 11 Got 11 and 00 substring and got 0 as substrings Jaruloj Chongstitvatana 2301379 Chapter 2 Finite Automata 20