Finite Automaton Processing

Finite Automaton

• A finite automaton is a machine that processes an input string and produces an output of either "accept" or "reject".
• The processing begins in the start state, and the automaton receives the input symbols one by one from left to right.
• After reading each symbol, the automaton moves from one state to another along the transition labeled with that symbol.

Formal Definition of a Finite Automation

• A finite automaton has a set of states, a set of rules for moving from one state to another, an input alphabet, a start state, and a set of accept states.
• A finite automaton is defined as a 5-tuple consisting of these five parts.

Language of a Machine

• If A is the set of all strings that a machine M accepts, then A is the language of machine M, denoted as L(M) = A.
• A machine M recognizes a language A, or accepts A.
• A machine may accept several strings, but it always recognizes only one language.

Understanding a Machine

• A good way to understand a machine is to try it on some sample input strings to see how it works.
• By experimenting with sample strings, the machine's method of functioning often becomes apparent.

Finite Automaton M1

• Machine M1 accepts strings that end with a 1, and strings that end with an even number of 0s following the last 1.
• M1 has three states: q1, q2, and q3, with q1 as the start state and q2 as an accept state.

Finite Automaton M2

• Machine M2 accepts all strings that end in a 1, denoted as L(M2) = {w | w ends in a 1}.

Theory of Computation

• The theory of computation begins with the question of what a computer is, and uses idealized models to understand how computers work.
• Finite automata are used as models for computers with extremely limited memory.

Applications of Finite Automata

• Finite automata are used in speech processing, optical character recognition, and modeling and predicting price changes in financial markets.
• They are found at the heart of various electromechanical devices.