Module 1: Fundamental
The Theory of computation is a branch of the theoretical computer science that deals with the study of algorithms and
computational complexity. It aims to answer fundamental questions about
What can be computed
How efficiently it can be done
What limitations exist in terms of computational power
Problem
Now a days machines (digital, analogue, mechanical) play a very crucial role in the development of human, we need some
mechanism (language) to communicate with the machines
Solution
We need a language for communication with machines. But we do not require natural languages to communicate with the
machines, as natural languages are very complex and machine interaction require very fewer complex languages compare
to natural languages.
Sequential Circuit - Definition
A sequential circuit is a digital circuit where output depends on both current inputs and previous states.
It contains memory elements (flip-flops or latches) to store past inputs.
Unlike combinational circuits, sequential circuits retain state information and can perform time-dependent
operations.
Sequential circuits are used in counters, registers, and finite state machines (FSMs).
A sequential circuit consists of:
Inputs: External signals that influence the circuit.
Combinational Logic: Processes inputs and previous states to determine the next state.
Memory Elements (Flip-Flops/Latches): Store past states.
Outputs: The final result based on inputs and stored states.
Block Diagram
The various components of the block diagram are
explained as follows:
Input Tape: The input tape is divided into squares,
each square containing a single symbol from the input
alphabet Σ. The end of the tape is the end marker € at
the left end and the end marker $ at the right end. The
absence of end markers indicates that the tape is of
infinite length. The left-to-right sequence of symbols
between the two end markers is the input string to be
processed
Reading Head (R-head): The head examines only one
square at a time and will move one square to the right.
Finite Control: Is the inference engine take care of transition
Transition State Diagram
Module 1: Fundamental 1
Graphical, easy to understand, easy to design. A transition graph or a transition system is a finite directed labelled graph in
which each circle represents a state and the directed edges indicate the transition of one state to another state. The initial
state is represented by a circle with an arrow pointing towards it, the final state by two concentric circles.
Transition Table
It is a two dimensional table where number of columns equal to the number of input alphabets and number or rows equal to
number of states.
Mathematical Definition of Language
Symbol
Symbols are the basic building blocks, which can be any character or token. In English we call them as letters.
Alphabet
An alphabet is a finite non empty set of symbols (every language has its own alphabet). Here in Theory of computation, we
use symbol Σ for depicting alphabet. e.g. Σ = { a, b, c, …, z }
String
It is a finite sequence of symbols, E.g. Σ= {a, b}. String = aabb, ab, b, so on.
Language
A language is defined as a set of strings. (In natural language - set of words and grammar, we apply this model from words
to sentence)
Similarly, in our system we have finite number of symbols or letters but using those letters we can generate infinite strings
or words
so, we may have languages that have infinite number of words, so it is not possible for us to list them, we have to use some
framework which can be somehow represent the same language, there are mainly two methods to represent a language
by a grammar that generates a language (Regular Grammar generates Regular Language)
by a machine that accepts a language (Finite Automata accepts Regular Language)
Σ
0
= {ε}
Σ
1
= {a, b}
Σ
2
= Σ.Σ = {a, b}.{a, b} = {aa, ab, ba, bb}
Σ
3
= {aaa, aab, aba, abb, baa, bab, bba, bbb}
Σ
k
is the set of all strings from the alphabet Σof length exactly K.
Σ
k
= {W ∣ ∣w∣ = k} (using the symbols from the alphabet Σ
Kleene Closure
if is a set of symbols then we use Σ∗ to denote the set of strings obtained by concatenating zero or more symbols from Σ
of any length, in general any string of any length which can have only symbols specified in Σ.
Σ
∗
= U
i=∞
i=0
{W ∣ ∣w∣ = i}
using the symbols from the alphabet Σ.
Positive Closure
If Σis a set of symbols then we use Σ+ to denote the set of strings obtained by concatenating one or more symbols from
Σ of any length, in general any string of any length which can have only symbols specified in Σ(except ε).
Σ
+
= U
i=∞
i=1
{W ∣ ∣w∣ = i}
using the symbols from the alphabet Σ.
Module 1: Fundamental 2
Automaton
An automaton ins defined as a self operating system where energy, materials and information are transformed,
transmitted and used for performing some functions without direct participation of man.
The term is often used to describe a theoretical machine that operates according to a set of rules and capable of
carrying out complex operations without human intervention..
Example: automatic machine tools, automatic packing machines, and automatic photo printing machines
Module 1: Fundamental 3
