DFA

• DETERMINISTIC FINITE AUTOMATON (DFA)

  A) tuple

  B) states

  C) input symbols

  D) transition function

  E) initial

  F) start

  G) accept

  H) maior ou igual

  
• EXAMPLE DFA

  
• TRANSITION (STATE) DIAGRAM

  A) graph

  B) node

  C) edge

  D) arrow with start

  E) double circle

  
• TRANSITION TABLE

  • A transition table is the tabular representation of the function, but is sufficient to represent an automaton
  • States -> rows
  • Inputs -> columns
  • Initial state -> arrow
  • Final states -> star (*)

  
• EXAMPLE - 3 EQUIVALENT NOTATIONS

  
• LANGUAGE OF A DFA

  A) accepted

  B) regular

  
• EXAMPLE (FROM SLIDE 4)

  
• (IN)COMPLETE DFAS

  A) not accepted

  B) total

  
• EXAMPLE

  
• COMPLEMENT

  A) - L

  
• PRODUCT

  A) complete

  
• PRODUCT (cont.)

  A) intersection

  B) union

  C) difference

  
• PRODUCT EXAMPLE

  
• PRODUCT EXAMPLE RESULT