Let $B=\{1^ky|y\in \{0,1\}^* \textrm{ and y contains at least k 1s }, k \geq 1\}$.Again a language that seemingly looks irregular for memory involvement. But we can prove it to be regular instead. It is surprising to see that $B$ can be written as $10+1(1+0)^*$, which is a trivial regular expression. The forward subset relation is trivial. For backward subset relation (i.e., the regular expression is a subset of $B$), we see that other than $10$, we can adjust the first occurrences of 1's in two groups - one corresponding to $1^k$ and the other corresponding to $y$, such that the constraint holds.
Friday, February 26, 2010
Another Interesting Regular Language
Refer to Sipser 2.49a.
Subscribe to:
Post Comments (Atom)
2 comments:
Are you sure that regular expression is correct? Accepted strings must have at least two 1's (k >= 1 so it must start with a 1 and y must contain at least one 1), however, your regular expression accepts both 1 and 10. I believe a correct regular expression is 10*1(1 + 0)*.
Note that 1(1 U 0)* contains the string 10, as (1 U 0)* contains the string 0 (not to mention the string 1, the empty string, and every other string involving a 1, 0 or both). The above comment is incorrect, the string need only contain a single 1 at minimum, and that is at the beginning necessarily and minimally. Thus, 10 is an accepted string because 1^(k=1) = the string 1, the specification is not k>=2, as the above commenter mentioned. By the same logic, the string 1 is accepted.
Post a Comment