TC

  • Proofs of non-regularity
    • Pumping Lemma
    • Distinguishing extensions
  • exercises on Regular languages (Homework 1)

March 3, 2026

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

Thm. \{a^nb^n \mid n\in \mathbb N\} is not regular

Proof.

  • Suppose, towards a contradiction, that \{a^nb^n \mid n\in \mathbb N\} is regular.
  • Then there is a DFA A=(\{a,b\}, Q, \delta, q_0,F) accepting \{a^nb^n \mid n\in \mathbb N\}.
  • Let T=\{a^n \mid n\in \mathbb N\} (a “test” set of words).
  • For a word w\in\{a,b\}^* let q_0w the state in Q we end-up after reading w.
  • Since |Q|<|T| there must be w_1,w_2\in T, w_1\neq w_2 s.t. q_0w_1=q_0w_2 (why?).
  • By the form of the words in T, there exist n,m\in \mathbb N, n\neq m s.t.
    q_0a^n=q_0a^m.
  • Hence q_0a^nb^n=q_0a^mb^n, contradiction since q_0a^nb^n\in F and q_0a^mb^n\notin F. \square

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.

How to prove that L is not regular (via distinguishing extensions)

A proof template.

  • Suppose, towards a contradiction, that L is regular.
  • Then there is a DFA A=(\{a,b\}, Q, \delta, q_0,F) accepting L
  • Let T=\{\dots\} (a “test” set of words).
  • For a word w\in\{a,b\}^* let q_0w the state in Q we end-up after reading w.
  • Since |Q|<|T| there must be w_1,w_2\in T, w_1\neq w_2 s.t. q_0w_1=q_0w_2.
  • Find a word z s.t. q_0w_1z\in F and q_0w_2z\notin F. Contradiction.

This works also to show that L does not have a DFA with less than a certain number k of states: just use T s.t. |T|\geq k.

Thm. \{a^nb^n \mid n\in \mathbb N\} is not regular (again)

Proof (long, make sure to scroll until you see \square).

  • Suppose, towards a contradiction, that \{a^nb^n \mid n\in \mathbb N\} is regular.
  • Then there is a DFA A=(\{a,b\}, Q, \delta, q_0,F) accepting \{a^nb^n \mid n\in \mathbb N\}. Let p=|Q|.
  • Consider the word w=a^pb^b.
  • Let q_0,q_1,\dots,q_\ell be the sequence of states the DFA passes through while scanning w.
    • q_\ell\in F
    • there must a state that repeats in the sequence (why?) and let q_i the first state that repeats.
  • There must exist x,y,z\in \{a,b\}^* s.t.
    • x is the part of w read when arriving for the first time at q_i
    • y is the part of w read between the first and the second occurrence of q_i
    • z is the rest
  • In other words, there exist x,y,z\in \{a,b\}^* s.t.
    • w=xyz
    • |xy|\leq p
    • |y|\geq 1
  • We can pump the cycle (an arbitrary number of times) and still end-up with an accepting word.
  • That is, it must be that for every i\in \mathbb N, q_0xy^iz\in F.
  • To obtain a contradiction we pump with some i s.t. q_0xy^iz\notin F.
    • Since |xy|<p this part of the string consists only of as.
    • That is xy^iz=a^{p+|y|(i-1)}b^p
    • What i can we choose s.t. q_0a^{p+|y|(i-1)}b^p\notin F?
    • Why does it work? \square

How to prove that L is not regular (via Pumping Lemma)

Proof template.

  • We prove the non-regularity via the Pumping Lemma.
  • Given p\in \mathbb N, choose a specific word w s.t. w\in L and |w|>p.
  • Given x,y,z s.t.
    • w=xyz
    • |xy|\leq p
    • |y|\geq 1
  • Choose some i\in \mathbb N and prove that xy^iz\notin L.

As for the case of \{a^nb^n \mid n\in \mathbb N\}, the idea is to choose w carefully to restrict the possibilities for x,y,z

The pumping Lemma

Theorem 1 If \begin{align*} \forall p\in \mathbb N\ \exists w\in L,\ |w|> p \land \forall x,y,z (w=xyz \land |xy|\leq p \land |y|\geq 1 \\ \implies \exists i\in \mathbb N\ xy^iz\notin L \end{align*} then L is not \mathbf{REGULAR}.

Caution

The Pumping Lemma cannot be used to prove that a language is \mathbf{REGULAR}.

Upcoming classes

Tomorrow
Context-Free Languages
Next Tuesday
  • More on Context-Free Languages
  • exercises on Regular languages (Homework 1)

Quiz 1

Which of the following sentences is false?

  1. (a + b)^∗a^∗ and ((a + b)a)^∗ generate the same language
  2. ((a + b)a)^∗ and (aa + ba)^∗ generate the same language
  3. ((a + b)a)^∗ generates the language reverse of the one generated by (a(a + b))^*
  4. (a + b)^∗a^∗ and (a^∗b)^∗a^∗ generate the same language

Quiz 2

Given the following equation between languages X = (a + \lambda)X + b\ , which of the following sentences is false?

  1. X=a^*b is a solution
  2. X=a^*b^* is a solution
  3. X=a^*b^+ is a solution
  4. X=a^+b^+ is a solution

Quiz 3

Given L=\{w\in \{0,1\}^* \mid \mathrm{value}_2(w)\in 3\mathbb N\}. Consider the sets

\{0,1\}\qquad \{0,1,10\}\qquad\{0,1,10,11\}

How many of them are L-distinguishible?

  1. 0
  2. 1
  3. 2
  4. 3

A set S is L-distinguishible if for every pair of distinct words w_1,w_2\in S, there is a word z s.t. exactly one between w_1z and w_2z is in L.

Quiz 4

You want to show that L=\{a^nb^m \mid n\neq m\} is not a regular language applying the pumping lemma directly to L.

Given the pumping length p, you choose a word w as in the argument to apply the pumping lemma. Which of the following possibilities has a chance to make the rest of the argument correct?

  1. w=a^{p!}b^{p+p!}
  2. w=a^{p+1}b^{p}
  3. w=a^pb^{p+p!}
  4. w=a^{p}b^{p+1}