Scientific Computing

A. Automata and Languages

a. Regular Languages
i. Finite Automata
Models that can be used by computers that have a limited
amount of memory. For example a controller for an automatic
door. The only operation is to open and close a door. It senses
the person approaching and will open or close the door if
nothing is detected. This can be visualized in a diagram as
follows,

This is called a state diagram, it shows the activity flow if one

happens. It can also be translated into a state transition table,
which shows the true and false conditions.

To understand the mathematical theory of finite automata, we

can use a finite automaton.
 There are 3 states and q2 will be the accept state. For example
the input string is 1101, we can first start from q1 and it will go to
q2, and loop back to q2, and go to q3, and end with q2, which is
the accept state and therefore the input string is valid.

A finite automaton is a 5-tuple (Q, Σ, δ, q0, F ):

1. Q is a finite set called the states
2. Σ is a finite set called the alphabet
3. δ : Q × Σ−→ Q is the transition function
4. q0 ∈ Q is the start state
5. F ⊆ Q is the set of accept states

We can describe M1, the finite automaton above, formally by

writing M1 = (Q, Σ, δ, q1 , F ), where
1. Q = {q1,q2,q3}
2. Σ = {0,1}
3. δ is described as

4. q1 is the start state

5. F = {q2}

If A is the set of all strings that machine M accepts, we say that

A is the language of machine M and write L(M ) = A. We say that
M recognizes A or that M accepts A. ‘Accept’ means the
machine recognize the one language.

A language is called a regular language if some finite

automaton recognizes it, therefore if a language is accepted by
the finite automaton, the language is a regular language.

ii. Nondeterminism
In NFA, given the current state there could be multiple next
states. The next state may be chosen at random, all the next
state may be chosen in parallel.
In a nondeterministic machine, several choices may exist for the
next state at any point.
 A nondeterministic finite automaton is a 5-tuple (Q,Σ,δ,q0,F):
1. Q is a finite set of states
2. Σ is a finite alphabet
3. δ : Q × Σε −→ P (Q) is the transition function
4. q0 ∈ Q is the start state
5. F ⊆ Q is the set of accept states

iii. Regular Expressions

Where we can use regular operations to build up expressions
describing languages.

Say that R is a regular expression if R is

1. a for some a in the alphabet Σ
 2. ε
3. ∅
4. (R1 ∪ R2), where R1 and R2 are regular expressions
5. (R1 ◦ R2), where R1 and R2 are regular expressions
6. (R1∗), where R1 is a regular expression

iv. Nonregular Languages

Use pumping lemma to prove that a language is not regular. It
can’t be used to probe that a language is regular. The theory is
that a language does not have this property, we are guaranteed
that it is not regular.
The property states that all stsrings in the language can be
‘pumped’ if they are at east as long as a certain special value,
called pumping lemma.

If A is a regLang, then A has a Pumping Length ‘P’ such that

any strings ‘S’ where |S| >= P may be divided into 3 parts S = x
y z.
Such as,
𝑖
1. for each i ≥ 0, x𝑦 z ∈ A
2. |y| > 0
3. |xy| ≤ p

The steps to pumping lemma:

1. Assume that A is a Regular
2. It has to have a pumping length, P
3. All strings longer than P can be pumped, |s| >= P
4. Now find a string ‘S’ in A such that |S| >= P
5. Divide S into x y z
𝑖
6. Show that x 𝑦 z, ϵ ! for some i
7. Then consider all ways that S can be divided into x y z
8. Show that non of these can be satisfy all the pumping
conditions at the same time
9. S can’t be pumped == contradiction, therefore it’s not
regular

b. Context-Free Languages
i. Context-Free Grammars
An example of context-free grammar with the rules
A → 0A1
A→B
B→#
Therefore if the derivation of the string 000#111 using the
grammar above is
A → 0A1 → 00A11 → 000A111 → 000B111 → 000#111

We can also write this using a parse tree.

A context-free grammar is a 4-tuple (V, Σ, R, S):

1. V is a finite set called the variables
2. Σ is a finite set, disjoint from V , called the terminals
3. R is a finite set of rules, with each rule being a variable and a
string of variables and terminals
4. S ∈ V is the start variable.

Example:
Consider grammar G3 = ({S}, {a,b}, R, S). The set of rules, R, is
S →aSb|SS|ε.
This grammar generates strings such as abab, aaabbb, and
aababb. You can see more easily what this language is if you
think of a as a left parenthesis “(” and b as a right parenthesis
“)”. Viewed in this way, L(G3) is the language of all strings of
properly nested parentheses. Observe that the right-hand side
of a rule may be the empty string ε.

