Difficulty: Intermediate. Prerequisites: Chapters 1–6 (especially Counting for probability).
Chapter 7 applies the counting tools from Chapter 6 to compute probabilities: how likely is an event? The final also covers regular expressions and finite state automata, which describe patterns in strings and the machines that recognise them. Probability gets 1 question and Regex/FSA gets 1 question on the final.
Sample space (S)
The set of all possible outcomes of an experiment.
Event (E)
A subset of the sample space.
Probability (p(E))
The ratio |E| / |S| when all outcomes are equally likely. Always between 0 and 1.
Conditional probability (p(E|F))
The probability of E given that F has occurred: p(E ∩ F) / p(F).
Independence
E and F are independent if p(E ∩ F) = p(E) · p(F), or equivalently p(E|F) = p(E).
Bernoulli trial
An experiment with exactly two outcomes: success (probability p) and failure (probability q = 1 - p).
Expected value (E(X))
The weighted average of a random variable's outcomes: ∑ p(s) · X(s) over all s in S. For Bernoulli trials with n trials and success probability p, E(X) = np.
Variance (V(X))
A measure of spread: V(X) = E(X²) - (E(X))².
Bayes' theorem
p(F|E) = p(E|F) · p(F) / [p(E|F) · p(F) + p(E|¬F) · p(¬F)]. Think of it as updating a belief after observing evidence.
Regular expression (regex)
A pattern that describes a set of strings over an alphabet.
Finite state automaton (FSA)
A machine (directed graph) with states and transitions that accepts or rejects input strings.
DFA (deterministic FSA)
An FSA with no ε-transitions: from each state, exactly one transition per input symbol.
NFA (nondeterministic FSA)
An FSA that can have ε-transitions and multiple transitions for the same input from one state.
p(E) = |E| / |S| (for equally likely outcomes).
p(Ē) = 1 - p(E), where Ē is the complement of E.
p(E_1 ∪ E_2) = p(E_1) + p(E_2) - p(E_1 ∩ E_2).
Three doors: one car, two goats. You pick a door, the host opens a goat door. Should you switch? Yes. Switching gives a 2/3 chance of winning. Staying gives 1/3. The host's action gives you information that changes the probabilities.
p(E|F) = p(E ∩ F) / p(F).
E and F are independent iff p(E ∩ F) = p(E) · p(F).
Probability of exactly k successes in n trials: p(X = k) = nCk · p^k · q^(n-k).
Probability of at least k successes: ∑(i=k to n) nCi · p^i · q^(n-i).
p(F|E) = p(E|F) · p(F) / [p(E|F) · p(F) + p(E|¬F) · p(¬F)].
Generalised form with multiple hypotheses F_1, …, F_n:
p(F_j|E) = p(E|F_j) · p(F_j) / ∑(i=1 to n) p(E|F_i) · p(F_i).
E(X) = ∑ p(s) · X(s) over all outcomes.
Linearity of expectation: E(X_1 + X_2 + … + X_n) = E(X_1) + E(X_2) + … + E(X_n). This holds even when variables are not independent.
E(aX + b) = a · E(X) + b.
For Bernoulli trials: E(X) = np.
Geometric distribution: p(X = k) = (1 - p)^(k-1) · p, and E(X) = 1/p.
Independent random variables: E(XY) = E(X) · E(Y).
V(X) = E(X²) - (E(X))².
Note: on the exam, ε (epsilon) may be replaced by λ (lambda). They mean the same thing: the empty string.
Alphabet (Σ): a finite set of symbols, e.g. {a, b}.
Language (Σ):* the set of all strings (including ε) over the alphabet.
ε: the empty string (length 0).
*: zero or more repetitions (the Kleene star). a* matches ε, a, aa, aaa, …
+: one or more repetitions. a+ matches a, aa, aaa, … (not ε).
?: zero or one occurrence.
|: or. (a | b) matches a or b.
[ ]: character class. [A-Z] matches any uppercase letter.
Ø: the empty set (no strings accepted).
An FSA is a directed graph where:
Each node is a state, each edge is a transition labelled with a symbol from Σ (or ε).
There is exactly 1 start state and at least 1 accepting (final) state.
If the input string drives the machine to an accepting state, the string is accepted; otherwise it is rejected.
NFA (nondeterministic): can have ε-transitions (transitions that consume no input) and multiple transitions from one state on the same symbol. Harder to implement directly as code.
DFA (deterministic): no ε-transitions, and from each state there is exactly one transition per symbol. Easy to implement. In the worst case, converting an NFA with n states to a DFA can produce up to 2^n states (the power set of the NFA's state set).
The subset construction method: each DFA state corresponds to a set of NFA states. Start with the ε-closure of the NFA's start state, then for each symbol, compute the set of states reachable from the current set. A DFA state is accepting if it contains any NFA accepting state.
Students confuse independent events with mutually exclusive events. Mutually exclusive events have p(E ∩ F) = 0; independent events have p(E ∩ F) = p(E) · p(F). They are different things.
Linearity of expectation holds even for dependent random variables. Students often assume variables must be independent for it to work.
In the Monty Hall problem, students often think the probability is 50/50 after a door is opened. It is not: switching gives 2/3.
An NFA and its equivalent DFA accept exactly the same language. Students sometimes think an NFA is more powerful.
⚠️ 1 question on discrete probability on the final. If you are solid on counting, probability builds on it directly.
⚠️ 1 question on regex and FSA (both DFA and NFA). Know the subset construction for converting NFA to DFA.
⚠️ Bayes' theorem is a common exam question. Be able to set up the formula and plug in.
⚠️ Know the Bernoulli trial formula for "exactly k successes" and "at least k successes."
True or false: p(E) + p(Ē) = 1.
Fill in the blank: for Bernoulli trials, the expected value is ___.
True or false: every NFA can be converted to an equivalent DFA.
What does a* match?
True or false: linearity of expectation requires independence.
Answers: 1. True. 2. np. 3. True. 4. Zero or more repetitions of a (ε, a, aa, aaa, …). 5. False (it holds regardless).
Q: A bag has 4 red and 6 blue balls. You draw one. What is p(red)?
A: |E| = 4, |S| = 10. p(red) = 4/10 = 2/5.
Q: What is the probability of getting exactly 3 heads in 5 fair coin flips?
A: 5C3 · (1/2)³ · (1/2)² = 10/32 = 5/16.
Q: Write a regex over {a, b} that matches all strings starting with a and ending with b.
A: a(a|b)*b.
Q: Can a DFA have ε-transitions?
A: No. Only NFAs can have ε-transitions.
Q: If E(X) = 3 and E(Y) = 5, what is E(X + Y)?
A: E(X + Y) = E(X) + E(Y) = 8 (by linearity of expectation).
Probability depends entirely on the counting techniques from Chapter 6, since p(E) = |E| / |S|. Regular expressions and FSA connect to the theoretical foundations of computation and appear again in more advanced courses such as Theory of Computation (CS 310 at Purdue). The idea of a state machine also underpins compiler design and network protocol specification.
CS 18200, CS 182, Purdue, discrete math, discrete probability, sample space, event, probability, conditional probability, Bayes theorem, independence, Bernoulli trial, binomial distribution, geometric distribution, expected value, variance, linearity of expectation, random variable, Monty Hall problem, regular expression, regex, Kleene star, alphabet, language, finite state automaton, FSA, DFA, NFA, deterministic, nondeterministic, epsilon transition, subset construction, accepting state, start state