0
$\begingroup$

I'm currently trying to prove that following NFA $\mathcal{M}_0 = (Q, \Sigma, \delta_0,0,\{0\})$ (see picture below) has an exponentially larger DFA $\mathcal{M}$ accepting the same language.

$\mathcal{M} = (2^Q,\Sigma,\delta,\{0\},F)$ is constructed using the subset/powerset algorithm and I'd like to show that $\mathcal{M}$ is minimal (i.e. $F = \{q \in 2^Q \mid 0 \in q\}$).

My problem is to show that every state $q \in 2^Q$ is reachable. I'm trying to prove this by induction over $|q|$.

It is clear for $|q| = 0$ since $\delta(\{0\},b) = \emptyset$. For $|q| = 1$ it follows directly from the NFA: $\Delta(\{0\},a^i) = \{i\}$ for $1 \leq i \leq n-2$.

The problem starts in the inductive step. Let $q = \{i_1,\dots,i_k\}$ with $0 \leq i_1 < i_2 < \cdots < i_k \leq n-2$.

For states with $i_1 = 0, i_k=n-2$ (using the induction hypothesis) or $i_1 = 0, i_2=1$ (using the first case mentioned) it is easy to show but in other cases I have no clue how to do it.

EDIT: Beware that the dotted states also have a $b$ loop to themselves (!), i.e. $\delta_0(i,b)=\{0,i\}$ for $1 \leq i \leq n-3$.

NFA

$\endgroup$
  • $\begingroup$ I am not sure I really understand your goal. You want to prove a lower bound on the size of the minimal DFA for your language? From David's answer, proving that you have a DFA with a large number of accessible states does not give a lower bound on the minimal DFA for your language. To prove such lower bounds, you have to use other techniques. Moreover, I am pretty sure your language can be recognized with a DFA having roughly 2n states... $\endgroup$ – holf Apr 5 '17 at 8:14
  • $\begingroup$ @holf I'd like to show that the subset automaton is minimal. Obviously I could apply the Myhill-Nerode theorem on the language itself or prove that all states are accessible and not equivalent. I'm asking about the first step since I'm already struggling in it. I tried it with $n-2 = 3$, so $n=5$ and the DFA had $2^{n-1} = 16$ states including the trap state from $\{0\}$. It would be great if you show that a DFA exists with only $2n$ states. $\endgroup$ – PeterMcCoy Apr 5 '17 at 8:33
  • $\begingroup$ OK just to be sure: what are the final states? For me it was {0} but maybe you had something different in mind. $\endgroup$ – holf Apr 5 '17 at 9:06
  • $\begingroup$ @holf Yes, $\{0\}$ is the initial and only accepting state of the NFA and there's always a $b$ loop in the dotted states as mentioned above i.e. $\delta_0(i,b) = i$ for $1 \leq i \leq n-3$ and a $b$ transition back to $0$. I added it in the opening post. $\endgroup$ – PeterMcCoy Apr 5 '17 at 9:33
1
$\begingroup$

I try to wrap up your question and answer the part you are interested in.

I. From @DavidRicherby answer, proving that you have a large number of accessible states is not enough to show lower bounds on the size of DFA for your language. As you said it in a comment, you also need to show that those states are not equivalent.

II. As you have already observed, the states of the DFA $\mathcal{M}$ are not equivalent since if $p,q \subseteq Q$ and $i \in p \setminus q$, then reading $a^{n-i-1}$ from $p$ leads to a final state whereas reading it from $q$ doesn't.

III. Let's show that every state of $\mathcal{M}$ are reachable. We only need to construct a word $w_q$ for each $q \subseteq Q$ such that the states that can be reached by reading $w_q$ are exactly $q$ in the initial automaton $\mathcal{M}_0$. I show you how to do it for $|q| = 2$ and then generalise. Assume $q = \{i,j\}$ with $i < j$. Then we define $w_q = a^{j-i}ba^i$. The only non-deterministic choice here is when $b$ is read. Either you decide to stay in state $j-i$ and then in the end you reach state $j$. Otherwise, you decide to backtrack to state $0$ and end up in state $i$.

Now let $q = \{i_1,\ldots,i_k\}$ with $i_1 < \ldots < i_k$. We define $w_q = a^{i_k-i_{k-1}}ba^{i_{k-1}-i_{k-2}}b \ldots ba^{i_2-i_1}ba^{i_1}$. Again, the only non-determinism comes from the letters $b$. You always have two choices: stay or reset to state $0$. If you always decide to stay, then in the end you reach state $i_1+\sum_{t=1}^{k-1}(i_{t+1}-i_t) = i_k$.

Now assume the last time you decide to go back to state $0$ was at the $j$th occurrence of $b$ ($j < k$). You can easily see that you reach state $i_{k-j}$.

Thus, the exact set of states you can reach in $\mathcal{M}_0$ by reading $w_q$ is $q$. Thus, you reach state $q$ in $\mathcal{M}$.

$\endgroup$
3
$\begingroup$

Any regular language is accepted by arbitrarily large automata with no inaccessible states. Let $M = (Q, \Sigma, \delta, q_0, F)$ be an automaton with no inaccessible states. For any natural number $n$, we can write $[n]=\{0, \dots, n-1\}$ and define a new automaton

$$M_n = (Q\times [n], \Sigma, \delta_n, (q_0,0), F\times [n])\,,$$

where $\delta_n((q,i),\sigma) = (\delta(q,\sigma), i+1\bmod n)$ for any $q\in Q$, $i\in[n]$, $\sigma\in\Sigma$.

The effect is that each state counts modulo $n$ the number of characters that have been seen so far, but this has no effect on the behaviour of the automaton, other than making the state space bigger.

The automaton $M_n$ might have inaccessible states, so delete them. But note that, after reading any word of length $0\leq \ell<n$, the automaton is in some state of the form $(q,\ell)$, so at least $n$ states are accessible. Setting $n = 2^{|Q|}$ gives you an exponentially bigger automaton, but why stop there? :-)

Thanks to @holf for the elegant fix to the problem of the disconnected state space.

$\endgroup$
  • $\begingroup$ Let us continue this discussion in chat. $\endgroup$ – holf Apr 5 '17 at 10:41
  • $\begingroup$ @DavidRicherby Thank you for the explanation on how to construct an exponentially bigger automaton. However, this answer doesn't help me in determining a way to show that every state is accessible in the particular subset DFA mentioned in the opening post :( I know that when I prove that every state is accessible and not equivalent the constructed DFA is minimal and proving the non-equivalence is simple with $p,q \in 2^Q\setminus \emptyset, p \ne q$ with $i \in p\setminus q$ and the string $a^{n-i-1}$ which leads to a state in $F$ starting from $p$ but doesn't from $q$. $\endgroup$ – PeterMcCoy Apr 5 '17 at 12:32
  • $\begingroup$ @PeterMcCoy Sure. You asked a bunch of questions and I just answered the first one. But, IMO, the question of whether something is true is more generally interesting than the question of whether a particular proof technique can be made to work. You're completely entitled to wait for somebody to answer all your questions but I'm not so interested in figuring out if the subset construction for that particular automaton produces an automaton with no inaccessible states. I'm not criticizing your question, by the way, it's a perfectly reasonable thing to ask. $\endgroup$ – David Richerby Apr 5 '17 at 13:15
  • 1
    $\begingroup$ @PeterMcCoy And if you actually want to show that a minumal DFA for the language has exponentially many states, a more promising direction would be to try to use Myhill-Nerode to come up with $2^{\Omega(n)}$ equivalence classes of strings in the language. $\endgroup$ – David Richerby Apr 5 '17 at 13:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.