-1
$\begingroup$

I understand that this topic has been discussed, and I have reviewed numerous posts about it on stack overflow. However, my question remains unresolved. Specifically, I am seeking clarification on the use of the Pigeonhole Principle in determining the regularity of a language.

Consider the string a^{12}.

Suppose we have a DFA with 5 states and we process the string a^{12}. By the Pigeonhole Principle, the DFA will revisit a state more than once. If we remove the segment between the revisited states, this could result in an odd number of a's, for instance, a^7

The string a^7 would end in the same accepting state as a^{12}, yet a^7 does not belong to the language L={a^2n∣n≥0}.

My lecturer mentioned that the Pigeonhole Principle is used to prove that languages are non-regular. Based on this principle, I demonstrated how L fails the test, leading to my confusion. So how can L still be classified as a regular language?

This is also another similar proof that it fails:

enter image description here

$\endgroup$
2
  • $\begingroup$ The problem is in your last part of the proof "the length of $w'$ may not be even". No point in your proof points to the fact that $l_2 - l_1$ might be odd, in fact, for teh DFA for this language, this $l_2-l_1$ value is always even. $\endgroup$
    – EnEm
    Commented Jul 10 at 1:20
  • $\begingroup$ Your proof would have been complete if you showed that for all DFAs that can exist for $L$, there exists a string $l \in L$ such that $l_1 - l_2$ is odd. $\endgroup$
    – EnEm
    Commented Jul 10 at 1:22

1 Answer 1

1
$\begingroup$

The simplest DFA has two states S and O, every a switches from S to O and from O to S, and S is accepting. After 2n “a”s we are in state S, and after 2n+1 “a”s we are in the non-accepting state O.

It’s quite obvious that to move from any state to the same state we need exactly 2k “a”s. Your l2 - l1 can never be odd.

$\endgroup$

Your Answer

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

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