Complexity theory
1
Introduction to Complexity theory
“Complexity theory" is the body of knowledge
concerning fundamental principles of computation.
Its beginnings can be traced way back in history to
the use of asymptotic complexity and reducibility by
the Babylonians.
2
Modern complexity theory is the result of research activities in
many different fields: biologists studying models for neuron
nets or evolution, electrical engineers developing switching
theory as a tool to hardware design, mathematicians working
on the foundations of logic and arithmetic’s, linguists
investigating grammars for natural languages, physicists
studying the implications of building Quantum computers, and
last but not least, computer scientists searching for efficient
algorithms for hard problems.
The course will give an introduction to some of these areas.
3
Relations and functions
A (binary) relation is a set of pairs. The first
component of each pair is chosen from a set called
the domain, and the second component of each pair is
chosen from a (possibly different) set called the range.
Often, the domain and the range are the same set S. In
that case we say the relation is on S. If R is a relation
and (a; b) is a pair in R, then we often write aRb.
4
Relations and functions
We say a relation R on set S is
reflexive if aRa for all a Ɛ S,
irreflexive if aRa is false for all a Ɛ S,
transitive if aRb and bRc imply aRc,
symmetric if aRb implies bRa,
asymmetric if aRb implies that bRa is false, and
antisymmetric if aRb and bRa implies that a = b.
5
Definitions
• Automaton
— A self-operating machine or mechanism, plural is Automata.
• Automata
— Abstract computing devices
• Automata theory
— The study of abstract machines and the computational problems that
can be solved using these machines.
• Mathematical models of computation
— Finite automata
— Push-down automata
— Turing machines
6
Kinds of Automata
• Automata are distinguished by the temporary
memory
— Finite Automata - no temporary memory
— Pushdown Automata - stack
— Turing Machines - random access memory
7
Kinds of Automata …
Finite
temporary memory
Automaton
input memory
Finite
Automaton
output memory
Example: Vending Machine’s small computing power - a machine from which
items such as packaged food or drinks can be bought by inserting money.
8
Kinds of Automata …
Pushdown Stack Push, Pop
Automaton
input memory
Pushdown
Automaton
output memory
Example: Compilers for Programming Languages
(medium computing power)
9
Kinds of Automata …
Turing
Random Access Memory
Machine
input memory
Turing
Machine
output memory
Examples: Any Algorithm (highest computing power)
10
Kinds of Automata …
Power of Automata
Finite Pushdown Turing
Automata Automata Machine
Less power More power
Solve more computational problems
11
Related Terminology in Complexity Theory
Symbol: an entity or letters
Alphabets: is a finite set of symbols, usually
letters, digits, and punctuations.
String: Sequence of alphabet
Length of Concatenation
u aab, u 3
v abaab, v 5
uv aababaab 8
uv u v 3 5 8
12
Empty String
• A string with no letters: or or
• Observations: 0
w w w
abba abba abba
• Note:
— A language that does not contain any word at all is
denoted by or { }.
— This language doesn’t contain any word not even the
NULL string. i.e. { } ≠ {}
— Suppose a language L doesn’t contain NULL then L = L +
but L ≠ L + {}.
— NULL is identity element with respect to concatenation
13
Substring
• Substring of string is a subsequence of
consecutive characters of the string.
• Example:
String Substring
abbab ab
abbab abba
abbab b
abbab bbab
14
Substring …
• Let a string be abbab
• Example:
Prefixes Suffixes
abbab w uv
a bbab
prefix
ab bab
suffix
abb ab
abba b
abbab
15
The * Operation
•
:*closure of alphabets (also Kleene star)
– Is the set of all strings from alphabet
– There are infinitely many words each of finite length
a, b
* , a, b, aa, ab, ba, bb, aaa, aab,
16
The + Operation
• :Kleene plus
• Is a set of all strings from except
* and
• Note : are infinite
a, b
* , a, b, aa, ab, ba, bb, aaa, aab,
*
a, b, aa, ab, ba, bb, aaa, aab,
17
Finite state automata
– It can be deterministic (DFA) or non-deterministic (NFA)
Deterministic – faster recognizer, but it may take more
space
Non-deterministic – slower, but it may take less space.
• DFA is a five tuple, M(S,,move,s0,F ）
– S: a set of states
: input symbol alphabet
– move: a transition function, mapping from S to S,
move(s,a) = s’
– s0: the start state, s0 ∈ S
– F: a set of states F distinguished as accepting states, FS
Finite …
• Notes on DFA
– No state has an or λ transition.
– For each state s and input symbol a, there is at
most one edge labeled a leaving s.
– To describe a DFA, we use the transition graph
or table
– It accepts an input string x if and only if there is
some path in the transition graph from start
state to some accepting state.
Regular Expressions
• Definition:
– Language-defining symbols generated according
to some rule are called regular expressions
– A regular expression represents a pattern:
• strings that match the pattern are in the language
• strings that do not match are not in the language
20
Regular Expressions …
• Examples:
– (a+b.c)* describes the language
{a,bc}* = {λ, a, bc, aa, abc, bca, …}
– (a+b)+ describes the language
{a,b}+ = {a, b, aa, ab, ba, bb, aaa, …}
21
Pushdown Automata(PDA)
PDAs: a more powerful computation device that can recognize CFLs.
PDA: a є-NFA with a “stack” which serves as “memory”, and store a string of
stack symbols.
●
LR ↔ FSA
●
CFL ↔ PDA
The general non-deterministic version accepts ALL CFLs. The deterministic
version accepts only a subsets of the CFLs.
22
PDA
• PDA Accept input if:
• Input is consumed and stack is empty (Acceptance by
“Empty Stack”)
• Or, input is consumed and PDA is in a final state
(Acceptance by “Final State”).
PDA Rejection
• A string is rejected if there is no computation such that:
All the input is consumed
AND
The last state is an accept state
Hierarchy of languages
Regular Languages Finite State Machines, Regular Expression
Context Free Languages Context Free Grammar, Push-down Automata
Non-Recursively Enumerable Languages
Recursively Enumerable Languages
Recursive Languages
Context-Free Languages
Regular Languages
24
Formal definition of a PDA
● M = (Q, Σ, Γ, δ, q0, z0, F)
Q, Σ, q0, F are the same as in FSAs. Which is?
Γ: set of stack symbols (finite) (denoted using X, Y, Z)
z0: start stack symbol.
δ : Q x ( ΣU {є}) x Γ → 2Q x Γ
* transitions
25
Pushdown Automata (PDA)
tape
tape head
stack head
finite
control stack
p u s h d o w n
The tape is divided into finitely many cells. Each cell contains a symbol in an
26
alphabet Σ.
Pushdown Automata (PDA)
The stack head always scans the top symbol of the stack. It performs
two basic operations:
Push: add a new symbol at the top.
Pop: read and remove the top symbol.
Alphabet of stack symbols: Γ
The head/pointer scans at a cell on the tape and can read a symbol on the
cell. In each move, the head can move to the right cell.
27
FINITE AUTOMATA PUSHDOWN AUTOMATA
A finite automaton (FA) is a simple A pushdown automaton (PDA) is a
idealized machine used to type of automaton that employs a
recognize patterns within input stack.
taken from some character set
It doesn’t has the capability to store It has stack to store the input
long sequence of input alphabets alphabets
Finite Automata can be constructed Pushdown Automata can be
for Type-3 grammar constructed for Type-2 grammar
Input alphabets are accepted by Input alphabets are accepted by
reaching “final states” reaching :
1. Empty stack
2. Final state
NFA can be converted into equivalent NPDA has more capability than DPDA
DFA
It consist of 5 tuples: It consists of 7 tuples:
L = {Q, q0, ∑, F, σ} L = {Q, q0, ∑, F, ᴦ, σ, z0 }
Finite automata can be constructed Pushdown automata can be
for regular language constructed for context free grammar
Pushdown Automaton(PDA)
In one transition the PDA may do the following:
•Consume the input symbol. If є is the input symbol, then no input is
consumed.
•Go to a new state, which may be the same as the previous state.
•Replace the symbol at the top of the stack by any string.
If this string is є then this is a pop of the stack
The string might be the same as the current stack top (does nothing)
Replace with a new string (pop and push) Replace with multiple symbols
(multiple pushes)
29
PDA. Simple example
L = {0 1 | n 0 }.
n n
A PDA is able to recognize this language!
• – Can use its stack to store the number of 0’s it has seen.
• As each 0 is read, push it onto the
stack
• As soon as 1’s are read, pop a 0 off
the stack
• If reading the input is finished exactly
when the stack is empty,
accept the input else reject the input 30
PDA. Simple example
L = {0 1 | n
n n
0 }.
є, empty
stack
є
q q q
0 1 2
0, 1,
push 0
●
pop 0
q0: push 0.
●
q1: pop all 0s while reading 1s.
●
q2: accept when we have an empty
stack.
31
r.e. recursive
languages languages
Multi-Tape Turing Machines
A multi-tape Turing machine is one that has n
tapes for reading and writing information, instead of
only one.
The first tape is initialized with the input, and the
rest are initially empty.
•Despite these added abilities, multi-tape Turing
machines are no more capable than regular ones.
•Store the contents of all n tapes on the one tape,
separated by the # symbol.
Keep track of the tape heads using “dotted symbols”. Each of
these is a new input symbol which is identical to a symbol,
with a dot over it.
Have the machine execute the tape operations of the multi-tape
machine one by one.
If (,) R, we write production
is called a sentential form
39
Time and Space Complexity of a Turing Machine
Time complexity refers to the measure of the number of
times the tape moves when the machine is initialized for
some input symbols and the space complexity is the number
of cells of the tape written.
Time complexity all reasonable functions: T(n) = O(n log
n)
TM's space complexity: S(n) = O(n)
