這是常用語言嗎？如果是這樣，那麼正則表達式是什麼？

Question

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

這種語言是否經常？如果是這樣，你如何證明它，以及如何用Python中的正則表達式來表示它？

這是爲班級工作，所以如果你可以解釋你的答案背後的原因和過程，它將不勝感激。

Answer 1

你的語言是等同於這種語言：

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

可以證明，B「是B的子集，因爲在B中的條件」是與B相同，但其中k爲1

證明B是B'的子集涉及證明B中的所有單詞，其中k> = 1也屬於B'，這很容易，因爲我們可以拿走B中所有單詞中的前1，並設置y成爲字符串的其餘部分，那麼y將總是包含至少一個1.

因此，我們可以得出結論B = B'。

---

因此，我們的工作簡化爲確保第一個字符是1，至少有1 1在字符串的其餘部分。

正則表達式（CS表示法）將是：

10*1(0 + 1)* 

在以共同正則表達式引擎中使用的符號：

10*1[01]* 

的DFA：

這裏q2是最終狀態。

「至少」是解決這個問題的關鍵。如果這個詞變得「平等」，那麼故事會有所不同。