0
B = {1^k y | k >= 1, y in {0, 1}* and y contains at least k 1's }

Is this language regular? If so, how do you prove it, and how would you represent it with a regular expression in Python?

This is for class work, so if you could explain the reasons and processes behind your answer, it'd be much appreciated.

starblue
  • 55,348
  • 14
  • 97
  • 151
camdroid
  • 524
  • 7
  • 24
  • We haven't studied context-free languages yet - how can you tell that? – camdroid Feb 19 '13 at 05:45
  • 2
    It's not regular, because you can't store an arbitrary size `k` in a finite number of states. For a formal proof use the pumping lemma. – starblue Feb 19 '13 at 05:47
  • @starblue - Isn't the Pumping Lemma necessary but not sufficient? – camdroid Feb 19 '13 at 05:56
  • @camdroid: Proof by contradiction. If the necessary condition is not met, then it is not regular expression. – nhahtdh Feb 19 '13 at 06:17
  • @nhahtdh: Proof by contradiction using Pumping Lemma will prove that a language is irregular, but I want to prove that it is regular, and the converse of the Pumping Lemma doesn't hold. – camdroid Feb 19 '13 at 06:25
  • @nhahtdh: It is regular - I know what the answer is, I'm trying to understand how to arrive at it. – camdroid Feb 19 '13 at 06:29
  • Misread the question (didn't read the "at least"). If it is equal then most probably not regular. – nhahtdh Feb 19 '13 at 06:32
  • Sorry, my previous comment was wrong. The trick is that there is no unambiguous boundary between the two parts, so you can move ones into the y part. – starblue Feb 19 '13 at 07:35
  • Can you explain the notation? Obviously y is a binary number, what is 1^k? ::: My University days are long ago, but by definiton if you can represent the set by a regex it is regular (hence the name 'regular' in regular expression) – ilomambo Feb 19 '13 at 08:24

1 Answers1

6

The language you have is equivalent to this language:

B' = {1 y | y in {0, 1}* and y contains at least one 1}

You can prove that B' is subset of B, since the condition in B' is the same as B, but with k set to 1.

Proving B is subset of B' involves proving that all words in B where k >= 1 also belongs to B', which is easy, since we can take away the first 1 in all words in B and set y to be the rest of the string, then y will always contain at least one 1.

Therefore, we can conclude that B = B'.

So our job is simplified to ensuring the first character is 1 and there is at least 1 1 in the rest of the string.

The regular expression (the CS notation) will be:

10*1(0 + 1)*

In the notation used by common regex engines:

10*1[01]*

The DFA:

DFA

Here q2 is a final state.

"At least" is the key to solving this question. If the word becomes "equal", then the story will be different.

nhahtdh
  • 55,989
  • 15
  • 126
  • 162