CSC236 Notes

Jenci Wei
Fall 2021

1
Contents
1 Simple Induction 3

2 Complete Induction 4

3 Structural Induction 5

4 Principle of Well-Ordering 6

5 Languages 7

6 Regular Expressions 9

7 Deterministic Finite State Machine 10

8 Non-deterministic Finite State Machine 11

9 Regularity of Languages 12

10 Recurrences 14

11 Recursive Correctness 16

12 Iterative Correctness 17

Page 2
1 Simple Induction
If the initial case works, and each case that works implies its successor works, then all cases work

[P (0) ∧ (∀n ∈ N, P (n) =⇒ P (n + 1))] =⇒ ∀n ∈ N, P (n)

Simple induction outline

• Inductive step: introduce n and inductive hypothesis H(n)

– Derive conclusion C(n): show that C(n) follows from H(n), indicating where H(n) is used and
why that is valid
– In simple induction, C(n) is H(n + 1)
• Verify base cases: verify that the claim is true for any cases not covered in the inductive step

Page 3
2 Complete Induction
Notation:
k=n−1
^
P (k) := ∀k ∈ N, k < n =⇒ P (k)
k=0

If all the previous cases always imply the current case, then all cases are true
"k=n−1 # !
^
∀n ∈ N, P (k) =⇒ P (n) =⇒ ∀n ∈ N, P (n)
k=0

Complete induction outline

• Inductive step: state inductive hypothesis H(n)

– Derive conclusion C(n): show that C(n) follows from H(n), indicating where H(n) is used and
why that is valid
– H(n) assumes the main claim for every natural number from the starting point up to n − 1
– C(n) is the main claim for n
• Verify base cases: verify that the claim is true for any cases not covered in the inductive step

Page 4
3 Structural Induction
Recursively defined function: example

1,
 if n = 0
f (n) = 2, if n = 1

f (n − 2) + f (n − 1), if n > 1


Inductively defined set: example

• N is the smallest set such that

1. 0 ∈ N (basis)
2. n ∈ N =⇒ n + 1 ∈ N (inductive step)

– Smallest: no proper subsets satisfy these conditions

• Define E: the smallest set such that

1. x, y, z ∈ E
2. e1 , e2 ∈ E =⇒ (e1 + e2 ), (e1 − e2 ), (e1 × e2 ), (e1 ÷ e2 ) ∈ E

Structural induction
• Define P (e) : vr(e) = op(e) + 1 where
– vr is the variable-counting function
– op is the operator-counting function

• Verify base cases: show that the property is true for the simplest members, {x, y, z}; i.e. show
– P (x)
– P (y)
– P (z)

• Inductive step: let e1 , e2 ∈ E. Assume H({e1 , e2 }), i.e. P (e1 ) and P (e2 ).
– Show that C({e1 , e2 }) follows: all possible combinations of e1 and e2 have the property, i.e.
∗ P ((e1 + e2 ))
∗ P ((e1 − e2 ))
∗ P ((e1 × e2 ))
∗ P ((e1 ÷ e2 ))

Page 5
4 Principle of Well-Ordering
Every non-empty subset of N has a smallest element

Proving a claim using Principle of Well-Ordering

• Assume the negation for a contradiction
• Let S be some set

• Show that S is nonempty and S ⊆ N

• By the Principle of Well-Ordering S has a smallest element, call it s0
• From this, show that there exists an element s less than s0

• This is a contradiction, and so our assumption is false

