why study automata theory

• Relevance of the Automata Theory:

  • Useful to model hardware and software
  • Software for design and test of digital circuits
  • Lexical analysis in compilers (i.e., breaking the input into logical units such as keywords, identifiers)
  • Text processing, web search
  • State machines, communication protocols, security, cryptography, analytics, etc.
• EXAMPLE OF AN AUTOMATON: ON/OFF SWITCH

  • Simple finite automaton - models a switch
  • Two states [circles]: on and off

  o Only one input [labels in edges]: Press -Represents the external influence on the system [state transition] -Press button has an effect dependent of the state

  • Initial state represented by an arrow with label Start
  • There can exist one or more final (acceptance) states, represented by double circles

  
• FINITE AUTOMATON

  • System that in each moment is in one of a finite number of states
  • States memorize the relevant part of the history of the system
  • Being finite, it needs to forget what is not relevant
  • It can be implemented with finite resources. For example, we could implement it in hardware as a circuit. Or as a simple form of program that can make decisions looking only at a limited amount of data or the position in the code itself.
• EXAMPLE OF AN AUTOMATON: RECOGNIZER

  • If the input is the string "then" the automaton goes from the initial to the final state
  • Accumulates the history of the input
  • The goal is to recognize the string "then"

  
• STRUCTURAL REPRESENTATIONS

  There are two important notations that are not automaton-like, but play an important role in the study of automata and their applications: Regular expressions and Grammars
• REGULAR EXPRESSIONS

  • Describe the structure of strings
  • Same power as automata
  • Example: [1-9][0-9][0-9][0-9][-][0-9][0-9][0-9][ ][A-Z][a-z]*
  • Describe "4200-465 Porto" , but not "5505-032 Vila Real"
  • Correction: [1-9][0-9][0-9][0-9][-][0-9][0-9][0-9][ ][A-Z][a-z]*([ ][A-Z][a-z]*)*
  • Correction does not describe, e.g., "Vila Nova de Gaia" ...
  • Lets try it: https://regex101.com
• GRAMMARS

  • Process data with recursive structure.
  • Example of a grammar rule: E -> E + E.
  • One expression may consist of two expressions connected by +.
  • Used in syntactic analyzers (parsers), e.g., in compilers.
  • Lets try it: https://web.stanford.edu/class/archive/cs/cs103/cs103.1156/tools/cfg/
• AUTOMATA AND COMPLEXITY

  • "What can a computer do at all?": This study is called decidability and the problems that can be solved by a computer are called decidable. (E.g., determine whether a player has a winning strategy in a game of Magic: The Gathering)
• AUTOMATA AND COMPLEXITY

  • "What can a computer do efficiently?" This study is called intractability and the problems that can be solved by a computer using no more time than some slowly growing function of the size of the input are called tractable. (E.g., graph coloring: How many colors do you need to color a graph such that no two adjacent vertices are of the same color?)
• AUTOMATA AND COMPLEXITY

  Automata are essential for the study of the limits of computation.