Example:
For generating a language that generates qual number of a’s
𝑛 𝑛
and b’s in the form 𝑎 𝑏 . The context-free grammar will be
defined as
G = { (S,A), (a,b), (S→ aAb, A → aAb|𝛆)}
Therefore,
S → aAb
→ aaAbb
→ aaaAbbb
→ aaabbb
 3 3 𝑛 𝑛
→𝑎 𝑏 = 𝑎 𝑏

Chomsky Normal Form is a simplification of CFG. It allows us to

shorthand all the subtraction.
1. If the start symbol S occurs on some right side, create a
new start symbol S and a new production S’ → S
2. Remove null productions
3. Remove unit productions
4. Replace each production A → 𝐵1.... 𝐵𝑛 where n > 2, with A
→ 𝐵1𝐶 where C → 𝐵2... 𝐵𝑛. Repeat this step for all
production having two or more symbols on the right side
5. If the right side of any production is in the form A → aB
where ‘a’ is a terminal and A and B are non-terminals, the
production is replaced by A → XB and X → a. Repeat this
step for every production which is of the form A → aB.

ii. Pushdown Automata

A way to implement CFG in a similar way we design finite
automata for regular grammar.
Pushdown automata is equal with finite state machine with
stack.
A stack has two operations, pop (remove top element) and push
(add a new element to the top).
A PDA (PushDown Automata) has 3 components. An input tape,
finite control unit, and a stack with infinite size.

A pushdown automaton is a 6-tuple (Q, Σ, Γ, δ, q0, F ), where Q,

Σ,
Γ, and F are all finite sets:
1. Q is the set of states
2. Σ is the input alphabet
3. Γ is the stack alphabet
4. δ: Q × Σε × Γε−→P(Q × Γε) is the transition function
5. q0 ∈ Q is the start state
 6. F ⊆ Q is the set of accept states.

iii. Non-Context Free Languages

To test if a language is not context-free, use the pumping
lemma.

If A is a context-free language, then A has a Pumping Length ‘P’

such that any strings ‘S’ where |S|>=P may be divided into 5
parts S = u v x y z. Such that the following condition must be
true,
𝑖 𝑖
1. 𝑢𝑣 𝑥𝑦 𝑧 ϵ A for every i >= 0
2. |vy| > 0
3. |vxy| <= P

Steps:
1. Assume that A is context-free
2. It has to have a pumping length, P
3. All string longer than P can be pumped |s| >= P
4. Now find a string ‘S’ in A such that |S| >= P
5. Divide S into u v x y z
𝑖 𝑖
6. Show that 𝑢𝑣 𝑥𝑦 𝑧 ϵ! for some i
7. Then consider all ways that S can be divided into x y z
8. Show that non of these can be satisfy all the pumping
conditions at the same time
9. If S can’t be pumped, then it contradicts

iv. Deterministic Context-Free Languages

A deterministic pushdown automaton is a 6-tuple (Q, Σ, Γ, δ, q0,
F ),
where Q, Σ, Γ, and F are all finite sets:
1. Q is the set of states
2. Σ is the input alphabet
3. Γ is the stack alphabet
4 . δ : Q × Σ ε × Γε −→ ( Q × Γε ) ∪ { ∅ } is the transition function
5. q0 ∈ Q is the start state
6. F ⊆ Q is the set of accept states

The transition function δ must satisfy the following condition. For

every q ∈ Q, a ∈ Σ, and x ∈ Γ, exactly one of the values
δ(q,a,x),δ(q,a,ε),δ(q,ε,x), andδ(q,ε,ε)
is not ∅.
B. Computability Theory
a. The Church-Turing Thesis
i. Turing Machines
Was proposed by Alan Turing in 1936, it’s similar to a finite
automaton but with unlimited and unrestricted memory.

1. A Turing machine can both write on the tape and read from it.
2. The read-write head can move both to the left and to the right.
3. The tape is infinite.
4. The special states for rejecting and accepting take effect
immediately.

Rules of operation
At each step of the computation, read the correct symbol,
update the same cell, and move exactly one cell either left or
right.

If the head is at the left end of the tape and tries to move left, do
not move. Stay at the left end.

This means that when at q1 and the label is 0, change it to

empty space and move to the right, then it’s at q2.
A Turing machine is a 7-tuple, (Q, Σ, Γ, δ, q0, qaccept, qreject),
where
Q, Σ, Γ are all finite sets:
1. Q is the set of states
2. Σ is the input alphabet not containing the blank symbol ␣
3. Γ is the tape alphabet, where␣∈ Γ and Σ ⊆ Γ
4. δ: Q×Γ−→Q×Γ×{L,R}is the transition function
5. q0 ∈ Q is the start state
6. qaccept ∈ Q is the accept state
7. qreject ∈ Q is the reject state, where qreject ̸= qaccept.

