CODEWITHSUNDEEP
regexcomputer-scienceregular-language
camdroid
camdroid

Reputation: 524

Is this a regular language? If so, what is it's regular expression?

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.

Upvotes: 0

Views: 2166

Answers (1)

nhahtdh
nhahtdh

Reputation: 56809

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.

Upvotes: 6

Related Questions