Finite state machine without output

Best Of Luck

1. Finite State Machine Without Output Name: Tayyab Aman Roll No.: 19014156-018 Instructor: Mr.Shahbaz Ayyaz

2. History & Introduction The two neurophysiologists  Warren McCulloch  and  Walter Pitts  were the first to present a description of finite automata in 1943 . Their research paper, entitled, “A Logical Calculus Immanent in Nervous Activity”, made significant contributions to the study of theory of automata, the theory of computation and cybernetics.  An automaton in which the state set {Q} contains only a finite number of elements is called a finite-state machine (FSM) , it is famous name is Finite Automata (FA ). FSMs are conceived as an abstract machine that can be in one of a finite number of states .  FSMs Input Language Output

3. Types Of FSMs Without Output With Output Mealy * Note:: DFM & Non-DFM Give answer in Yes/No.

4. Deterministic Finite-State Machine A finite-state machine M is defined by Five-tuple are as follows ; M = (Q, Σ, δ,q ,F) Q: It represents the non-empty set of finite states . Σ: It presents the non-empty finite set of the input alphabet. δ : It represents the state transition function . Q × Σ  → Q is the next-state function q : It is the initial state. F: It is the set of final states (F ⊆ Q). Initial State Final State 1     0,1

5. Deterministic Finite Automata There is a unique or single move from one state to another with same input Symbol. DFM is a simplest model of computation. Example:         1 1 1 1 Q ={ , , , } Σ={0,1} Initial State F= { δ = Transition Table (State , Input)         1  

6. Example Acceptance of a string by DFA : A String w is accepted by DFA If δ( for some q є F. L =set of all strings starts with a. L={a,ab,aab,abb,aa,aba,……..} Let String =abb Because we start with initial state & end in final state ,so string is present.         a b a ,b a ,b Scanning the string ,a) Then ( ) Then ( ) Then  

7. Example Construct a DFA to accept the string 0,1 which contain Even number of 1’s- Solution L={0,11,011,110,1111,………} 1) 2) 3) 4) 5)       1     1     1 1       1 1 Transition Table 1 1  

8. Example Design a DFA which accept set of all strings over {a,b} which starts with ab- Solution In order to check starting string we add an extra state which is called Dead state. Total No. of states=Length of a smallest string+ 1 + 1 = 4 2         a b b a,b a a,b Dead State a b a b Q={ , } Σ ={a,b}  

9. Example Construct a DFA which accept set of all strings over {0,1} which interpreted as binary number divisible by 2- Solution: When we divide any number by 2 we get 2 remainders ( 0,1 ) = State with 0 remainder = State with 1 remainder       1 1 1 1 Examples:( = 3  

10. Nondeterministic Finite Automata(NFA) In NFA Or NDFA , we may lead to more than one states for a given inputs. An NFA for a language can be smaller & easier to construct than a DFA . We need to convert NFA to DFA for designing a compiler. Every DFA is NFA , but every NFA is not DFA. It is also a 5-tuple Machine. M = (Q, Σ, δ,q ,F) But in NDFM , δ :Q x Σ  P(Q) is a function called as transition function.     є       a a

11. Example Design a NFA over an alphabet {0,1} such that every string accept must start with 0- Solution: NFA DFA     0,1       0,1 0,1 1 ∅ 1 ∅ 1 1

12. Conversion NDFA To DFA Step 1:  Initially Q' = ϕ Step 2:  Add q0 of NFA to Q'. Then find the transitions from this start state. Step 3:  In Q', find the possible set of states for each input symbol. If this set of states is not in Q', then add it to Q'. Step 4:  In DFA, the final state will be all the states which contain F(final states of NFA)

13. Example convert NDFA To DFA State 1 →q0 {q0, q1} {q1} q1 ϕ {q0, q1} Now we will obtain δ' transition for state q0 . δ'([ q0], 0) = {q0, q1}                  = [q0, q1]       ( new  state generated)   δ'([ q0], 1) = {q1} = [q1 ] The δ' transition for state q1 is obtained as: δ'([ q1], 0) =  ϕ   δ'([ q1], 1) = [q0, q1]   Now we will obtain δ' transition on [q0, q1]. δ'([ q0, q1], 0) =  δ( q0, 0) ∪  δ( q1, 0)                         = {q0, q1} ∪  ϕ                         = { q0, q1}                         = [q0, q1]   Similarly, δ'([ q0, q1], 1) =  δ( q0, 1) ∪  δ( q1, 1)                         = {q1} ∪ {q0, q1}                         = {q0, q1}                         = [q0, q1]  As in the given NFA, q1 is a final state, then in DFA wherever, q1 exists that state becomes a final state. Hence in the DFA, final states are [q1] and [q0, q1]. Therefore set of final states F = {[q1], [q0, q1]}. 

14. Cont.…. State 1 →[q0] [q0, q1] [q1] *[q1] ϕ [q0, q1] *[q0, q1] [q0, q1] [q0, q1] Suppose A  = [q0]   B = [q1]   C = [q0, q1] With these new names the DFA will be as follows: 0,

15. Applications FSMs are used in games; they are most recognized for being utilized in  artificial intelligence , and however, they are also frequent in executions of navigating parsing text, input handling of the customer, as well as network protocols . The finite state machines are applicable in vending machines, video games, traffic lights,  controllers  in CPU, text parsing, analysis of protocol,  recognition of speech , language processing, etc . These are restricted in computational power; they have the good quality of being comparatively simple to recognize. So, they are frequently used by software developers as well as system designers for summarizing the performance of a difficult system.

16. References https:// www.elprocus.com/finite-state-machine . https:// www.javatpoint.com/automata-conversion-from-nfa-to-dfa https:// www.youtube.com/c/ashakhilrani https:// www.youtube.com/watch?v=Qa6csfkK7_I