TC

  • common proof techniques
  • minimization algorithm (Moore)
  • exercises on Regular languages (Homework 1)

February 24, 2026

Common proof strategies

  • by contradiction: to prove that P\implies Q, assume P \land \lnot Q and deduce a contradiction.
    e.g.: \sqrt{2} is not rational, there are infinite prime numbers, …
  • by induction: to prove \forall n\in \mathbb{N}\ P(n), prove instead P(0) and that for all n\in \mathbb{N}, P(n)\to P(n+1) or sometimes (P(0)\land P(1)\land \dots\land P(n) \to P(n+1)).
    induction on n\in \mathbb{N}, depth of trees, length of strings, number of connectives in a formula, …
  • by cases: divide the problem at hand into smaller problems.

  • pigeonhole principle: there is no total injective function from \{1,2,3,\dots,n+1\} to \{1,2,3,\dots,n\}
    e.g.: Given five points on a sphere, there is a closed hemisphere containing at least four of them. Pumping Lemma
  • diagonalization:
    e.g. \mathbb{R} and \mathscr{P}(\mathbb{N}) are not countable, the halting problem is not decidable (towards the end of the course)

How to write proofs?

  • use sentences, not just formulas/symbols.
    • what you see on a blackboard is only half of a proof, the rest is the spoken part.
    • read proofs in books as “literature”, to understand the style of writing proofs.
  • what level of detail?
    • As a general rule, if the reader can change the statement of an exercise into something false, but what you wrote still applies, then it is not enough and it is not a proof.
  • Try to “kill” your argument
    • Write down your proof and then try to show the argument is false or that you didn’t write enough details. If you can show is false, then add more details to your proof (or change it if it is wrong).

Recap on DFAs

  • Regular languages are the ones
    • recognized by DFAs
    • described by regular expressions
    • accepted by \lambda-NFAs
  • Closed under union, intersection, complement, concatenation, Kleene star, reverse … how?
    • Exercise 1.2 (part b)
    • Exercise 1.2 (part c)
    • Exercise 1.1 (part a)
    • Exercise 1.1 (part c) [c only L_{aa} \cup L_{bb}]

  • \lambda-NFAs are equivalent to DFAs. How?
  • To every regex we can associate a \lambda-NFA. How?
    • Exercise 1.29 (part a)

Minimum DFA

A=(\Sigma,Q,\delta,q_0,F) DFA to find the minimum DFA for \mathcal L(A), first remove all unreachable states from q_0 Exercici 8 (part a and c)

Idea

For a minimum DFA recognizing the same language as A, we need to identify states that are equivalent w.r.t. accepting words.

p,q\in Q
p\sim q means
\forall w\in \Sigma^*,
\delta(q,w)\in F \iff \delta(p,w)\in F.

[p] := \{q\in Q \mid p\sim q\}

A/_\sim=(\Sigma, \{[p] \mid q\in Q\}, \delta', [q_0], \{[q] \mid q\in F\}) where \delta'([q],a) := [\delta(q,a)] is the minimum DFA equivalent to A.

How do we compute A/_\sim?

p\sim_i q means
\forall w\in \Sigma^*,
if |w| \leq i, then
\delta(q,w)\in F \iff \delta(p,w)\in F.

Properties

  • p\sim_{i+1} q if and only if p\sim_i q and for all a\in \Sigma, \delta(p,a)\sim_i \delta(q,a).
  • if the partition associated to \sim_i and \sim_{i+1} are the same, then \sim_i is the same as \sim.

Moore’s algorithm:

Compute A/_\sim via a partition refinemenet algorithm that iteratively computes \sim_i until it stabilizes, i.e., until \sim_i and \sim_{i+1} are the same.

Moore’s algorithm

\begin{algorithm} \caption{Moore’s algorithm} \begin{algorithmic} \If{$F = \emptyset$} \Return $(\Sigma,\{1\}, \ast, 1, \emptyset)$ \EndIf \If{$F = Q$} \Return $(A,\{1\}, \ast, 1, \{1\})$ \EndIf \ForAll{$p \in \{1,\ldots,n\}$} \State $\pi'[p] \gets \begin{cases} 0 & \text{if } p \in F \\ 1 & \text{otherwise} \end{cases}$ \EndFor \State $\pi \gets \text{undefined}$ \While{$\pi \ne \pi'$} \State $\pi \gets \pi'$ \State compute $\pi'$ from $\pi$ \EndWhile \Return the quotient of $\mathcal{A}$ by $\pi$ \end{algorithmic} \end{algorithm}
\begin{algorithm} \caption{Computing $\pi'$ from $\pi$} \begin{algorithmic} \ForAll{$p \in \{1,\ldots,n\}$} \State $s[p] \gets (\pi[p],\, \pi[p \cdot a_1],\, \ldots,\, \pi[p \cdot a_k])$ \EndFor \State compute the permutation $\sigma$ that sorts the states according to $s[\ ]$ \State $i \gets 0$ \State $\pi'[\sigma(1)] \gets i$ \ForAll{$p \in \{2,\ldots,n\}$} \If{$s[p] \ne s[p-1]$} \State $i \gets i + 1$ \EndIf \State $\pi'[\sigma(p)] \gets i$ \EndFor \Return $\pi'$ \end{algorithmic} \end{algorithm}

What is the worst-case cost of Moore’s algorithm? An example when this happens?

Upcoming classes

Tomorrow
exercises on RACSO
Next Tuesday
  • Proofs of non-regularity
  • exercises on Regular languages (Homework 1)

Quiz

Given two arbitrary languages L_1,L_2 let L_1\Delta L_2 = (L_1\cup L_2)\setminus (L_1\cap L_2)\ .

Which of the following statements is false?

  1. Even if L_1 and L_2 are not regular, L_1\Delta L_2 may be regular.
  2. If only one among L_1 and L_2 is regular, then L_1\Delta L_2 may be not regular.
  3. Even if L_1 and L_2 are regular, L_1\Delta L_2 may be not regular.
  4. If L_1\Delta L_2 and L_1 are regular, then L_2 is regular.

Quiz

Which of the following is a minimum DFA over the alfabeth \Sigma=\{a,b\}?

\begin{array}{r|ll} & a & b \\ \hline \to A & B & A \\ B & B & C\\ C & D & A \\ D & D & E\ \text{+}\\ E & D & F\ \text{+}\\ F & F & D\ \text{+} \end{array}

\begin{array}{r|ll} & a & b \\ \hline \to A & B & A \\ B & B & C\\ C & D & A \\ D & B & C\ \text{+} \end{array}

\begin{array}{r|ll} & a & b \\ \hline \to A & B & B \\ B & C & C \ \text{+}\\ C & D & D \\ D & E & E\\ E & F & F\ \text{+}\\ F & A & A \end{array}

  1. Only the first
  2. Only the second
  3. Only the third
  4. None of them