Problems

Encode Strings of Problems
Finite sequence of characters drawn from some alphabet. Lower case Episolon refers to an alphabet.
Languages
Formal language is a set of strings.
Need for Formalism
We need to formally specify their behavior in ALL cases. ]
  • What happens if there is no transition out of a state on some input?
  • What happens if there are multiple transitions out of a state on some input?

    • Decision Problems

    Example Automaton
    OVERVIEW
  • An automaton is an idealized mathematical computing machine.
  • A language is a set of strings
  • A decision problem is a yes/no question
  • The automaton will input a string and attempt to give an answer

    • Finite Automaton

    Consists of a set of states connected by transitions. Has accepting states - returns YES.
    DFA
    Deterministic, Finite, Automaton.
  • For each state in the DFA, there must be EXACTLY ONE transition defined for each symbol in the alphabet.
  • Unique start state
  • Can be multiple accepting states
    •    Login to remove ads X
    Feedback | How-To