CT_Sec_1.pptxfyocyococoycxoycyocycoyxykx6x

Yitix

1. Section 1 Deterministic Finite Automata (DFA) 1

2. Th e o r y o f C o m pu t a t i o n We use these methods to recognize regular languages 2 Languages Regular Languages Deterministic Finite Automata (DFA)

3. Automata The term "Automata" is derived from the Greek word "α ὐτόμ ατα" which means "self-acting“ An automaton is an abstract self-propelled computing device which follows a predetermined sequence of operations automatically. An automaton with a finite number of states is called a  Finite Automaton  (FA) or  Finite State Machine  (FSM).

4. Formal definition of a Finite Automaton An automaton can be represented by a 5-tuple (Q, ∑, δ, q , F), where

5. Related Terminologies Alphabet String

6. Length of a String Kleene Star

7. Kleene Closure / Plus Language

8. Wh a t i s a L a ngu a g e ? A language is a set of strings over For example, alphabet {0, 1} a n alphabet. Language Language Language Language L1 L2 L3 L4 = = = = {1, 0, 11, 00} {01, 111, 000} {ε} the empty string "epsilon” ∅ , t h e e m p t y l a n g u a g e , with no strings 3

9. Wh a t i s a R e gu l a r Language? Regular language is one that can be recognized by a Deterministic Finite Automata (DFA), or Non-Deterministic Finite Automat (NFA), or Regular Expressions (Regex). For example: L1={strings end with 1}, e.g. {01, 11, 10101, 100001, L2= {strings start and end with 0}, e.g. {0, 00, 010, 011110, L3= {strings have even number of 1’s}, e.g. {11, 101, 1010, 1111,... } …} …} 4

10. Deterministic Finite Automata (DFA) What is the formal description of M1? Example 1: M1 This DFA is a 5-tuple: (Q, Σ , δ , q , F) Q = set of states = {q0, q1} Σ “sigma” = alphabet set = {0, 1 } δ = t r a ns i t i o n f un c t i o n = state q = first state = q0 F = set of final states = {q1}. 5 diagram / table

11. Deterministic F in i t e A u t o m a t a ( D F A ) Example 1: M1 d = transition function State Diagram (figure) Transition Table 6 1 q0 q0 q1 * q1 q0 q1

12. Deterministic Finite Automata (DFA) Transition Table What is the language recognized/accepted by M1? e.g {01, 011, 0101, 01011, 1, 11, 101, 1001…} L1 = {over (0, 1)|strings that end with 1} 7 1 q0 q0 q1 * q1 q0 q1

13. M o r e examples of DFA Example2: M2 W h a t M2? is the language recognized by 1 1 q q 1 State Diagram for M 2 3

14. Machine Input string: ε 2 Example2: M2 What is M2? the language recognized by 1 1 e.g. {ε, q q 1 State Diagram for M 2 4

15. C h e c k i n g s o m e a cc e p t e d s t r i n g s Example2: M2 What is the M2? language recognized by 1 1 e.g. {ε, 0, q q 1 State Diagram for M 2 5 Input string:

16. C h e c k i n g s o m e a cc e p t e d s t r i n g s What is the language M2? recognized by 1 1 e.g. {ε, 0, 00, q q 1 State Diagram for M 2 6 Input string: 00

17. C h e c k i n g s o m e a cc e p t e d s t r i n g s Input string: 1 What is the language M2? recognized by 1 1 e.g. {ε, 0, 00, q q 1 State Diagram for M 2 7

18. Machine Input string: 10 2 Example2: M 2 What is the language M 2 ? e.g {ε, 0, 00, 10, …} recognized by 1 1 q q 1 L(M 2 ) = { over (0, 1) | strings that end with or ε, empty string} State Diagram for M 2 8