An Automata is used for a recognizer called an acceptor and as a transducer i.e. a machine with output capability as well. Acceptor automata accept a set of words sor strings and reject others. The main application of automata is in designing of lexical analyzer, which is an important part of the Compiler.
Also Check: Theory of Computation: areas, history & importance
In a formal way, an automata is defined as, “It is a system where energy, materials and the data or information are transformed and used for performing some functions very less participation of any human being directly”. Automatic photo printing machines, artificial card punching machines, human detection, and reorganization machine, etc. are real time examples of automata.
Under the computer science branch the term ‘Automata’ means ‘Discrete Automata’ and it is defined as;
Characteristics of automata
The characteristics of automata are as follow;
Input: At each of the discrete instance of time t1, t2, t3, ….., tn the input values are as I1, I2, I3,….Ip, each of which can take a finite number of fixed values from the input alphabet ∑, are applied to the input side of the model.
Output: O1, O2, O3, …., Oq, are the output of the discrete automata model, each of which can take a finite number of fixed values from an output O.
States: An state is a condition of processing the inputs. At any instant of time the automaton can be in one of the states q1, q2, q3, ….. qn.
State relation: The next stage of an automaton at any instant of time is determined by the present state and the present input.
Also check: nfa applications
Output relation: The output is related to either state only or to both the input and the current state. It should be noted that at any instant in time, the automaton is in some state. On reading an input symbol the automaton moves to the next state which is given by the state relation.
Also Check: DFA vs NFA
According to the characteristics of automata, it is useful to run on some given sequence of inputs in discrete time steps. An automaton gets one input every time step that is picked up from a finite set of alphabets. At any time, the symbols so far fed to the automaton as input string. At each time step when the automaton reads an input string, it jumps or transitions to another state that is decided by a transaction function that takes the current state and input symbol as input parameters for the computation of the next state or output. The automaton reads the alphabet of input strings one after another and transitions from state to state as per the transition function rules, until the string is read completely by the automation machine. Once the input word has been read, the automaton is said to have stopped and the state at which automation has stopped is named the final state. Depending on the final state of the machine, it’s clear that the automaton either accepts or rejects an input string.
Example of Automata:
Sequential machine: A sequential machine is a mathematical model of a certain type of simple computational structure. Its behavior represents the working process of finite Automata. Sequential machines have numerous applications, for example, in asynchronous circuits, coding theory, con- current systems, digital circuit design, formal language theory, hardware testing, protocol design, and software and hardware verification.
Vending Machines: A vending machine is an automated machine that dispenses numerous items such as cold drinks, snacks, beverages, alcohol etc. to sales automatically after a buyer inserts currency or credit into the machine. A vending machine is works on a finite state automata to control the functions process.
Traffic Lights: The optimization of traffic light controllers in a city is a systematic representation of handling the instructions of traffic rules. Its process depends on a set of instructions that works in a loop with switching among instructions to control traffic.
Video Games: Video game levels represent the states of automata. In which a sequence of instructions is followed by the players to accomplish the task.
Also check: cfg examples with solutions
Text Parsing: Text parsing is a technique that is used to derive a text string using the production rules of grammar to check the acceptability of a string.
Regular Expression Matching: It is a technique to check whether the two or more regular expressions are similar to each other or not. The finite state machine is useful to check out whether the expressions are acceptable or not by a machine or not.
Speech Recognition: Speech recognition via machine is the technology enhancement that is capable to identify words and phrases in spoken language and convert them to a machine-readable format. Receiving words and phrases from real world and then converted it into machine readable language automatically is effectively solved by using finite state machine.
Also Check: Context Free Grammar solved examples
For theory of computation, I found it very helpful study material. Thank you.
provided study material is very helpful and easy to understand the particular concept…..thank you