Overview

Consider the language $L_1$ defined as: \[ L_1 = \{ ucv \in \{a,b,c\}^*\ |\ u,v \in \{a,b\}^* \text{ and $u$ is a substring of $v$} \} \] In a homework, you were asked to prove that this language is not regular, i.e. that no finite automaton accepts it (or, equivalently, no regular expression defines it). This proof, like all such proofs we considered in class, should consist of an algorithm that automates the process of finding counter example strings. I.e. for any machine you give it as input, the algorithm should produce a counter example string, customized to that machine, showing that the machine does not accept the language $L_1$. I recieved many algorithms that were seriously flawed in a variety of ways. This self-help assignment is just asking you to take a look at several of these buggy solution algorithms and identify the problems with them. Hopefully, if you can turn the same critical eye to your own assignments, you won't make similar mistakes in the future.

Note: all these algorithms fail because there are machines for which they don't produce valid counter example strings. They're not flawed based on some technicality, or because they are not formatted correctly. They are flawed because you can't run them and get proper counter example strings!

Example 1

Consider the language $L_1$ = { ucv ∈ {a,b,c}* | u,v ∈ {a,b}* and u is a substring of v }. The following purports to be an algorithm that proves that no finite automaton accepts L_1. It is an actual midshipman solution to a homework problem.
Algorithm A
Input: machine $M = \left(Q,\{a,b,c\},\delta/\Delta,s,W)\right)$
Output: string $w'$ such that either $w' \in L_1$ but $w' \notin L(M)$, or $w' \notin L_1$ but $w' \in L(M)$.
  1. set $w = aabcaabaab$
  2. if $M$ doesn't accept $w$
    • $w' = w$
    else
    • $x = \lambda$, $y = aab$, $z = caabaab$
    • set $w' = xy^3z$
  1. Run the algorithm above on the machine $M_A$ shown to the right. What is the string $w'$ returned by the algorithm?
  2. How do you know that $w'$ fails to be a counterexample for this machine?
  3. What went wrong here? What's wrong with this algorithm? Why did it fail to produce a counterexample string?

Example 2

Consider the language $L_1$ = { ucv ∈ {a,b,c}* | u,v ∈ {a,b}* and u is a substring of v }. The following purports to be an algorithm that proves that no finite automaton accepts L_1. It is an actual midshipman solution to a homework problem.
Algorithm B
Input: machine $M = \left(Q,\{a,b,c\},\delta/\Delta,s,W)\right)$
Output: string $w'$ such that either $w' \in L_1$ but $w' \notin L(M)$, or $w' \notin L_1$ but $w' \in L(M)$.
  1. set $w = cabaab$
  2. if $M$ doesn't accept $w$
    • $w' = w$
    else
    • get $x$, $y$, $z$ from the Pumping Lemma version 2.0
    • set $w' = xy^3z$
  1. Try running Algorithm B on the machine $M_B$ shown above. Depending on how forgiving you are, you will either derive a string $w'$ that is not a counterexample or stop and declare that you can't complete a proper run of Algorithm B on this input! What's wrong with this algorithm?

Example 3

Consider the language $L_1$ = { ucv ∈ {a,b,c}* | u,v ∈ {a,b}* and u is a substring of v }. The following purports to be an algorithm that proves that no finite automaton accepts L_1. It is simliar to a number of solutions a homework problem submitted by students.
Algorithm C
Input: machine $M = \left(Q,\{a,b,c\},\delta/\Delta,s,W)\right)$
Output: string $w'$ such that either $w' \in L_1$ but $w' \notin L(M)$, or $w' \notin L_1$ but $w' \in L(M)$.
  1. set $w = u^{|Q|} c v^{|Q|}$
  2. if $M$ doesn't accept $w$
    • $w' = w$
    else
    • get $x$, $y$, $z$ from the Pumping Lemma version 2.0
    • set $w' = xy^2z$
  1. Try running the algorithm above on the machine $M_C$ shown to the right. Why is it that you can't even run this algorithm?!?!

Example 4

Consider the language $L_1$ = { ucv ∈ {a,b,c}* | u,v ∈ {a,b}* and u is a substring of v }. The following purports to be an algorithm that proves that no finite automaton accepts L_1. It is simliar to a number of solutions a homework problem submitted by students.
Algorithm D
Input: machine $M = \left(Q,\{a,b,c\},\delta/\Delta,s,W)\right)$
Output: string $w'$ such that either $w' \in L_1$ but $w' \notin L(M)$, or $w' \notin L_1$ but $w' \in L(M)$.
  1. set $w = a c a^{|Q|}$
  2. if $M$ doesn't accept $w$
    • $w' = w$
    else
    • get $x = a$, $y=c$, $z = a^{|Q|}$ from the Pumping Lemma version 2.0
    • set $w' = xy^0z$ Note: $w'$ doesn't have any $c$'s, and so is not in $L_1$, but the P.L. tells us $w' \in L(M)$
  1. Try running the algorithm above on the machine $M_C$ shown to the right. What string $w'$ does the algorithm return?
  2. How do you know that $w'$ fails to be a counterexample for this machine?
  3. What went wrong here? What's wrong with this algorithm? Why did it fail to produce a counterexample string?

Postscript

Below is Algorithm X, which actually works. It truly generates a counter example string $w'$ for any input machine $M$. The notes in red that augment the algorithm actually prove this fact. Go ahead and run Algorithm X on all of the above input machines, and you'll see that it generates a proper counter example string in all cases.
Algorithm X
Input: machine $M = \left(Q,\{a,b,c\},\delta/\Delta,s,W)\right)$
Output: string $w'$ such that either $w' \in L_1$ but $w' \notin L(M)$, or $w' \notin L_1$ but $w' \in L(M)$.
  1. set $w = a^{|Q|} c a^{|Q|}$ Note: $w \in L_1$
  2. if $M$ doesn't accept $w$
    • $w' = w$ Note: $w \in L_1$ but $w \notin L(M)$, so we have a counter example.
    else
    • get $x$, $y$, $z$ from the Pumping Lemma version 2.0
      Note: $w \in L(M)$ and $|w| \geq |Q|$, so we can call P.L.v2.0.
    • set $w' = xy^2z$ Note: P.L.v2.0 guarantees us that $|xy| \leq |Q|$ and $y \neq \lambda$, so $y$ is one or more $a$'s from the block preceding the "$c$". Thus, $w' \notin L(M)$, since there are more $a$'s before the $c$ than after, but $q \in L(M)$ by P.L.v2.0, so we have a counter example.