Optional Fun Problem: Birget's Theorem

The Myhill$-$Nerode theorem we proved in lecture is actually a special case of a slightly broader

theorem that says the following:

Theorem: Let $L$ be a language over $$ and Ssube${}^{*}$ be a distinguishing set for $L.$ Then every DFA

for $L$ must have at least $|S|$ states.

It's not that difficult to adapt the proof of the Myhill$-$Nerode theorem from lecture to prove this

version of the theorem. For brevity's sake we aren't going to ask you to do this, but you are

welcome to tinker around with this result if you'd like.

Unfortunately, distinguishability is not a powerful enough technique to lower$-$bound the sizes of

NFAs. In fact, it's in general quite hard to bound NFA sizes; there's a million$-$dollar prize for

anyone who finds a efficient algorithm $($for some precise definition of "efficient"$)$ that, given an

arbitrary NFA, converts it to the smallest possible equivalent NFA!

Although it's generally difficult to lower$-$bound the sizes of NFAs, there are some techniques we can

use to find lower bounds on the sizes of NFAs. Let $L$ be a language over $.$ A generalized fooling

set for $L$ is a set $F$ of pairs of strings in ${}^{**}$ with the following properties:

For any $(x,y)inF,$ we have xyinL.

For any distinct pairs $(x_1,y_1),(x_2,y_2)inF,$ we have $x_1{y}_2!$inL or $x_2{y}_1!$inL $($this is an inclusive

OR$.)$

Prove that if $L$ is a language and there is a generalized fooling set $F$ for $L$ that contains $n$ pairs of

strings, then any NFA for $L$ must have at least $n$ states.

Optional Fun Problem: Birget's Theorem