Finite Automata

• Finite Automata is a computational model for computers with extremely limited memory.
• Finite Automata is the simplest machine to recognize patterns.
• Finite Automata involve states and transitions among states in response to inputs.
• Finite Automata is an abstract model of a digital computer which reads an input string and changes its internal state depending on the current input symbol.
• Finite Automata is also known as Finite State Machine.
• Two types of Finite Automata:
  • Deterministic Finite Automata (DFA)
  • Nondeterministic Finite Automata (NFA)
• Finite Automata's applications include embedded systems and controllers of household appliances.
• Markov Chains: A probabilistic counterpart of Finite Automata.

State Diagram of Finite Automata

• A finite automaton is a set of states, input symbols, transition function, a start state, and a set of accept states.
• A finite automaton called M₁ has three states: q1, q2, and q3.
• If an input string 1101 is fed into M1:
  • Start in state q1.
  • Read 1, follow transition from q1 to q2.
  • Read 1, follow transition from q2 to q2.
  • Read 0, follow transition from q2 to q3.
  • Read 1, follow transition from q3 to q2.
• Accept: M₁ is in an accept state q2 at the end of the input.

Formal definition of Finite Automata

• Q: Finite set of states
• Σ: Finite set of input symbols
• δ: Transition function that takes as arguments a state and an input symbol and returns a state (Q x ∑ -> Q).
• S/q0 ∈ Q: Start state
• F ⊆ Q : Final state/s or set of accept state/s.
• M₁ has three states: q1, q2, and q3, where M₁ = (Q, Σ, δ, q1, F).
• The input for M₁ is either 0 or 1.
• q1 is the start state for M₁.
• q2 is the accept state for M₁.
• If A is a set of strings that M accepts, A is the language of machine M, and write L(M) = A.
• L(M₁) = A, or equivalently, M₁ recognizes A, where A = {w|w contains at least one 1 and an even number of 0s follow the last 1}.

Deterministic Finite Automata (DFA)

• In DFA, for a particular input character, the machine goes to one state only.
• The term "deterministic“ refers to the fact that on each input there is one and only one state to which the automaton can transition from its current state.