Search code examples
regexcomputer-scienceregular-language

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.

Solution

  • 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.