Compiler Designing W02L10

Implementing Finite Automata

  • For lexical analysis, this is the final step as we are moving in this order: Lexical Specifivation –> regex –> NFA –> DFA –> Implementing the table.
  • Sometimes NFA is converted to table directly depending upon space needs.
  • For implementing a FA, a table is made out of the given FA, states and inputs made the rows and columns. A state(or set of states) is the data of the cells.
  • When an NFA is implemented to a table, there can be cases when many rows are same hence these rows are combined and linked to states as linked list, hence less space is consumed.
  • When an NFA is converted to DFA, it can sometimes increase the space consumption.

Converted_file_9f886d65

  • NFA is compact but slower than DFA.

Compiler Designing W0207

Finite Automata I

  • Finite automata is an implementation model fr regex which is a specification language for Lexical Analysis.
  • A finite automata consists of:
∑: set of input alphabets

S: set of states

n: start state

F ⊆ S: accepting state(s)

transition function: state1—>(input) state2

  • L(FA) = set of accepted strings
  • In FA, string is matched when at the end if the input, pointer for the states is on the one of the accepting state(s), otherwise like in case if pointer is stuck or at the end the pointer is not on any accepting state(s) then matching fails.
  • Notations are as follows:
  • STATE -> CIRCLE
  • START STATE -> CIRCLE having edge with NO SOURCE
  • ACCEPTING STATE -> TWO CONCENTRIC CIRCLES
  • TRANSITION -> EDGE CONNECTING TWO STATES