regex - これは正規語ですか？もしそうなら、それは正規表現ですか？

Question

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

この言語は規則的ですか？もしそうなら、それをどのように証明し、それを Python の正規表現でどのように表現しますか?

授業用ですので、その理由と経緯を教えていただけると助かります。

Answer 1

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:

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.