Computational

Theory
Introduction
LECTURE ONE
ASSIST. LECTURER NIYAZ MUHAMAD
Outline
➢What is Theory of Computation?
➢What is Automata
➢What is the difference between robotics and automation?
➢Applications of Computation Theory
➢Sets
➢Operations on Sets
➢Properties of Sets
➢Language
➢Graphs
➢Learning outcomes
What is Theory of
Computation?
➢Theory of computation is the branch that deals with whether and how
efficiently problems can be solved on a model of computation, using an
algorithm.
➢In simple terms, the Theory of Computation answers these questions:
➢What problems can the machine solve? What problems can’t it solve?
➢How fast can a machine solve a problem?
➢How much memory space does a machine need to solve a problem?
➢The main purpose of theory of computation is to develop abstract
mathematical models of computation and to investigate the capabilities
and limitations of these models.
What is Theory of
Computation?
➢The field is divided into three major branches:
❖Automata Theory: Refers to the analysis of how machines work to
solve a problem.
❖Computability Theory: Pertains to determining which problems a
machine can solve and which ones it can’t.
❖Computational Complexity Theory: which analyzes the resources (like
time and memory) required for a machine to solve a problem.
What is Automata
➢studies abstract machines called "automatons" or "automata" (the
plural form), which are derived from the Greek word αὐτόματα
meaning "self-acting".
➢These mathematical models process inputs by moving through states
to perform computations and solve problems, providing a fundamental
understanding of computation.
➢Key types of automata include Finite-State Machines, Pushdown
Automata, Linear-Bounded Automata, and the most powerful, the
Turing Machine, which is the basis for modern computers.
What is the difference between
robotics and automation?
➢Let's look at the difference between robotics and automation.
Automation is the process of performing jobs normally performed by
humans using physical machinery, computer software, and other
technology.
➢Robotics is the process of designing, building, and deploying robots to
complete a certain task.
Applications of Computation
Theory
➢Compiler Design: Automata used in lexical analysis & parsing.
➢Text Processing: Regex (based on automata) used in search & pattern
matching.
➢AI & Natural Language Processing (NLP): Grammars used in chatbots,
translators, and voice assistants.
➢Networking & Security: Protocols modelled as finite automata; intrusion
detection.
➢Operating Systems: Process scheduling & state transitions modelled by
automata.
➢Robotics & Control Systems: Sequential actions modelled by finite
automata.
➢Database Systems: Query optimization uses formal languages.
➢Cryptography: Complexity theory ensures secure encryption.
Sets
➢Set is a collection of “objects” called the elements or members of the
set.
➢Common forms of describing sets are:
❖List all elements, e.g. {a, b, c, d}.
❖Form new sets by combining sets through operators.
Examples in Sets Representation:
C = { a, b, c, d, e, f } finite set
S = { 2, 4, 6, 8, …} infinite set
S = { j : j > 0, and j = 2k for k > 0 }
S = { j : j is nonnegative and even }
Sets
➢Terminology and Notation:
❖To indicate that x is a member of set S, we write x∈ S.
❖To denote the empty set (the set with no members) as {} or ∅.
❖If every element of set A is also an element in set B, we say that A is a
subset of B, and write A⊆ B.
❖If A is not a part of B, if at least one of the elements of A does not
belong to B then we say that A is not a subset of B, and write A⊈ B.
 Operations on Sets
