Automata Tutorial
What is Automata?
Automata is a mathematical model and abstract model, which is used to detect string in various languages. In Automata,
- Regular language is recognized by Finite state Automata
- Context Free language is recognized by Push down Automata
- Context sensitive language is recognized by linear bounded Automata
- Recursive Enumerable Language is recognized by Turing Machine.
What do you mean by Finite Automata?
Finite state Automata or Finite State Machine are the simplest model used in Automata. Finite state automata accept regular language. The term finite means it has a limited number of possible states, and number of alphabets in the strings are finite.
Finite state Automata is represented by 5 tuples or elements (Q, ?, q0, F, ?):
Q: It is a collection of finite set of states.
?: It is a finite set of input Symbols called the alphabet of the automata.
q0: It is used for representing initial state of the finite automata from where the starting of the input is processed.
F: It is a collection of finite set of final states.
?: It is used for representing Transition Function. The states of Finite Automata move from one state to another state in response to some inputs by using transition function. The transition function is given by Finite State automata are:
Q x ? -> Q
Examples:
The example of Finite state Automata is Automatic door controller because it has limited memory for detecting the present state of the controller, automatic doors are often found at entrance and exists of various hotels, supermarkets, theaters and hospitals etc. Automatic door have two pads that are used for detection:
Front Pad: This is located at front of the doorway to detect the presence of the person.
Rear Pad: This pad is located at backside of the doorway. In this, controller hold the door to open till the person passes all the way through it.
Some other examples of finite automata are elevator, digital watches, dish washes and calculators.
Important features of Finite Automata
Input: Finite Automata takes some input and with the use of this input we can produce some output. The input of the automata is given in the input tape used in the automata. This tape is divided into cells or squares which can hold one symbol at a time.
Output: Finite Automata produce some output with the use of some input.
States of Automata: Automata have finite number of input states. States of Automata like q0, q1…qn.
State Relation: State relations show how automata moves from one state to another state. The next state of the automata at any instant of time is determined by the present state and the input.
Advantages of finite Automata
Below are some advantages of Finite State Automata and Finite State Machine:
- Finite state machines are very flexible.
- Well suited for domains where execution time is shared between various modules.
- In finite state automata, we can easily determine the reachability of an input state whether it is accepted or rejected.
Disadvantages of finite Automata
Below are some disadvantages of Finite State Automata and Finite State Machine:
- Finite state Automata have very limited amount of memory.
- Various multiplications operations on large numbers cannot be carried out on finite automata, because it has limited memory and it cannot remember the full-length sequence of large numbers.
- Not applicable for all types of applications.
- Finite state Automata cannot process Natural Language processes.
- Finite state automata have less computational power than some other models of computation used in automata such as Push down Automata, linear bounded automata and Turing machine.
Applications of Finite Automata
Finite Automata is used in various fields like science, mathematics, and engineering. Below are some applications of finite automata:
Finite state Automata used in Word Processor Programs to provide features, which allow us to search for a given string.
- It is used in Digital Logic Design to control units for a disk or an Input/output controller on a process.
- It is used in Lexical Analysis phase in complier design.
- It is used in various spell checker applications.
- It is used in various Circuit switching design.
- It is used in various text editors.
Automata Tutorial
- What is Automata
- What is Automata theory
- Finite Automata
- Minimization of Finite Automata
- Conversion from NFA to DFA using Transition diagram
- Finite Automata with output
- Minimization of Finite Automata with output
- Conversion From Moore Machine to Mealy Machine
- Conversion From Mealy Machine to Moore Machine
- What do you mean by Regular Expression?
- Conversion from DFA to Regular expression
- Converting Finite Automata to Regular Conversion using Arden’s Theorem
- Pumping Lemma for Regular Languages
- Closure Properties of Regular Languages
- What do you mean by Context Free Grammar?
- Derivation Tree of Context Free Grammar
- What do you mean by Ambiguity in Context Free Grammar?
- Simplification in Context Free Grammar
- Chomsky Normal Form
- Greibach Normal Form
- Pumping Lemma for Context Free Languages
- Push Down Automata
- Non-deterministic Turing Machine
- Closure Properties of Context Free Languages
- Decision Properties of Context Free Language
- CYK algorithm
- Representation of Push down Automata
- Conversion From Context Free Grammar to Push Down Automata
- Types of Push down Automata
- What do you mean by Turing Machine?
- Representation of Turing Machine?
- What do you mean by Context Sensitive Grammar or Type 1 grammar?
- Grammar in Automata
- How to Construct DFA
- NFA to Regular Expression
- Recursive Grammar in Automata