0

I need to prove that for an NFA that accepts all languages $L(M)=\{w \in \{a,b\}^* \mid wab \}$ with a suffix of $ab$ needs at least 3 states.

The smallest automata would look like this: $\to(s) \to a \to (a) \to b \to (accepting)$ Abviously you could create a self loop on $(s)$ that accepts $a,b$

I guess for proving it would be sufficient to show that it works with 3 states but not with 2. Can anyone give me a hint on how could I start the proof?

Kailas
  • 241
  • 1
  • 7
Chris
  • 521

2 Answers2

1

Hint : The acceptable string with minimum length is $ab$ (length $2$). Hence, it must have at least $2+1 =3 $ states.

Gaurav
  • 405
1

How about the following:

I show that the automata has to differentiate between 3 different words that don't belong in the same state class. $w \in \{a,b\}^*$

$w_1 = \epsilon\\ w_2 = ab\\ w_3 = a$

For $w_1$ and $w_2$:

$\begin{align*} z_{12} = \epsilon &\Rightarrow& w_1z_{12}&=\epsilon \not\in L\\ &&w_2z_{12}&=ab \in L\end{align*}$

For $w_1$ and $w_3$:

$\begin{align*} z_{13} = b &\Rightarrow& w_1z_{13}&=b \not\in L\\ &&w_3z_{13}&=ab \in L\end{align*}$

For $w_1$ and $w_2$:

$\begin{align*} z_{23} = \epsilon &\Rightarrow& w_2z_{23}&=ab \in L\\ &&w_3z_{23}&=a \not\in L\end{align*}$

Chris
  • 521