Finite automata

FA, TYPES OF FA, EXAMPLES, DFA, NDFA / NFA, EXAMPLES.

1. Finite Automata by Manish Tadhiyal

2. Content Finite automata Types of finite automata Finite state diagram Deterministic finite automata(DFA) Example of DFA Non-deterministic finite automata(NFA) Example of NFA

3. Finite Automata A finite automata (FA) is a simple idealized machine used to recognize patterns within input taken from some character set (or alphabet) C. the job of an FA is to accept or reject a input depending on whether the pattern defined by the FA occurs in the input.

4. Types of finite automata Finite automata without output Deterministic finite automata Non-deterministic finite automata Finite automata with output Mealy machine Moore machine

5. Finite State Diagram A graphic representation of a finite automata A finite state diagram is a directed graph, where nodes represent elements in Q (i.e., states) and arrows are characters in  such that: q a q b Indicates: transmission between q a to q b with a. The initial state is marked with: > The final state(s) are marked with: a

6. Deterministic finite automata For each pair of states and possible input chars, there is a unique next state (as specified by the transitions), then the FA is deterministic finite automata. T hat means the DFA follow single path with single transmission.

7. Deterministic finite automata Q :Finite set of states S: Finite Alphabet d : Transition function - a total function from Q x S to Q q :Initial/Start State F :Set of final/accepting state

8. Example Set of strings over { a,b } that contain “ bb” q2 q0 q1 a b a b a b d a b q0 q0 q1 q1 q0 q2 q2 q2 q2

9. Another Example Build a FA to accept strings of even length q 1 a,b a,b q

10. Non-Deterministic finite automata For each pair of states and possible input chars, there may be more then one next state (as specified by the transitions), then the FA is non-deterministic finite automata. Conceptually, a nondeterministic FA can follow many paths simultaneously.

11. Non-deterministic finite automata (NDFA) or (NFA) M = (Q, , , s, F) where Q= Finite set of states = Input alphabet  = Q x  2^Q s = Initial state F = Final state

12. Difference between DFA and NFA q i q j q k q q i q j a a a DFA NFA a

13. String having alphabet =( a,b ) String accept language start with a and end with a. q q f q 1 a b a b a b q 2

14. Another Example Build a FA to accept strings of even length q q 1 q 2 a,b a,b

15. THANK YOU