Finite Automaton Basics

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.

This quiz covers the fundamental concepts of finite automata, including their processing and output. It explains how the automaton reads input strings and moves between states along the transition.