Page 6
5 Languages
Definitions
• Alphabet: finite, non-empty set of symbols
– Conventionally denoted Σ
– E.g. {a, b}, {0, 1, −1}
• String: finite (including empty) sequence of symbols over an alphabet
– is the empty string
– Σ∗ is the set of all strings over Σ
– E.g. abba is a string over {a, b}
• Language: subset of Σ∗ for some alphabet Σ. Possibly empty, possibly infinite subset
– E.g. {} , {aa, aaa, aaaa, . . .}
– {} =
6 {} since one has length 0 and the other has length 1
String operations:
• |s|: string length, number of symbols in s
– E.g. |bba| = 3
• s = t: iff |s| = |t| and si = ti for 0 ≤ i < |s|
• sR : reversal of s, obtained by reversing symbols of s
– E.g. 1011R = 1101
• st or s ◦ t: concatenation of s and t, all characters of s followed by all those in t
– bba ◦ bb = bbabb
• sk : s concatenated with itself k times
– ab3 = ababab, 1010 =
• Σn : all strings of length n over Σ
• Σ∗ : all strings over Σ
Language operations:
• L: complement of L, i.e. Σ∗ − L
– E.g. if L is language of strings over {0, 1} that start with 0, then L is the language of strings that
begin with 1 plus the empty string
• L ∪ L0 : union
• L ∩ L0 : intersection
• L − L0 : difference
– E.g. {0, 00, 000} − {10, 01, 0} = {00, 000}
• Rev(L): sR : s ∈ L

• LL0 or L ◦ L0 : concatenation, {rt : r ∈ L, t ∈ L0 }

Page 7
– E.g. L {} = L = {} L, L {} = {} = {} L
• Lk : exponentiation, concatenation of L k times
– E.g. L0 = {}, even when L = {}

• L∗ : Kleene star, L0 ∪ L1 ∪ L2 ∪ · · ·

Page 8
6 Regular Expressions
The regular expressions over alphabet Σ is the smallest set such that
1. ∅, , and x, for every x ∈ Σ are REs over Σ
2. If T and S are REs over Σ, then so are
• (T + S) (union) - lowest precedence operator
• (T S) (concatenation) - middle precedence operator
• T ∗ (star) - highest precedence
Regular expression to language
• The L(R), then language denoted by R is defined by structural induction:

– Basis: If R is a regular expression by the basis of the definition of regular expressions, then define
L(R):
∗ L(∅) = ∅ (the empty language, no strings)
∗ L() = {} (the language consisting of just the empty string)
∗ L(x) = {x} (the language consisting of the one-symbol string)
– Induction step: If R is a reular expression by the induction step of the definition, then define
L(R):
∗ L((S + T )) = L(S) ∪ L(T )
∗ L((ST )) = L(S)L(T )
∗ L(T ∗ ) = L(T )∗
Regular expression identities
• Commutativity of union: R + S ≡ S + R
• Associativity of union: (R + S) + T ≡ R + (S + T )

• Associativity of concatenation: (RS)T ≡ R(ST )

• Left distributivity: R(S + T ) ≡ RS + RT
• Right distributivity: (S + T )R ≡ SR + T R

• Identity for union: R + ∅ = R

• Identity for concatenation: R ≡ R = R
• Annihilator for concatenation: ∅R ≡ ∅ ≡ R∅
• Idempotence of Kleene star: (R∗ )∗ ≡ R∗

Page 9
7 Deterministic Finite State Machine
Build an automaton with formalities
• Quintuple: (Q, Σ, q0 , F, δ)
• Q is the set of states
• Σ is finite, non-empty alphabet

• q0 is start state
• F is set of accepting states
• δ : Q × Σ → Q is transition function

