I am working through Sipser's Introduction to the theory of computation on my own, so I don't have access to a teacher. Hopefully you can help me! Giving hints is highly appreciated.

This question is about problem 1.49a, and the chapter is belongs to is about finite automata, regular languages, pumping lemma. We learned how to prove a language is regular (a finite automaton exists) and how to disprove that (using pumping lemma and/or that regular languages are closed under union, intersection, star, complement).

$ B = \{1^{k}y$ $|$ $y \in \{0,1\}^{*}$ and y contains at least $k$ 1's, for $k \geq 1 \} $

Show that B is a regular language.

I found another question here that answers how to find the regular expression / automaton to recognize this language.

But it seems I found a proof that B is actually not regular: the string $1^{p}01^{p}$ is in B, but by applying the pumping lemma, for pumping length $p$ this string cannot be pumped. Pumping it could make the first string of 1's longer than the second, making the condition in de definition of B where y must contain at least the same amount of 1's as the first string, untrue, and therefore the pumped string is not in B.

Obviously I am not as smart as M. Sipser, and in the question I linked to a proof of regularity has been shown, so I am doing something wrong. What?

  • 1
    $\begingroup$ As discussed in the other question you linked to: the string $1^p 0 1^p$ starts with a $1$ and then contains another $1$ later on, so it belongs in $B$ according to $B$'s membership criterion with $k=1$ (and continues to do so once it's pumped). You don't need to take $k$ as large as possible. $\endgroup$ – mjqxxxx Nov 19 '14 at 15:02
  • 1
    $\begingroup$ Oh! I made the mistake thinking that it would be a problem that pumping $1^{p}01^{p}$ would yield a string that is not of the form $1^{x}01^{x}$... of course it works! Yes I see now how that string can easily be pumped, the pumped fragment can be anything starting after the initial 1. Deleting / multiplying that fragment works. $\endgroup$ – ChrisD Nov 19 '14 at 15:35
  • 1
    $\begingroup$ You've made a common error. Yes, $B$ contains as a subset the language $\{1^p01^p \}$, which is not regular. But many regular languages contain irregular languages as subsets. For example, every irregular language of 0's and 1's is a subset of $(0+1)^*$, and $(0+1)^*$ is as regular as can be. So showing that your language $B$ contains an irregular subset is no use in showing that $B$ is either regular or irregular. $\endgroup$ – MJD Nov 19 '14 at 16:38
  • $\begingroup$ @MJD I probably did not clearly explain what I meant with that part. I meant to say that I thought that I had found a string in B that cannot be pumped, and that string is $1^{p}01^{p}$ for $p$ = pumping length. (But, as it turns out, that string can actually be pumped.) I probably should have put what I meant with the value $p$ earlier in that sentence. My apologies. On the other hand: your comment reinforced my rather brittle understanding of the subject, so thanks! $\endgroup$ – ChrisD Nov 19 '14 at 17:52
  • 1
    $\begingroup$ I totally misunderstood your comment, which now seems completely clear. Sorry for my confusion! $\endgroup$ – MJD Nov 19 '14 at 18:06

Your Answer

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

Browse other questions tagged or ask your own question.