# 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