CSE-3201-Lecture-06-Lexical Analysis-NFA and DFA.pptx

Lexical Analysis-NFA and DFA

1. Lecture-06 Lexical Analysis (NFA and DFA) Mostafiz Ahammed Lecturer Department of Computer Science and Engineering Notre Dame University Bangladesh

2. Finite State Automata (FSAs) “Finite State Machines”, “Finite Automata”, “FA” A recognizer for a language is a program that takes as input a string x and answers “yes” if x is a sentence of the language and “no” otherwise. The regular expression is compiled into a recognizer by constructing a generalized transition diagram called a finite automaton. One start state Many final states Each state is labeled with a state name Directed edges, labeled with symbols Two types Deterministic (DFA) Non-deterministic (NFA)

3. Nondeterministic Finite Automata A nondeterministic finite automaton (NFA) is a mathematical model that consists of A set of states S A set of input symbols  A transition function that maps state/symbol pairs to a set of states A special state s called the start state A set of states F (subset of S) of final states INPUT: string OUTPUT: yes or no

4. Example – NFA : (a|b)*abb S = { 0, 1, 2, 3 } s = F = { 3 }  = { a, b } start 3 b 2 1 b a a b a b { 0, 1 } { } 1 -- { 2 } 2 -- { 3 } s t a t e i n p u t  (null) moves possible i j  Switch state but do not use any input symbol Transition Table

5. How Does An NFA Work ? start 1 b 2 b 3 a a b Given an input string, we trace moves If no more input & in final state, ACCEPT EXAMPLE: Input: ababb move (0, a) = 1 move (1, b) = 2 move (2, a) = ? (undefined) REJECT ! move (0, a) = move (0, b) = move (0, a) = 1 move (1, b) = 2 move (2, b) = 3 ACCEPT ! - O R -

6. Handling Undefined Transitions We can handle undefined transitions by defining one more state, a “death” state, and transitioning all previously undefined transition to this death state. st a rt 3 b 2 1 b a a b a a a, b 4 

7. Other Concepts st a rt 3 a 1 b 2 b Not all paths may result in acceptance. a b aabb is accepted along path : 0   1  2  3 BUT… it is not accepted along the valid path:    

8. Deterministic Finite Automata A DFA is an NFA with the following restrictions:  moves are not allowed For every state s  S, there is one and only one path from s for every input symbol a   . Since transition tables don’t have any alternative options, DFAs are easily simulated via an algorithm .

9. Example – DFA : (a|b)*abb st a rt 3 b 2 1 b a b start 3 b 2 1 b a b a b a a What Language is Accepted? Recall the original NFA: a

10. Relation between RE, NFA and DFA There is an algorithm for converting any RE into an NFA. There is an algorithm for converting any NFA to a DFA. There is an algorithm for converting any DFA to a RE. These facts tell us that REs, NFAs and DFAs have equivalent expressive power. All three describe the class of regular languages.

11. DFA vs NFA Both DFA and NFA are the recognizers of regular sets. But – time-space trade space exists DFAs are faster recognizers – Can be much bigger too..

12. Converting Regular Expressions to NFAs Thompson’s Construction Empty string  is a regular expression denoting {  } a is a regular expression denoting { a } for any a in   i f st art i a f st art

13. Converting Regular Expressions to NFAs If P and Q are regular expressions with NFAs N p , N q : P | Q (union) PQ (concatenation) N p N q i f     st a rt N q N p i f s t art

14. Converting Regular Expressions to NFAs If Q is a regular expression with NFA N q : Q* (closure)  N q f  i st a rt  

15. Example (ab* | a*b)* Starting with: 4 b 3 a*b a st a rt ab* 1 2 a b st a rt 1 a 2 4 3 6 ab* | a*b 5     a b b st a rt

16. Example (ab* | a*b)* 1 a 2 4 3 6 ab* | a*b 5     a b b st a rt 1 2 a 4 5 6 (ab* | a*b)* 8   7       b b 3 a st a rt

17. Properties of Construction Let r be a regular expression, with NFA N(r), then N(r) has #of states  2*(#symbols + #operators) of r N(r) has exactly one start and one accepting state Each state of N(r) has at most one outgoing edge a  or at most two outgoing  -transition

18. Detailed Example r 12 r 5 r 3 r 11 r 4 r 9 r 10 r 8 r 7 r 6 r r 1 r 2 (ab*c) | (a(b|c*)) Parse Tree for this regular expression: r 13 b * c a a | ( ) b | * c What is the NFA? Let’s construct it !

19. Detailed Example – Construction(1) r 3 : a r : b r 2 : c    b  r 1 : r 4 : r 1 r 2    b  c r 5 : r 3 r 4    b  a c (ab*c) | (a(b|c*))

20. Detailed Example – Construction(2) r 11 : a r 7 : b r 6 : c    c  r 9 : r 7 | r 8   b r 10 : r 9    c (ab*c) | (a(b|c*))  r 8 :    c  r 12 : r 11 r 10   b a    

21. Detailed Example – Final Step b   r 13 : r 5 | r 12   a c c       b a     1 6 5 4 3 8 2 10 9 12 13 14 11 15 7 16 17  