➢Complement(A‛ or A̅): Contain all elements in universal set which are
not in A.
A̅ = { x:x ∉ A | x ∈ U}
➢Union: consist of all elements in either A or B
A ∪ B = { x:x ∈ A or x ∈ B}
➢Intersection: consist of all elements in both A or B
A ⋂ B = { x:x ∈ A and x ∈ B}
➢Difference(-): consist of all elements in A but not in B
A - B = { x:x ∈ A but x ∉ B}
Operations on Sets
➢Cardinality: This refers to the size of set subsets or the number of
elements in set A.
It is denoted by |A| or n(A)
➢Power set: This refers to the set of all possible subsets of a given set,
including the empty set and the set itself.
It is commonly denoted as P(A) or 2𝐴 for a set A.
Properties of Sets
➢Let A, B, and C be subsets of the universal set U.
➢Distributive properties
A ⋂ (B ∪ C) = (A ⋂ B) ∪ (A ⋂ C)
A ∪ (B ⋂ C) = (A ∪ B) ⋂ (A ∪ C)
➢Independent properties
A⋂A=A
A∪A=A
➢Absorption Law
(A ∪ B) ∩ A = A
(A ∩ B) ∪ A = A
Properties of Sets
➢Double Complement property
(A‛ )‛ = A
➢De Morgan’s laws
(A ∪ B)‛ = A‛ ⋂ B‛
(A ⋂ B)‛ = A‛ ∪ B‛
➢Commutative properties
➢A ⋂ B = B ⋂ A
➢A ∪ B = B ∪ A
Properties of Sets
➢Associative laws
A ⋂ (B ⋂ C) = (A ⋂ B) ⋂ C
A ∪ (B ∪ C) = (A ∪ B) ∪ C
➢Identity properties
A∪∅=A
A⋂U=A
➢Complement properties
A ∪ A‛ = U
A ⋂ A‛ = ∅
Language
➢Symbols: Symbols are an entity or individual objects, which can be any
letter, alphabet, or any picture.
Example: 1, a, b, #
➢Alphabets: Alphabets are a finite set of symbols. It is denoted by ∑.
Examples:
∑ = {a, b} ∑ = {A, B, C, D}
∑ = {0, 1, 2} ∑ = {#, β, Δ}
➢String: It is a finite collection of symbols from the alphabet. The string is
denoted by w.
Example: If ∑ = {a, b}, various string that can be generated from ∑ are {ab,
aa, aaa, bb, bbb, ba, aba, ....}.
Language
➢A string with no symbols is known as an empty string. It is represented
by epsilon (𝜖) or lambda (𝜆) or null (∧).
➢The number of symbols in a string w is called the length of a string. It is
denoted by |w|.
Example:
w = 010
|w| = 3
|00100| = 5
|ab| = 2
|∧|=0
Language
➢Language: A language is a set of strings of terminal symbols derivable
from alphabet. A language which is formed over Σ can be Finite or
Infinite.
Example:
L1 = {Set of string of length 2} = {aa, bb, ba, bb} finite language
L2 = {Set of all strings starts with 'a'} = {a, aa, aaa, abb, abbb, ababb, …}
Infinite Language
Types of Languages
➢Talking Language (e.g.: English, Arabic): It has alphabet: ∑ = {a, b, c, …,
z}. From these alphabetic we make sentences that belong to the
language. Now we need a grammar to know if this sentence is true or
false.
➢Programming Language: (e.g.: c++, Pascal):It has alphabetic:
∑ ={a,b,c,..., z , A,B,C,..., Z, ?, /, - ,\}. From these alphabetic we make
sentences that belong to programming language. Now we want to
know if this sentence is true or false so we need a compiler to make
sure that syntax is true.
➢Formal Language: (any language we want): It has strings from these
strings we make sentences that belong to this formal language. And we
want to know if this sentence is true or false so we need rules.
Graphs
➢Automata are indeed a type of directed graph (digraph) used to model
computational processes, where vertices represent states and edges
represent transitions between those states.
➢A graph consists of a set of vertices (V) and a set of edges (E),
➢with edges being ordered pairs of vertices for digraphs. A walk is a
sequence of edges connecting vertices, and a path is a walk with no
repeated edges, while a simple path is a path with no repeated vertices.
Graphs
➢An undirected graph, often simply called a graph, is a fundamental
concept in graph theory and discrete mathematics. It is formally
defined as:
➢A set of points (also known as nodes or vertices).
➢A set of lines (also known as edges or links) that connect some of these
points.
Learning Outcomes
➢Explain the purpose of Theory of Computation and Automata.
➢Distinguish between robotics and automation.
➢Identify applications of computation theory.
➢Apply basic concepts of sets, languages, and graphs.
Thank You