Automata Theory
- An automaton is defined as a system where energy, materials and information are transformed, transmitted and used for performing some functions without direct participation of human.
- Examples are automatic machine tools, automatic packing machines, and automatic photo printing machines.
- In computer science, the term 'automaton' is also known as 'discrete automaton'
Fig. 1: Model of a discrete automaton
The characteristics of automaton are described below:
- Input: At each of the discrete instants of time t1, t2, t3, ...., tm the input values 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 shown in Fig. 1.
- Output: O1, O2, O3, ..., Oq are the outputs of the model, each of which can take a finite number of fixed values from an output O.
- States: At any instant of time the automaton can be in one of the states q1, q2, q3, ..., qn
- State relation: The next state of an automaton at any instant of time is determined by the present state and the present input
- Output relation: The output is related to either state only or to both the input an the state. It should be noted that at any instant of time the automaton is in some state. On 'reading' an input symbol, the automaton moves to a next state which is given by the state relation.
Types of Automaton:
- An automaton in which the output depends only on the input is called an automaton without a memory.
- An automaton in which the output depends on the states as well as the current input is called automaton with a finite memory. This type of automata is also called as Mealy machine.
- An automaton in which the output depends only on the states of the machine is called a Moore machine.
Here is a Worksheet for Practice
Problems to Solve in Automata Theory:
Q1. Given the language L = {ab, aa, baa}, which of the following strings are in L*?
1) abaabaaabaa
2) aaaabaaaa
3) baaaaabaaaab
4) baaaaabaa
Possible Answers:
(A) 1, 2 and 3
(B) 2, 3 and 4
(C) 1, 2 and 4
(D) 1, 3 and 4
Q2. The language, L is defined over Σ = {0, 1, 2, 3, 4, 5, 6, 7} has the following set of strings included in its dictionary:
L = {7, 16, 43, 61, 223, ...}
Identify the language represented by L from the following options:
(A) Alternate odd and even numbers
(B) Octal representation of a number
(C) Divisible by 7
(D) Octal representation of a number divisible by 7.
Q3. Two finite state machines are said to be equivalent if they:
(A) Have the same number of edges
(B) Have the same number of states
(C) Recognize the same set of tokens
(D) Have the same number of edges and states