Turing’s Thesis states that any computation that can be carried

out by
mechanical means can be performed by some Turing Machine
 Few arguments for accepting this thesis are
• Anything that can be done with existing digital computers can
also be done by Turing Machine
• No one has yet been able to suggest a problem solvable by
what we
consider on an algorithm, for which a Turing Machine Program
cannot be written.

Recursively Enumerable Language

• A language L and Σ is said to be RE if there exists a Turing
Machine
that accepts it.

ii. Variants of Turing Machines

Multi-tape Turing machine
Theorem - every multi-tape Turing machine has an equivalent
single-tape Turing machine.

Nondeterminism in Turing Machine

A 7 tuples, P = (Q, Σ, Γ , δ, q0, b, F)
• Q = Non-empty set of states
• Σ = Non-empty set of Symbols
• Γ = Non-empty set of Tape Symbols
• δ = Transition function Q x Σ > Γ x (R/L) x Q
• Q0 = Initial state
• B = Blank Symbol
• Z0 = Set of Final states (Accepts & Reject)
• δ = Q x Σ > P{Γ x (R/L) x Q}

Outcomes:
Accept - if any branch of the computation accepts, then the
nondeterministic TM will accept
Reject - if all branches of the computation HALT and REJECT,
then the NDTM rejects
Loop - Computation continues but ACCEPT is never
encountered. Some braces in the computation history are infinite
b. Reducibility
i. Undecidable Problems From Language Theory
How to prove that some problems are undecidable, reduce one
problem to another problem.
Reduce the hard problems into smaller and easier problems.

ii. A Simple Undecidability Problem

 The halting problem - Does a program halt when given a specific
input?
HALTTM = {<M,w>| M is a Turing Machine and M halts on input
w}
Proof:
- Assume it’s decidable
- User R to build another Turing, S, that decides 𝐴𝑇𝑀
- But 𝐴𝑇𝑀 is undecidable

c. Advanced Topic in Computability Theory

The Recursion Theorem
Turing machine that ignores its input and prints out a copy of its
own description → SELF machine.

A compiler which implements ‘compute your own description’ for

a TM.
C. Complexity Theory
Complexity theory - machine A is decidable with restricted resources (time,
memory, processor)
Example:
𝑘 𝑘
Let A = { 𝑎 𝑏 | k >= 0}
How many steps are needed to decide A?
Depends on the input. We give an upper bound for all inputs of length n →
worst-case complexity.
a. Time Complexity
Running time for programms
- Consider only computable functions - decidable (always
halt)
- Consider only deterministic machines
- Consider all inputs of size N
The goal is to find a function of N to describe the running time.

Example:
3 2
𝐹(𝑁) = 17𝑁 + 5𝑁 + 3𝑙𝑜𝑔𝑁3 + 29
 3
Only care about the largest values of N, we only care about 𝑁
Then, we can just show the asymptotic upper bound. Therefore,
we can say that
3
𝐹(𝑁) = 𝑂( 𝑁 )

Example:
Let M be a deterministic TM that always halts, let N be the size
of an input.
The time complexity (running time) of M is a function f.
F(n) - the maximum number of steps that M takes on any input
of size N.
Size of input - means the length of the input.

b. Space Complexity
Let M be a deterministic Turing machine that halts on all inputs.
The space complexity of M is the function f : N −→ N , where f
(n) is the maximum number of tape cells that M scans on any
input of length n. If the space complexity of M is f(n), we also
say that M runs in space f (n).
If M is a nondeterministic Turing machine wherein all branches
halt on all inputs, we define its space complexity f(n) to be the
maximum number of tape cells that M scans on any branch of its
computation for any input of length n.

Let f : N −→ R+ be a function. The space complexity classes,

SPACE(f(n)) and NSPACE(f(n)), are defined as follows.
SPACE(f (n)) = {L| L is a language decided by an O(f (n)) space
deterministic Turing machine}.
 NSPACE(f (n)) = {L| L is a language decided by an O(f (n))
space nondeterministic Turing machine}.
c. Relationships between Time and Space complexity
For t(n) >= n :
1. 𝑇𝐼𝑀𝐸(𝑡(𝑛)) ⊆ 𝑆𝑃𝐴𝐶𝐸(𝑡(𝑛))
𝑂(𝑡(𝑛))
2. 𝑆𝑃𝐴𝐶𝐸(𝑡(𝑛)) ⊆ 𝑇𝐼𝑀𝐸(2 )
Trade off between memory use and runtime performance.
Space efficiency and time efficiency reach at two opposite ends.
The more time efficiency it has, the less space it has, vice versa.