1
$\begingroup$

Given a language $L = \left\{ a^{nk+1} | n > 0 \right\}$ and $k$ is an integer constant.

How to show that a DFA for this language must have $k+2$ states or more states using minimum state lemma.

By minimum state lemma I mean the number of minimum state a DFA has is the number of pairewise distinguishable states. I have constructed a set of pairewise distinguishable string ${a, aa, aaa, ... a^{k+2}}$ with respect to L and found that I can not add anymore strings to it. But I don't know how to prove this string has the maximum number of pairewise distinguishable strings.

$\endgroup$
  • 1
    $\begingroup$ What do you think? What have you tried, and where have you failed? Also, can you state the "minimum state lemma"? This is not a standard term, though I'm sure it refers to some form of the Myhill–Nerode theorem. $\endgroup$ – Yuval Filmus Feb 26 '17 at 21:58
  • $\begingroup$ @junhong: why do you care how much bigger the set could be? You only need to prove a minimum DFA size. $\endgroup$ – rici Feb 26 '17 at 22:51
  • $\begingroup$ In the other direction, it suffices to construct a DFA with the minimum number of states. this gives you an upper bound on the maximum number of pairwise distinguishable strings. $\endgroup$ – Yuval Filmus Feb 26 '17 at 23:43
0
$\begingroup$

You can prove that your set is maximal in (at least) two different ways:

  1. Show that every string is equivalent to one of the strings in your set.

  2. Construct a DFA for the language having the same number of states as are strings in your set.

In your case both approaches are not too difficult.

Note, however, that the question only asks you to show that every DFA for the language must contain at least $k+2$ states. For this there is no need to show that your collection is maximal. If you find $k+2$ pairwise inequivalent strings, then it follows that every DFA for the language must contain at least $k+2$ states. If the collection is not maximal, all it means is that your bound isn't tight.

$\endgroup$
  • $\begingroup$ Thank you! For proving the set is maximal, what do you mean by each string is equivenlent to one of the strings in the set? How do you prove this equivalence? $\endgroup$ – Junhong Xu Feb 27 '17 at 0:33
  • $\begingroup$ Given an arbitrary string, you have to show that it's equivalent to (in your case) one of $a,a^2,\ldots,a^{k+2}$. $\endgroup$ – Yuval Filmus Feb 27 '17 at 0:34

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.