Finite Machines

  • Finite Automaton Definition:

    • A finite automaton is a 5-tuple (Q, , δ, q0, F), where:

      • Q is a finite set called states
      • is a finite set called alphabet
      • δ: Q × Q is the transition function
      • q0 Q is the start state
      • F Q is the set of accept states (final sates)
  • Explaining the definition:

    • The definition is called 5-tuple because it consists of 5 parts
    • We use something called a transition function denoted by δ to define rules for moving. If a finite automaton has an arrow from state x to state y labeled with the input symbol 1, that means if the automaton is in state x and it reads 1 it moves to y this transition is denoted as δ(x, 1) = y. This notation is a kind of mathematical shorthand
    • δ: Q × Q. This means that the domain of δ function is combined from Q × and the range is Q (From the functions properties, Introduction)
  • If the start state is also an accept state therefore M accept
  • A language is called regular language if some finite automaton recognizes it
  • Steps for how to think as a machine:

  • You have to figure out what you need to remember about the string you are reading it (we call it crucial information)
  • List the possibilities that the crucial information depend on
  • Assign the transitions, how to go from one possibility to another
  • Set the start state, that means the state of possibility seeing 0 symbols
  • Set the accept states
  • Nondeterministic is a generalization of deterministic

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s