Can extend δ : Q × Σ → Q to a transition function that tells us what state a string s takes the automaton
to: (
∗ ∗ ∗ q, if s =
δ : Q × Σ → Q defined by δ (q, s) =
δ(δ (q, s ), a), if s0 ∈ Σ∗ , a ∈ Σ, s = s0 a
∗ 0

String s is accepted iff δ ∗ (q0 , s) ∈ F , and rejected otherwise

Product construction

• Q = Q1 × Q2
• Σ does not change

(1) (2)
• q0 = q0 , q0

• F = F1 × F2 for intersection or {(q1 , q2 ) ∈ Q : q1 ∈ F1 ∨ q2 ∈ F2 } for union

• δ ((q1 , q2 ), c) = (δ1 (q1 , c), δ2 (q2 , c))

Page 10
8 Non-deterministic Finite State Machine
Difference from DFSA
• δ can have multiple outputs
Convert NFSA to DFSA - subset construction
• E.g. Σ = {0, 1}

• Start at the start state combined with any states reachable from the start with -transitions
• If there are any 1-transitions from this new combined start state, combine them into a new state
• If there are any 0-transitions from this new combined start state, combine them into a new state

• Repeat for every state reachable from the start

Equivalence between machines and expressions

L = L(M ) for some DFSA M

⇐⇒ L = L(M 0 ) for some NFSA M 0
⇐⇒ L = L(R) for some regular expression R

Convert DFSA to regular expression - eliminate states

1. s1 , . . . , sm are states with transitions to q, with labels S1 , . . . , Sm

2. t1 , . . . , tn are states with transitions from q, with labels T1 , . . . , Tn
3. Q is any self-loop on q

4. Eliminate q, and union transition label Si Q∗ Tj from si to tj

• Start from si , Si to the former q, then Q any number of times, then Tj to the destination tj
Summary

easy subset construction

RE NFSA DFSA

eliminate states

Page 11
9 Regularity of Languages
Regular languages closure
• L regular =⇒ L regular
• L regular =⇒ Rev(L) regular
• If |L| is finite, then L is regular

• If L is a language in which every string has length ≤ k for some k ∈ N, then L is regular
Pumping Lemma
• If L ⊆ Σ∗ is a regular language, then there is some nL ∈ N such that if x ∈ L and |x| ≥ nL , then

– ∃u, v, w ∈ Σ∗ such that x = uvw (x is a sandwich)

– |v| > 0 (sandwich filling is not empty)
– |uv| ≤ nL (first two layers not bigger than nL )
– ∀k ∈ N, uv k w ∈ L (filling can be “pumped”)
Proof of irregularity using Pumping Lemma

• Assume for contradiction that L is regular

• Let m > 0
• Let x = ... ∈ L, satisfying |x| ≥ m

• By Pumping Lemma, x = uvw, where |uv| ≤ m, and |v| > 0, and for all k ∈ N, uv k w ∈ L.
• Then uvvw ∈ L, however it is not in L
• Which is a contradiction, and so the assumption is false. Therefore L is not regular.
Myhill-Nerode

• If machine M (L) has |Q| = nL , x ∈ L ∧ |x| ≥ nL , denote qi = δ ∗ (q0 , x[: i]), so x “visits” q0 , q1 , . . . , qnL
with the nL +1 prefixes of x (including ), so there is at least one state that x visits twice (by pigeonhole
principle, and x has nL + 1 prefixes)
Proof of irregularity using Myhill-Nerode

• Assume for contradiction that L is regular

• There is some FSA M that accepts L, where M has |Q| = m > 0
• Consider the prefixes x0 , x1 , . . . , xm , which are valid prefixes of...
• Since ther are m + 1 prefixes and m states, there are at least 2 prefixes that drive M to the same state,
so there are 0 ≤ h < i ≤ m such that xh and xi drive M to the same state
• So, since xh y is accepted, xi y must also be accepted
• But xi y is not accepted

• This is a contradiction, and so the assumption is false. Therefore L is not regular

PDA
• DFSA plus an infinite stack with finite set of stack symbols

Page 12
• Each transition depends on the state, (optionally) the input symbol, (optionally) a pop from stack
• Each transition results in a state, (optional) push onto stack
Linear bounded automata
• Finite states

• Read/write a tape of memory proportional to input size

• Tape moves on one position from left to right
• Most realistic model of our current computing capability

Turing machine
• Finite states
• Read/write an infinite tape of memory
• Tape moves on one position from left to right

• Model that we usually use to say what is computable

Each machine has a corresponding grammar
• E.g. FSAs use regexes

Page 13
10 Recurrences
Recursive definition example: Fibonacci patterns
(
n, if n < 2
F (n) = For a natural number n
F (n − 2) + F (n − 1), if n ≥ 2

Closed form for F (n): √ √

φn − φ̂n 1+ 5 1− 5
F (n) = √ , where φ = , φ̂ =
5 2 2
Mergesort complexity
1. Derive a recurrence to express worst-case run times in terms of n = |A|:
(
c0 , if n = 1
T (n) = n n
T 2 + T 2 + n, if n > 1

2. Repeated substitution/unwinding in special case where n = 2k for some natural number k leads to

T (2k ) = 2k T (1) + k2k = c0 n + n log n

Conjecture: T ∈ Θ(n log n)

3. Prove T is non-decreasing
4. Prove T ∈ O(n log n) and T ∈ Ω(n log n)
Divide-and-conquer general case
(
k, if n ≤ B
T (n) =
a1 T nb + a2 T nb + f (n), if n > B

where b, k > 0, a1 , a2 ≥ 0, and a = a1 + a2 > 0. f (n) is the cost of splitting and recombining.
• b: number of pieces we divide the problem into
• a: number of recursive calls of T
• f : cost of splitting and later re-combining the problem input
Master Theorem: if f ∈ Θ(nd ), then

d
Θ(n ),
 if a < bd
T (n) ∈ Θ(n logb n), if a = bd
d

Θ(nlogb a ), if a > bd


• d: degree of polynomial expressing splitting/recombining costs

Master Theorem examples
• Binary search: b = 2, d = 0, a = 1, so the complexity is Θ(log n)
• Mergesort: b = 2, d = 1, a = 2, so the complexity is Θ(n log n)
To prove the Master Theorem:
1. Unwind the recurrence, and prove a result for n = bk

Page 14
2. Prove that T is non-decreasing
3. Extend to all n
Binary multiplication
• Want to multiply bits but they do not fit into a machine instruction

• Cut down each multiplier in x × y in the middle, resulting x1 x0 × y1 y0

xy = (2n/2 x1 + x0 )(2n/2 y1 + y0 ) = 2n x1 y1 + 2n/2 (x1 y0 + y1 x0 ) + x0 y0

– Divide each factor (roughly) in half – b = 2

– Recursively multiply the halves – a = 4
– Combine the products with shifts and adds – d = 1
– Complexity: Θ(n2 )
• Gauss’s trick
xy = 2n x1 y1 + 2n/2 x1 y1 + 2n/2 ((x1 − x0 )(y0 − y1 ) + x0 y0 ) + x0 y0
– a becomes 3 since we only recursively multiplicate 3 times
– Complexity: Θ(nlog2 3 )

Page 15
11 Recursive Correctness
Want to prove: precondition =⇒ termination and postcondition

Proof example: by induction on n

• Base case: n = . . .
– Terminates because there are no loops or further calls
– Returns . . . , so postcondition satisfied
• Induction step: Assume n > . . . and that the postcondition is satisfied for inputs of size 1 ≤ k < . . .,
and the function terminates on such inputs.
– Show that IH applies to the recursive call
– Translate the postcondition to the recursive call
– Show that the original call satisfies postcondition

Page 16
12 Iterative Correctness
Loop invariant
• Come up with a loop invariant
• Prove by induction
Prove termination

• Associate a decreasing sequence in N with loop iterations

• By the Principle of Well-Ordering, there must be a smallest, and hence last, element of the sequence,
which is linked to the last iteration
• Could add a loop invariant to do so

Prove partial correctness

• precondition ∧ execution ∧ termination =⇒ postcondition
• Assume loop terminates after iteration f

• By loop condition . . . , we have . . . , which is the postcondition

Putting everything together, we have iterative correctness

Page 17