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.

Improve this question
$\endgroup$
3
  • 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, 2017 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, 2017 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, 2017 at 23:43

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\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, 2017 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, 2017 at 0:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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