CPSC 323: Lexical Analysis(DFA)

2.1-2.7

Tasks of a Lexer

• Tokenizing source, i.e. breaking up the source code into meaningful units called Tokens.

• Removing (overpass) comments

• Case conversion

• Dealing with pragmas (i.e., significant comments)

• Saving source locations (file, line, column) for error

messages

Token vs. Lexeme

• Token is a generic type of a meaningful unit

• Lexeme is the actual instance

• Ex. the source code is if (a > b) then

Finite State Machine(FSM)

• A computational model used to design systems with a limited number of distinct states.

• Tokens are represented by regular expressions which are represented by FSM

• 2 types

  • Deterministic Finite State Machine (DFSM) or

    Deterministic Finite Automaton (DFA)

  • Nondeterministic Finite State Machine (NFSM) or

    Nondeterministic Finite State Automaton (NFA)

• The set of all DFSMs = the set of all NFSMs

Components of a FSM

• States: Different conditions or modes of the system.

• Transitions: Rules that move the system from one state to

another based on input.

• Input: External signals or events that affect transitions.

• Output: Actions or responses triggered by state changes (in

some FSMs)

Uses for a FSM

Modeling traffic lights, vending machines, user authentication flows.

Basic steps in a FSM

• The system starts in an initial state.

• When an input/event occurs, transitions to a new state according to its transition rules.

• Output may be generated depending on the type.

• Visualization: States as circles, transitions as arrows with input labels.

Deterministic Finite State Machines (DFSM)

• No state has more than one outgoing edge with the same label. Each state has 1 transition for each input symbol

• No ambiguity in transitions.

• For a given state and input, the next state is uniquely determined.

• All FSMs we've studied earlier (basic examples) are DFSMs.

• Example Use Case: Simple vending machine that responds deterministically to coin inputs.

Non-deterministic Finite State Machines (NFSM)

• States may have more than one outgoing edge with same label.

• Edges may be labeled with ε (epsilon), the empty string. [Note that some books use the Machines symbol λ.]

• The automaton can make an ε epsilon transition without consuming the current input character.

Finite State Machine Diagram Notation

Transitions

EX: s1 (a)- > s2

• Is read In state s1 on input “a” go to state s2

• If end of input

– If in accepting state => accept

– Otherwise => reject

• If no transition possible (got stuck) => reject

Toll Gate example

• Consider the problem of designing a “computer” that controls a toll gate

• When a car arrives at the toll gate, the gate is closed. The gate opens as soon as the driver has payed 25 cents.

• We assume that we have only three coin denominations: 5, 10, and 25 cents. We also assume that no excess

change is returned.

• After having arrived at the toll gate, the driver inserts a sequence of coins into the machine. At any moment, the machine has to decide whether or not to open the gate, i.e., whether or not the driver has paid 25 cents (or

more).

• In order to decide this, the machine is in one of the following six states, at any moment during the process:

• The machine is in state q0, if it has not collected any money yet.

• The machine is in state q1, if it has collected exactly 5 cents.

• The machine is in state q2, if it has collected exactly 10 (=2x5) cents.

• The machine is in state q3, if it has collected exactly 15(=3x5) cents.

• The machine is in state q4, if it has collected exactly 20(=4x5) cents.

• The machine is in state q5, if it has collected 25(=5*5) cents or more.

• Initially (when a car arrives at the toll gate), the machine is in state q0

• What is the sequence of states reached if the driver presents the sequence (10,5,5,10) of coins?

• For 6 cases memory used is (log2)6=3 bits

DSFM for toll gate

• 5 Tuples:

  • Q = {q0, q1, q2, q3, q4, q5},

    Σ = {5, 10, 25}

    the start state is q0

    F = {q5}

  • N is the table

DFA 3 State example

• Starting state q1; accept state q2

• Input string 00110: q1->q1->q1->q2->q2->q3. State q3 is not an

accept state so the machine rejects 00110

• Input string 1: q1->q2. State q2 is an accept state so the machine

accepts 1

• Examples in textbook: 1101, 0101010

• The machine accepts every binary string having the property that

  there are an even number of 0s (including no 0) following the

  rightmost 1

• Empty string not accepted

• Strings consisting of 0s only are also rejected

• Strings with an odd number of 0s following the rightmost 1 are also

rejected

Example 1 DSFM/Table

DSFM example

• DFSM Tuple:

• Q = {1, 2, 3, 4}

• Σ = {a, b, c}

• q₀ = 1 (starting state)

• F = {3, 4} (accepting states)

• State Transition Function N

- Ex accepted states: bbaa, aaaaa, aaabc, aaaca, aaacb, aabaa

Candy Machine DSFM

• Scenario: Candy costs 25 cents. Accepts:

• Nickel (n) = 5¢

• Dime (d) = 10¢

- Quarter(q)=25c

• No change returned

• DFSM Tuple:

• States (Q): {0,1,2,3,4,5,6} — represents total

• Input symbols (Σ): {n, d, q}

• Initial state (q₀): 0

• Accepting states (F): {5,6} — machine can vend

candy

• State transition function (N):

Σ (Sigma)

• 1 of 5 tuples in a DSFM representing a finite amount of input symbols

Q

• 1 of 5 tuples representing a finite set of states

q₀ ∈ Q

1 of 5 DSFM tuples. The starting (initial) state in Q.

F ⊆ Q

1 of 5 tuples in a DSFM.he set of accepting (final) states.

N: Q × Σ → Q

• 1 of 5 DSFM tuples. The state transition function, mapping a state and input symbol to a single next state.

• N maps a current state and an input symbol to exactly one next state.

Table FSM Implementation

• 1 row for each state and one column for each input

• Can be referenced as Table[j][k]

• J: state, K:input

• Empty entry means the machine is stuck

Role of Graphical Representation

Represent the software behavior in FSM without actually writing an actual program.

Why do you need DFA?

• Engine behind common tasks on a computer

• Ensure precision and no ambiguoity

• EX: Typing apple

When you press Ctrl+F and type "apple," the

computer builds a tiny temporary DFA.

• State 1: Have I seen "a"?

• State 2: Have I seen "p"?

• State 3: Have I seen another "p"?

• It feeds the entire webpage into that machine letter- by-letter. If it ever hits the "Final State," it highlights the word for you.

What are some uses for DFA?

• Game logic

• Vending machine

• Game characters and their movements

  • Idle state→jump state

  • Jump state→ hit ground→ idle state

  • You would use a DFA to prevent a bug like double jumping