advertisement

advertisement

Information about Cs419 lec6 lexical analysis using nfa

advertisement

Dr. Hussien M. Sharaf NON DETERMINISTIC FINITE AUTOMATA NFA There is a fixed number of states but we can be in multiple states at one time. NFA = “a 5-tuple “ (Q, Σ, , q0, F) Q A finite set of states Σ A finite input alphabet q0 The initial/starting state, q0 is in Q F A set of final/accepting states, which is a subset of Q δ A transition function, which is a total function from Q x Σ to 2Q , this function: Takes a state and input symbol as arguments. Returns a set of states instead a single state as in DFA. δ: (Q x Σ) –> 2Q -2Q is the power set of Q, the set of all subsets of Q δ(q,s) is a function from Q x S to 2Q (but not to Q) 2

NFA A finite automaton is deterministic if It has no edges/transitions labeled with epsilon/lamda. For each state and for each symbol in the alphabet, there is exactly one edge labeled with that symbol.

Dr. Hussien M. Sharaf NFA NFA travels all possible paths, and so it remains in many states at once. As long as at least one of the paths results in an accepting state, the NFA accepts the input. Alphabet = {a } a q0 q1 a q2 a q3 4

Dr. Hussien M. Sharaf NFA Alphabet = {a } Two choices a q0 q1 a q2 a q3 5

Dr. Hussien M. Sharaf NFA Alphabet = {a } Two choices a q0 q1 a q2 No transition a q3 No transition 6

Dr. Hussien M. Sharaf NFA An NFA accepts a string: if there is a computation of the NFA that accepts the string i.e., all the input string is processed and the automaton is in an accepting state 7

Dr. Hussien M. Sharaf Acceptance Example 1 NFA a a a q0 q1 a q2 a q3 8

Dr. Hussien M. Sharaf First Choice NFA a a a q0 q1 a q2 a q3 9

Dr. Hussien M. Sharaf First Choice NFA a a All input is consumed a q0 q1 a q3 a q2 “accept”

Dr. Hussien M. Sharaf Second Choice NFA a a a q0 q1 a q3 a q2

Dr. Hussien M. Sharaf Second Choice NFA a a Input cannot be consumed a q1 a q2 Automaton Halts q0 a q 3 “reject”

Dr. Hussien M. Sharaf NFA aa is accepted by the NFA: “accept” a q0 q1 q2 a q0 a q3 because this computation accepts aa a q1 a q2 a q3 “reject” this computation is ignored 13

Dr. Hussien M. Sharaf NFA An NFA rejects a string: if there is no computation of the NFA that accepts the string. For each computation: • All the input is consumed and the automaton is in a non final state OR • The input cannot be consumed 14

Dr. Hussien M. Sharaf NFA a is rejected by the NFA: “reject” a q0 q1 a q2 a q0 a q 3 “reject” q1 a q2 a q3 All possible computations lead to rejection 15

Dr. Hussien M. Sharaf NFA aaa is rejected by the NFA: “reject” a q0 q1 a q2 a q0 a q3 q1 a q2 a q3 “reject” All possible computations lead to rejection 16

Dr. Hussien M. Sharaf LAMBDA TRANSITIONS q0 a q1 q2 a q3 17

Dr. Hussien M. Sharaf LAMBDA TRANSITIONS Acceptance Example 2 a a q0 a q1 q2 a q3 18

Dr. Hussien M. Sharaf LAMBDA TRANSITIONS a a q0 a q1 q2 a q3 19

Dr. Hussien M. Sharaf LAMBDA TRANSITIONS input tape head does not move a a q0 a q1 q2 a q3

Dr. Hussien M. Sharaf LAMBDA TRANSITIONS all input is consumed a a “accept” q0 a q1 q2 a q3 String aa is accepted 21

Dr. Hussien M. Sharaf LAMBDA TRANSITIONS Rejection Example 3 a a a q0 a q1 q2 a q3 22

Dr. Hussien M. Sharaf LAMBDA TRANSITIONS a a a q0 a q1 q2 a q3 23

Dr. Hussien M. Sharaf LAMBDA TRANSITIONS (read head doesn’t move) a a a q0 a q1 q2 a q3 24

Dr. Hussien M. Sharaf LAMBDA TRANSITIONS Input cannot be consumed a a a Automaton halts “reject” q0 a q1 q2 a q3 String aaa is rejected 25

Dr. Hussien M. Sharaf LAMBDA TRANSITIONS Language accepted: q0 a q1 L {aa } q2 a q3 26

Dr. Hussien M. Sharaf Example 4 q0 a b q1 q2 q3 27

Dr. Hussien M. Sharaf a b q0 a b q1 q2 q3 28

Dr. Hussien M. Sharaf a b q0 a b q1 q2 q3 29

Dr. Hussien M. Sharaf a b “accept” q0 a b q1 q2 q3 30

Dr. Hussien M. Sharaf Another String a b a b q0 a b q1 q2 q3 31

Dr. Hussien M. Sharaf a b a b q0 a b q1 q2 q3 32

Dr. Hussien M. Sharaf a b a b q0 a b q1 q2 q3 33

Dr. Hussien M. Sharaf a b a b q0 a b q1 q2 q3 34

Dr. Hussien M. Sharaf a b a b q0 a b q1 q2 q3 35

Dr. Hussien M. Sharaf a b a b q0 a b q1 q2 q3 36

Dr. Hussien M. Sharaf a b a b “accept” q0 a b q1 q2 q3 37

Dr. Hussien M. Sharaf Language accepted L ab , abab , ababab , ... ab q0 a b q1 q2 q3 38

Dr. Hussien M. Sharaf EXAMPLE 5 0 q0 1 q1 0, 1 q2 39

Dr. Hussien M. Sharaf Language accepted L ( M ) = {λ , 10 , 1010 , 101010 , ... } = {10 } * 0 q0 1 q1 0, 1 q2 (redundant state) 40

DETERMINISTIC AND NONDETERMINISTIC AUTOMATA Deterministic Finite Automata (DFA) One transition per input per state No -moves Nondeterministic Finite Automata (NFA) Can have multiple transitions for one input in a given state Can have -moves 41

THANK YOU Dr. Hussien M. Sharaf 42

Lexical Analysis. Articles, experts, jobs, and more: get all the professional insights you need on LinkedIn. Sign up Get more personalized results when you ...

Read more

View 10617 Nfa posts, presentations, experts, and more. Get the professional knowledge you need on LinkedIn. LinkedIn Home What is LinkedIn? Join Today

Read more

Lexical Analysis - Part 3 © Harry H. Porter, 2005 Converting an NFA to a DFA Given: A non-deterministic finite state machine (NFA) Goal:

Read more

Scanner Generator. Regular Expressions to NFA, ... A scanner generator builds lexical analyzers from token ... Lexical analyzers perform lexical analysis.

Read more

CS421 COMPILERS AND INTERPRETERS ... • The lexical structure is specified using regular ... Yale University Lexical Analysis : Page 23 of 40 NFA -> DFA

Read more

Compiler Construction/Lexical analysis. From Wikibooks, ... Since, however, this section is about using JavaCC to generate a token manager, ...

Read more

... Yale University Lexical Analysis : Page 9 of 40 Lexical ... • Finite Automata can also be represented using transition tables For NFA, each entry ...

Read more

## Add a comment