Computer Science notes ⇒ Mathematics for Computer Science

N = {0, 1, 2, 3, ...}

Z = {..., -3, -2, -1, 0, 1, 2, 3, ...}

Numbers not in the sets of rationals or integers, e.g.,

R - union of the sets of rationals and irrationals

• Closed interval:
• Open interval:

Therefore, we can write the set of reals as:

We can also mix intervals to get half-opened intervals, e.g.: or .

f : A -> B

Function f maps every value from domain A onto a single value in the range B.

If f(A) = B, then the function is surjective and can be inverted.

The image is that portion of the range for which there exists a mapping for the domain.

Injective Function

Surjective Function

Something that is both injective and surjective is bijective.

A function is even if

A function is odd if

• Polynomial function of degree x.
• Rational functions ( ) where f(x) and g(x) are polynomials.
• Algebraic functions (sum, difference, quotient, power or product of rationals)

Function is built up over a series of intervals, e.g.,:

A more general case could be:

The domain of f(x) is the union of the intervals R₁, R₂, etc: .

To ensure that the piecewise function is indeed a function, they must be pairwise disjoint: . If any intervals overlap, it is not pairwise disjoint, and is not a function.

Let f : A -> B be an injective function. The function g : B -> A is the inverse of f if: . g(y) can also be written as f^-1(y).

A function is not invertable if it is not injective or not surjective.

Consider 2 functions - f : B -> C and g : A -> B, where the domain at f must be indentical to the image of g.

(f·g)(x) = f(g(x))

f·g has domain A and range C. g must be surjective otherwise f is not a function.

g(A) = B

• As x gets closer and closer to a, does the value of function f(x) get closer and closer to some limit, L?
• Can we make the function value f(x) as close to L as desired by making x sufficiently close to a?

If both of the above requirements are met, then:

A more formal definition is:

Limit Rules

Compound Functions Rules

Tolerances

Infinite Limits

A function is continuous if its graph has:

• no breaks
• no holes
• no vertical asymptotes

Therefore, we can say that there are the following types of discontinuity:

• removable discontinuity
• jump discontinuity (piecewise functions)
• infinite discontinuity (vertical asymptote)

Conditions for Continuity

For special functions

Continuity on an Interval

Continuity of Compound Functions

Continuity of Composite Functions

Intermediate Value Theorem

Zeroes of a Function

Provided the limit exists: . Therefore, we can consider the derivative as a function. The domain is the union of all intervals over which f′ exists. f is differentiatible if ∃f′(x).∀x (a, b). Over the closed interval [a, b], f is differentiatible if:

• it is differentiatible over the open interval (a, b) and
• exists

Let g be the inverse of function f : A -> B.

provided that ≠ 0.

However, this is not well formed, as y is expressed in terms of x. We must use our knowledge of the original formula and derivative to reform the derivative to be all in terms of y.

f(g(x)) = f∧g(x)

We can use the chain rule to differentiate this. The chain rule is f(g(x)) = f′(x).g′(x).

The exponential function is of the form a^x, where a ∈ (0,∞) and it is a positive real number constant. The exponential function is defined in five stages.

1. If x is a positive integer then a^x = a × a × a ... x times.
2. If x = 0, then a⁰ = 1
3. If x = -n, where n is a positive integer, then a^-n = 1/aⁿ
4. If x = , where this is a rational number (i.e., p, q ∈ Z), then
5. If x ∈ R, then

If a ∈ (0,∞), then a^x is a continuous function with domain R and range (0,∞).

It is important to remember that this is not the same as the polynomial function. In a polynomial, the function varies on the base, but here it varies on the exponent. f(x) = a^x is exponential, but f(x) = xⁿ is polynomial.

Monotonicity

Exponentials can also be combined. If a, b ∈ (0, ∞) and x, y ∈ R, then a^{x + y} = a^x × a^y and a^{x - y} = a^x ÷ a^y. Also, (a^x)^y = a^xy and (ab)^x = a^xb^x

Exponential Limits

Derivative of Exponential

Natural Exponential

Natural Logarithm

Say you want to express a^x as an exponential to base e.

a^x = e^f(x) and then you can take natural logarithms of both side to get x ln a = f(x), therefore by substituting back in, a^x = e^{x ln a}.

This can then be used to differentiate a^x

D_x a^x = D_x e^{x ln a} = ln a e^{x ln a}, which by substituting back in becomes ln a a^x.

By differentiating from first principles, we showed D_x a^x = a^x , but since we now know that D_x a^x = a^x ln a, then a^x ln a = a^x . We can cancel through by a^x and get ln a = , so we can now say that f′(x) = a^x ln a

Using the rules we learnt earlier for inverses, we can derive the derivative for log_ax, which gives us D_y log_ay = 1/(y ln a)

The iterative algorithm for computing x will be based on a function of preceding values from this sequence. The function will determine convergence, and care should be taken to ensure convergence exists.

MCS covers two main types of algorithm, one-stage (e.g., Newton-Rapheson) and two-stage (e.g., Aitken's method). Two stage algorithms tend to have faster convergence, but one-stage algorithms have simpler initial conditions.

• Under what conditions will fixed-point iterations converge or diverge?
• What path does it take?
• How fast does it move along this path? - Can we choose f(x) to optimise convergance?

x_r+1 = F(x_r)

If it converges to s, lim_r→∞x_r = s and s = F(s), then s is called the fixed point of the iteration scheme. If the iterative process is initiallised with x₀ = s then it will remain static at the fixed point.

Behaviour Close to the Fixed Point

Convergance Paths

Rate of Convergance

Wikipedia

In Newton-Raphson, the gradient in the proximity of the root to guide the search. It is a universal scheme, where only one function is needed to find all the roots - provided that there are good initial estimates. Newton-Raphson is also a faster iteration method - it is quadratic.

Events can be one of two types: deterministic, where the same experimental conditions always give identical answers, or random, where the same experimental conditions give different answers, but the average of a large number of experiments are identical.

In nature, random events occur much more frequently than deterministic.

The sample space is the set of all possible outcomes of a random experiment. S is the universal set for the random experiment. Members of S are called sample points. e.g., for a coin toss, S = {H, T}

Sample spaces come in various forms. The first is a discrete sample space which can be either finite (e.g., a dice throw or coin toss) or infinite (defined on the set of positive integers, and are countable). The other sample space is the continuous sample space, which is defined over the set of reals.

Event A is sure if A ⇔ S - this is probability 1. Event A is impossible if A ⇔ ∅ - this is probability 0.

For events A and B, algebra can be used:

• either A or B - A ∪ B
• both A and B - A ∩ B
• the event not A - A^c
• event A and not B - A - B
• mutually exclusive events (can not occur together) - A ∩ B = ∅

Epistemic means
relating to knowledge

There are two approaches to estimating probability, the first is the a priori (epistemic) approach.

If event A can occur in h different ways out of a total of n possible ways, P(A) = h/n. This assumes the different occurances of A are equally likely and is often referred to as the uniform distribution of ignorance.

Aletoric means
relating to experience

The second approach is the a posteriori (aleatoric) approach. If an experiment is repeated n times and the event A is observed to occur h times, P(A) = h/n, however, n must be a very large value for this to be accurate.

If sample space S is finite, the set of events is the power-set of S. If sample space S is continuous, the events are measurable subsets.

For every event: P(A) ≥ 0, however for the sure event, P(A) = 1. However, for mutually exclusive events A₁, A₂, A₃, ... then P(A₁ ∪ A₂ ∪ A₃ ...) = P(A₁) + P(A₂) + P(A₃) ...

The theorems of probability follow the axioms. If A₁ ⊂ A₂ then P(A₁) ≤ P(A₂) ^ P(A₁ - A₂) = P(A₁) - P(A₂). For every event P(A) ∈ [0,1]. The impossible event has 0 probability P(∅) = 0 and the complementary P(A^c) = 1 - P(A).

If you consider two events, A and B, the probability of B given A has occured has the notation P(B|A) which can be expressed as P(B|A) = P(A ∩ B) / P(A), or equivalently P(A ∩ B) = P(B|A).P(A).

Mutually exclusive events are disjoint (i.e., P(A ∩ B) = 0), so P(B|A) = 0.

The probability of a set of independent events which are anded together (e.g., event A and event B, etc) can be expressed as P(A₁ ∩ A₂ ... A_n) = ∏ⁿ_{i = 1} P(A_i).

If you consider an event where A₁, A₂ ... A_n are mutually exclusive events which could have caused B. The sample space S = Uⁿ_{k = 1}, i.e., one of these events has to occur.

Bayes Rule gives us the probability of event B, and is expressed as: . Bayes theorem is called the theorem of probability of causes.

If you associate a variable with each point in the sample space, this is referred to as a random or stochastic variable. A random variable is discrete if the sample space is countable, or continuous if the sample space is uncountable.

If you consider a set of discrete random variables, X ∈ {x_Ak, A_k ∈ S} defined over the sample space S, the probability distribution P(X = x_Ak) = f(x_Ak), where f : S → [0, 1], f(x) ≥ 0, Σ_{Ak ∈ S}f(x_Ak) = 1.

If X is a continuous random variable, the probability that X takes on the value x is 0, as the sample space is uncountably large.

In a continuous distribution, f(x) is defined to mean P(A ≤ x ≤ B) = ∫^B_Af(x) dx, i.e., the probability that x lies between A and B is equal to the corresponding area beneath the function f(x).

Another method of considering density is cumulative distribution. Here, function F(x) = P(X ≤ x) = P(-∞ < x ≤ x). So, we could say that F(x) = ∫^x_-∞f(x) dx, hence f(x) = dF(x)/dx.

A graph of F(x) plotted against f(x) may look like:

A random event (e.g., heads in a coin toss, 4 on a dice) occurs with probability p and fails to occur with probability 1 - p. A random variable X is the number of times the event occurs in n Bernoulli trials.

The random variable X is the event that there are x successes and n - x failures, in n trials. This gives us the probability of successes to be p^x (where p is the probability of success) and the probability of failures is (1 - p)^{n - x}

There are n!/(x!(n - x)!) ways of getting this Bernoulli Trial, so the probability distribution P(X = x) = (n!/(x!(n - x)!))p^x(1 - p)^{n - x}, which we call the binomial distribution.

The expectation of random variable X is E(X) = Σ_j x_jP(X = x_j) if the event is discrete and E(X) = ∫ xP(X = x) dx if the event is continuous. This gives us a value μ of X, which is the expectation of X.

With the expectation, we can derive various theorems:

• If c is a constant and X is any random value, E(cX) = cE(X)
• If X and Y are any random values, E(X + Y) = E(X) + E(Y)
• If X and Y are independent random values, E(XY) = E(X) × E(Y)

Variance is the expectation of (X - μ)² → Var(X) = E[(X - μ)²]. Standard devaiation σ_X = √Var(X).

• For any random value X, Var(X) = E(X²) - μ².
• If c is a constant and X is any random value, Var(cX) = c²Var(X)
• If X and Y are independent random values, Var(X + Y) = Var(X) + Var(Y) and Var(X - Y) = Var(X) - Var(Y).

The binomial distribution has mean μ = np and variance Var(X) = np(1 - p) which gives a standardised random value as Z = (X - np)/√np(1 - p)

The binomial distribution is limited for rare events. If there is a large sample (i.e., n → ∞), a small probability (i.e., p → 0), the mean μ = np and variance Var(X) ≈ np, then the distribution can be expressed as P(X = x) = (μ^xe^-μ)/x!

The limiting case of the binomial distribution is when n → ∞. P(Z = z) = 1/√2π e^-z2/2, which is the normal distribution.

A non-standardised random value x is Gaussian if P(X = x) = 1/(σ_x√2π e^{-(x - μ2)/(2σ2)}. The sample space here is the set of reals (i.e., x ∈ R), which means x is a continuous random value.

This approximates the binomial with a standardised random value (Z = (X - np)/(np(1 - p)) when n is large and p is neither close to 0 or close to 1.

Transition graphs are pictoral representations of a regular language definition

A transition graph consists of states, an initial state, a final state (also called acceptor states) and named transitions between the states. The double ringed value represents the final state. In the above transition graph, 1 is the initial state and as 2 can not get to the final state, this is an illegal state.

From the transition graph, a transition table can be drawn up, for the above example:

Assume we have an on-off switch, we can define S₁(n) as automata is off after n pushes if and only if n is even and S₂(n) as the automata is on after n pushes if and only if n is odd. We can prove ∀n, S₁(n) ^ S₂(n) using induction.

As usual, we need to prove the base case (S₁(0) ^ S₂(0)) by considering implication in both directions, and prove for n + 1.

An alphabet is a finite non-empty set of symbols, e.g., Σ = {0, 1} or Σ = {a, b, c ... z}, etc

A string is a sequence of symbols of the alphabet, including the empty string (λ). Σ^k is the set of strings of length k (however, Σ ≠ Σ¹). Σ* is the unions of all strings of length k ≥ 0. Σ⁰ = λ. We can also define the set that includes the empty string as Σ⁺ = Σ* - λ

In strings, (assume a ∈ L) aⁿ means a...a (a n times). If w = abc and v = bcd, then wv = abcbcd. Prefixes are anything that forms the start of a string and a suffix is anything that forms the end of a string. The length of a string is the number of symbols in it and this can be represented using |w|.

A language is a set of strings chosen from some Σ*. L is a language over Σ: L ⊆ Σ*. Languages are sets, so any operation that can be performed on a set can be performed on a language, e.g., L is the complement of L.

Automata are abstract models of computing machines. They can read input, have a control mechanism (a finite internal state), a possibly infinite storage capability and an output. In this course, we will mainly be considering finite state automata (FSA) - machines without storage or memory. An important point to consider is that some problems are insoluble using finite state automata, and more powerful concepts are needed.

The DFA is specified using a 5-tuple, M = ⟨Q, Σ, δ, i, F⟩, where

• Q is a finite set of states
• Σ is a finite set of possible input symbols (the alphabet)
• δ is a transition function, such that Q × Σ ← Q
• i is the initial state (i ∈ Q)
• F is a set of final states (F ⊃ Q)

DFA's accept string S, if and only if δ(i, S) ∈ F, where the transition function δ is extended to deal with strings, such that δ(q, aw) = δ(δ(q, a), w). λ is accepted by M, if and only if i ∈ F.

A language L is accepted by an FSA M if and only if M accepts every string S in L and nothing else.

The definition of a DFA is such that for every element of the input alphabet, there is exactly one next state (i.e., δ is a function). An NDFA relaxes this restriction, so there can be more than one next state from a given input alphabet, so the transition function becomes a relation ρ.

There are advantages of non-determinism. Although digital computers are deterministic, it is often convenient to express problems using NDFAs, especially when using search. For example, the following NDFA definining awa, where w ∈ {a, b}* is a natural way of expression:

Any NDFA can be converted into a DFA by considering all possible transition paths in a NDFA and then drawing a DFA where a node is a set of the nodes in an NDFA.

We can formally define an NDFA as a tuple M = ⟨Q, Σ, ρ, i, F⟩, where:

• Q is a finite set of states,
• Σ is a finite set of possible input symbols (the alphabet)
• ρ is a transition relation, ⊃ 2^{Q × (Σ ∪ {λ}) × Q}
• i is an initial state (i ∈ Q)
• F is a set of final states (F ⊃ Q)

ρ can also be defined as a transition function which maps a state and a symbol (or λ) to a set of states.

Hence, we can say a string S is accepted by NDFA M = ⟨Q, Σ, ρ, i, F⟩ if and only if there exists a state q such that (i, S, q) ∈ ρ and q ∈ F, where the transition relation ρ is extended to strings by (q, aw, r) ∈ ρ, if and only if there exists a state p such that (q, a, p) ∈ ρ ^ (p, w, r) ∈ ρ. The empty string λ is accepted by M if and only if i ∈ F.

λ transitions are a feature of an NDFA. A transition does not consume an input symbol and these transitions are labelled with λ.

When converting an NDFA to a DFA with a λ transition, you always follow a λ transition when plotting the possible paths.

We could say that a DFA was a special case of an NDFA, where there are no non-deterministic elements. From the formal definitions of a DFA and NDFA, we could hence prove that for any NDFA, an equivalent DFA could be constructed.

If M is an NDFA ⟨S, Σ, ρ, i, F⟩, then we can construct DFA M′ = ⟨S′, Σ, δ, i′, F′⟩, where:

• S′ = 2^S
• i′ = {i}
• F′ is those subsets of S that contain at least one state in F
• δ is a function from S′ × Σ into S′ such that for each x ∈ Σ, s′ ∈ S′, δ(s′, x) is the set of all s ∈ S such that (u, x, s) ∈ ρ for some u ∈ s′. In other words, δ(s′, x) is the set of all states in S that can be reached from a state in s′ over an arc named x.

Inductive proof exists
in the lecture slides

Since δ is a function, then M′ is a DFA. All that needs to be done is prove that M and M′ accept the same strings. We can do this using induction on the string length, and using path equivalence to show that any string accepted by an NDFA is accepted by the same equivalent DFA.

A language L is regular if a DFA or NDFA exists that accepts L. If M is a DFA, L(M) is the language accepted by M. Every finite language is regular.

See notes for proof
of set operations

If we consider a regular language as a set, we can perform set operations on one or more regular languages, and still get regular languages out.

However, not all languages are regular and can not be represented by a DFA. For example, if we consider Scheme expressions, these have a balanced amount of opening and closing brackets, but these can not be represented by a DFA.

The proof for the pumping
lemma is on the lecture slides

We have a theorem called the pumping lemma that states, if a language contains strings of the form xⁿyⁿ for an arbitarily large n ∈ N then it must also contain strings of the form xⁿy^m where n ∋ m.

Instead of using machines to describe languages, we switch to an algebraic description - this is a more concise way of representing regular languages.

In regular expressions, + represents union, juxtaposition represents concatenation (note, some books use . for concatenation) and * is the star closure. For example:

Formal Definition

Generalised Transition Diagrams

Moore Machines

Mealy Machines

Are Mealy and Moore machines equivalent?

Constructing the Equivalence

Let L be any infinite regular language. There then exists strings x, y, z (where y ≠ λ) such that: ∀n > 0, xyⁿz ∈ L

• Let M be a DFA with n states that accepts L
• Consider a string w with length greater than n that is recognised by M
• Thus, the path taken by w visits at least one state twice
• With this information, we can break the string into three parts:
  • let x be the prefix of w, up to the first repeated state (x may be λ)
  • let y be the substring of w which follows x, such that if it travels round the circuit exactly once it returns to the same state (this must not be λ)
  • let z be the remainder of w
• Thus, w = xyz
• Hence, M accepts any string in the form xyⁿz (where n > 0) and could be represented as:
  

To apply the pumping lemma, you should assume some language L is regular and generate a contradiction. However, this is not perfect, for example, in the case of palindromes. so additional methods must be applied based on the length of symbols in the FSA to create a contradiction.

A problem is effectively soluble if there is an algorithm that gives you the answer in a finite number of steps - no matter on the inputs. The maximum number of steps must be predictable before commencing execution of the procedure.

An effective solution to a problem that has a yes or no answer is called a decision procedure. A problem that has a decision procedure is called decidable.

Equivalence of Regular Expressions

The Complement of a Regular Language

Closure Under Intersection

Closure Under Difference

Testing for Emptiness

Testing for Equivalence

Testing for (In)finiteness

For an example,
see lecture 7

Is there a way to minimise a DFA? States p and q are equivalent if and only if for all input strings w, δ(p, w) is accepting if and only if δ(q, w) is accepting. That is, starting from p and q with a given input, either both end up in an accepting state (not necessarily the same one) or neither does (not necessarily the same). States p and q are distinguisable if there is at least one string w such that one of δ(p, w) and δ(q, w) is accepting and the other is not.

One efficient way of accomplishing this is using the table filling system. For DFA M = (Q, Σ, δ, i, F), if p is an accepting state and q is non-accepting, then the pair {p, q} is distinguishable. The inductive step is that is p and q are states such that for some input symbol a, r = δ(p, a) and s = δ(q, a) are a pair of states known to be distinguishable then {p, q} is a pair of distinguishable states.

The procedure can be performed by filling up a table starting with the states we can distinguish immediately. At the end of the process, those states not marked will show the equivalent states.

The states eventually become an equivalence relation: reflexive, symmetric and transitive. The automaton can be minimised by substituting states for equivalent states

There are two ways to show a particular string is in the language of a grammer. The first involves working from the string towards S, e.g.,

• S → NP VP
• VP → VT NP
• NP → peter
• NP → mary
• VP → runs
• VT → likes
• VT → hates

So, to parse the string "peter hates mary" using the above CFG, the parsing process would look like:

• peter hates mary
• NP hates mary
• NP VT mary
• NP VT NP
• NP VP
• S

It is also possible to work from S towards the string, and this process is called deriving. For example, we could have:

• start with S
• S → NP VP, so rewrite S to NP VP, the notation for this is S ⇒ NP VP
• NP VP ⇒ peter VP
• peter VP ⇒ peter VT NP
• peter VT NP ⇒ peter hates NP
• peter hates NP ⇒ peter hates mary

Formally, we can express derivations as, given a string of symbols αβγ, where α, γ are strings from (V ∪ T)* and β is a string from (V ∪ T)⁺ and a rule β → δ, we can derive αδγ replacing β with δ:

• we write αβγ ⇒ αδγ to indicate that αδγ is directly derived from αβγ
• we are generally interested in the question "Is there a sequence of derivations such that α ⇒ ... ⇒ δ

In our example, we could have written peter VP ⇒ ... ⇒ peter hates mary. We say that peter VP derives peter hates mary, and this is written as peter VP ⇒* peter hates mary.

However, this leaves room for mistakes, as it relies on intuition.

To reduce some (but not all) non-determinism from a derivation, we can consider two types of derivations, left most and right most. In the left most derivation, the left most nonterminal is replaced, and in a right most derivation, the right most nonterminal is replaced. A left most derivation is indicated by: ⇒_lm* and a right most one by ⇒_rm*.

S ⇒* w ⇔ S ⇒_lm* w ^ S ⇒* w ⇔ S ⇒_rm*

Parse/Derivation Trees

Ambiguity

Parsers

• A grammar G generates a string α if S ⇒* α, where S is the start symbol of G.
• A grammar G generates a language L(G) if L(G) is the set of all terminal symbols that can be generated from G, i.e., L(G) = {α ∈ T* | S ⇒* α}

Not all context free grammars are regular, however some are. All regular languages can be expressed by a CFG. A CFG can be express all languages, however.

For a given CFG, the semiword is a string of terminals (maybe none) concatenated with exactly one variable on the right, e.g.,: tttV.

To prove this, we have to theorise that for any given finite automaton there is a CFG that generates exactly the language accepted by the FSA, i.e., all regular languages are context free. This is proved using a construction algorithm - we start with an FSA and generate a CFG:

• The variables of the CFG will be all the names of the states in the FSA, although the start state is renamed S.
• For every edge labelled a ∈ Σ ∨ λ, the transition a between two nodes (A and B) gives a production A → aB (where B = A in the case of a loop)
• An accept state A gives us A → λ
• The initial state gives us the start symbol S

Now we can prove that this CFG generates exactly the language accepted by the original FSA by showing that every word accepted by the FSA can be generated by the CFG and every word generated by the CFG is accepted by the FSA (we know in general that this is not possible, but our CFG has a particular form).

If we consider some word, say abbaa, accepted by the FSA, then we can construct the path through the FSA to an accepting state through a sequence of semi-paths. These semi-paths are formed from the string read from the input followed by the name of the state to which the string takes us.

• start in S, we have a semipath of S
• read a and go to X, semipath: aX
• then read b and go to Y, semipath: abY
• ...
• read the final a and go to semipath abbaaF
• as F is an accepting state, the word abbaa is accepted

This corresponds to a derivation of the string using the productions already generated from the FSA.

To prove the second statement we have to express every word of the CFG in the form of N → tN, thus every working string found in a derivation from this CFG must contain only one nonterminal and that will be at the very end, thus all derivations from this CFG give a sequence of semiwords, starting with S and corresponding to a growing semipath through the FSA. The word itself is only generated by the final accepting nonterminal being turned into a λ - this means the semipath ends in an accepting state, and the word generated is accepted by the FSA.

We have a final theorem to complete our proof: If all the productions of a CFG are either of the form N → semiword or N → word (where the word may be λ).

• Draw a state for each nonterminal and an additional state for the accept state
• For every production of the form N_x → w_yN_z, draw a directed arc from N_x to N_z
• If N_x = N_z then loop
• If N_p → w_q then we have a final state
• Thus, we have constructed a transition graph
• Any path in the transition graph from start to accept corresponds to a word in the language of the transition graph and also to the sequence of productions from the CFG which generate the same word. Conversely, every derivation of a word corresponds to a graph.
• Therefore, this form of CFG is regular.

Regular Grammars

Ambiguity is particularly a problem if we want to compare parsed structures, e.g., structured files. A CFG is ambiguous is there exists at least one string in the language accepted by the CFG for which there is more than one parse tree.

The question we need to ask is whether or not we can develop an algorithm that removes ambiguity from CFGs. There is no general algorithm that can tell us whether or not a CFG is ambiguous (this is discussed further in TOC).

If L is a CFG for which there exists an unambiguous grammar, then L is said to be unambiguous. However, if every grammar that generates L is ambiguous then the language is inherently ambiguous.

Are there techniques that might help us avoid ambiguity? We can look at the two causes of ambiguity:

• no respect for precedence of operators, a structure needs to be forced as required by the operator precedence
• a group of identical operators can group either from the left or from the right. It does not matter which, but we must pick one

A technique for removing ambiguity is introducing several new variables each representing those expressions that can share a level of binding strength.

Total Language Trees

To compute an NDPA, we need to describe sequences of configurations. In the case of an FSA, the state was enough. In the case of an NPDA, we need stacks and states.

The configuration of an NPDA is called the instantaneous description (ID) and is represented by a triple (q, w, γ), where q is the state, w is the remaining input and γ is the stack. As before, we assume the top of the stack is the left hand end.

In DFAs and NDFAs, the δ notation was sufficient to describe sequences of transitions through which a configuration could move, however for NPDAs, a different notation is required.

├_P, or just ├ (when P is assumed) is used to connect two IDs. We also use the symbol ├* to signify there are zero or more transitions of the NDPA. The basis of this is that I ├* I for any ID I, and inductively, I ├* J, if there exists some ID K such that I ├ K and K ├* J, that is, I ├* J if there exists a sequence of IDs K₁,...,K_n, and ∀i = 1, 2, ..., n - 1, K_i ├ K_i+1

We can also state the following principles of IDs:

• If a sequence of IDs (a computation) is legal, then adding an additional input string to the end of the input of each ID is also legal
• If a computation is legal, then the computation formed by adding the same string of stack symbols below the stacks for each ID is also legal
• If a computation is legal and some tail of inputs is not consumed then removing this tail in each case will not affect the legality

We can express these more formally:

• If P = (Q, Σ, Γ, δ, q₀, z₀, F) is an NPDA and (q, x, α) ├*_P (p, y, β), then for any strings w ∈ Σ* and γ ∈ Γ* it is also true that (q, xw, αγ) ├*_P (p, yw, βγ). This captures the first two principles above, and can be proved by induction.
• If P = (Q, Σ, Γ, δ, q₀, z₀, F) is an NPDA and (q, xw, α) ├*_P (p, yw, β), then it is also true that (q, x, α) ├*_P (p, y, β). This captures the third principle above

The language accepted by final state by a NDPA P = (Q, Σ, Γ, δ, q₀, z₀, F) is: L(P) = {w ∈ Σ* | (q₀, w, z₀) ├*_P (q, λ, α), q ∈ F, α ∈ Γ*}. Note that in this definition, the final stack content is irrelevant to this definition of acceptance.

For an NPDA P, the language accepted by empty stack is defined by N(P) = {w|(q₀, w, z₀) ├* (q, λ, λ)}, for any state q ∈ Q. (note that the N here indicates null stack).

For full proof, see Hopcroft
Motwani and Ullman
"Introduction to Automata
Theory, Languages and
Computation", page 231.

The class of languages that are L(P) for some NDPA P is the same for the class of languages that are N(P), perhaps for a different P. This class is exactly the context free languages. The proof of this is based on constructing the relevant automata.

When discussing acceptance by empty stack, the final states (final component) of the NPDA are irrelevant, so are sometimes omitted.

If L = N(P_N) for some NPDA where P_N = (Q, Σ, Γ, δ_N, q₀, z₀), then there is a NPDA P_F such that L = L(P_F). Diagrammatically, this looks like:

We let x₀ be a new stack symbol, the initial stack symbol for P_F and we construct a new start state, p₀ whose sole function is to push z₀, the start symbol of P_N onto the top of the stack and enter state q₀, the start state of P_N. P_F simulates P_N until the stack of P_N is empty. P_F detects this because it detects x₀ on the top of the stack. The state p_f is a new state in P_F which is the accepting state. The new automaton transfers to p_f whenever it discovers that P_N would have emptied its stack.

We can make a formal definition of this accepting state machine as: P_F = (Q ∪ {p₀, p_f}, Σ, Γ ∪ {x₀}, δ_F, p₀, x₀, {p_f}), where δ_F is defined by:

• δ_F(p₀, λ, x₀) = {(q₀, z₀x₀)}. P_F makes a spontaneous transition to the start state of P_N pushing its start symbol z₀ onto the stack.
• ∀q ∈ Q, a ∈ Σ ∪ {λ}, y ∈ Γ, δ_F(q, a, y) contains at least all the pairs in δ_N(q, a, y)
• In addition, (p_f, λ) ∈ δ_f(q, λ, x₀), ∀q ∈ Q
• No other pairs are found in δ_F(q, a, y)

It can be shown that w ∈ L(P_F) ⇔ w ∈ N(P_N). This fact is later used as a proof about languages that an NPDA will accept.

The construction to do a conversion from an acceptance by final state automata to an acceptance by empty stack machine is P_N = (Q ∪ {p₀, p}, Σ, Γ ∪ {x₀}, δ_N, p₀, x₀).

δ_N is defined by:

• δ_N(p₀, λ, x₀) = {q₀, z₀x₀}. The start symbol of P_F is pushed onto the stack at the outset and then goes to the start value of P_F.
• ∀q ∈ Q, a ∈ Σ ∪ {λ}, y ∈ Γ, δ_N(q, a, y) ⊇ δ_F(q, a, y). P_N simulates P_F.
• (p, λ) ∈ δ_N(q, λ, y), ∀q ∈ F, y ∈ Γ ∪ {x₀} - whenever P_F accepts, P_N can start emptying its stack without consuming any more input.
• ∀y ∈ Γ ∪ {x₀}, δ_N(p, λ, y) = {(p, λ)}. Once in p when P_F has accepted, P_N pops every symbol on its stack until the stack is empty. No further input is consumed.

We have shown from our final state to empty stack theorem that if we let L to be L(P_F) for some NPDA P_F = (Q, Σ, Γ, δ_F, q₀, z₀, F) then there is a NPDA P_N such that L = N(P_N). We can then show that the following classes of language are equivalent:

• context free languages
• languages accepted by final state in an NPDA
• languages accepted by empty state in an NPDA

If we have a CFG G, the mechanism is to construct an NPDA that simulates the leftmost derivations of G. At each stage of the derivation, we have a sentential form that describes the state of the derivation: xAα, where x is a string of terminals. A is the first nonterminal and α is a string of terminals and nonterminals. We can call Aα the tail of the sentential form, that is, the string that still needs processing. If we have a sentential form of terminals only, then the tail is λ.

The proposed NDPA has one state and simulates the sequence of left sentential forms that the grammar uses to derive w. The tail of xAα appears on the stack with A on the top.

To figure out how the NDPA works, we suppose that the NDPA is in an ID (q, y, Aα) representing the left sentential form xAα. The string being parsed w has form xy, so we are trying to match y against Aα. The NPDA will guess non-deterministically one of the rules, say A → β as appropriate for the next step in the derivation. This guess causes A to be replaced by β on the stack, so, (q, y, Aα) ├* (q, y, βα). However, this does not necessarily lead to the next sentential form as β may be prefixed by terminals. At this stage, the terminals need to be removed. Each terminal on the top of the stack is checked against the next input to ensure that we have guessed right. If we have not guessed right, then the NPDA branch dies. If we succeed then we shall eventually reach the left sentential form w, i.e., the terminal string where all the symbols of the stack have been expanded (if nonterminals) or matched against input (if terminals). At this point, the stack is empty and we accept by empty stack.

For proof, see
lecture notes

We can make this more precise by supposing F = (V, T, S, R) is a CFG and the construction of NPDA P is as follows: P = ({q}, T, V ∪ T, δ, q, S) (this NPDA is accepting by empty stack), where δ is defined as:

• A ∈ V, δ(q, λ, A) = {(q, β) | A → β ∈ R}
• a ∈ T, δ(q, a, a) = {(q, λ)}

To convert from an NPDA to a CFG, a similar approach is used, but in the other direction. Our problem is that given an NPDA P, we need to find a CFG G whose language is the same language that P accepts by empty stack. We can observe that:

• a fundamental event as far as an NPDA is concerned is the popping of a symbol from the stack, while consuming some input - this is a net process and may involve a sequence of steps including the pushing of other symbols and removal
• this process of popping the element may involve a sequence of state transitions, however there is a starting state at which the process begins and an ending state where it finishes.

In the construction of the grammar below, we use the following notation: nonterminals are associated with the net popping of a symbol, say X and the start and finish states, say p and q for the popping of X. Such a symbol is in the form [pXq].

If we let P = (Q, Σ, Γ, δ, q₀, z₀, F) be an NDPA, then there is a CFG G such that L(G) = N(P). We can construct G = (V, Σ, S, R) as follows:

• Let a special symbol S be the start symbol
• Other symbols: [pXq] where p and q are states in P and Q and X ∈ Γ
• Productions (R) for all states p we have S → [q₀z₀p]. This generates all the strings that cause P to pop z₀ while going from q₀ to p, thus for any string w, (q₀, w₀, z₀) ├* (p, λ, λ)
• Suppose δ(q, a, X) contains the pair (r, Y₁...Y_n) where a = Σ ∪ λ then for all lists of states r₁...r_n G includes the production [qXr_n] → a[rY₁Y₁]...[r_n-1Y_nr_n]. This production says that one way to pop X and go from q to state r_n is to read a (which may be λ) and then use some input to pop Y₁ off the stack while going from r to r₁, then read some input that pops Y₂, etc...

In order to prove that P will accept strings that satisfy this grammar we have to prove that[qXp] ⇒* w ⇔ (q, w, X) ├* (p, λ, λ)

A DPDA provides no choice of move in any situation. Such choice might come from:

• More than one pair in δ(q, a, x)
• A choice between consuming a real input symbol and making a λ transition.

P = (Q, Σ, Γ, δ, q₀, z, F) is deterministic exactly when:

1. δ(q, a, x) has at most one member for any q ∈ Q, a ∈ Σ ∪ {λ}, x ∈ Σ
2. If δ(q, a, x) is non empty for some a ∈ Σ, then δ(q, λ, x) must be empty

DPDAs accept all languages by final state that are regular, but there are also some non-regular languages that are accepted. DPDAs do not accept some context-free languages. All languages accepted by DPDAs are unambiguous, however not all inherently unambiguous languages are accepted by a DPDA.

Every context free language can be generated by a CFG in which all productions areof the form: A → BC, or A → a. This form is called the Chomsky Normal Form. To get to this form, we need to perform various steps.

Firstly we remove useless symbols. For a symbol to be useful, it must be both generating and reachable. X is generating if X ⇒* w, for some terminal string w. Every terminal is therefore generating. X is reachable if there is a derivation S ⇒ αXβ for some α and β.

To compute generating symbols, we have the basis that every terminal in T is generating. The inductive step is that if there is a production A → α and every symbol of α is known to be generating then A is generating.

To compute reachable symbols, we have the basis of S being reachable and the inductive step of supposing variable A is reachable. Then, for all productions with A as the head (LHS), all the symbols of the bodies of those productions are also reachable.

For the next step, we need to eliminate nullable symbols. A is nullable if A ⇒* λ. If A is nullable, then whenever A appears in a production body, A may or may not derive λ.

To compute nullable symbols, we have the base step that if A → λ is a production of G, then A is nullable. Inductively, if there is a production B → C₁C₂...C_k, where each C_i is nullable, then B is nullable. C_i must be a variable to be nullable. The procedure for this is:

1. Suppose G = (V, T, S, P) is a CFG
2. Determine all the nullable symbols
3. Construct G₁ = (V, T, S, P₁), where P₁ is determined as follows: Consider A → X₁X₂...X_k ∈ P, k ≥ 1. Suppose m of the k X_is are nullable then the new grammar will have 2^m versions of this production, where nullable X_is are present and absent. (If m = k, then don't include the A → λ case, otherwise if A → λ is in P, then remove this production)

The final step is to remove unit productions: A → B, where A and B are variables. These productions serve no use, so can be removed. However, we need to take care when identifying cycles. The procedure for identifying unit pairs, A ⇒* B using only unit productions, has the base step of (A, A) is a unit pair, as A ⇒* A. Then by induction, if (A, B) is a unit pair and B → C is a production where C is a variable, then (A, C) is a unit pair.

To eliminate unit productions, if we're given a CFG G = (V, T, S, P), then construct G₁ = (V, T, S, P₁) by finding all the unit pairs, and then for pair (A, B), add to P₁ all the productions A → α where B → α is a non-unit production of P.

Now we have the three processes for converting a CFG to an equivalent minimised CFG, we have to consider a safe order for performing these operations to ensure a minimised CFG. This is:

1. Remove λ productions
2. Eliminate unit productions
3. Eliminate useless symbols

Chomsky Normal Form