構造一個正則表達式以匹配以下語言

Question

我正在研究由教授在講座結束時發佈的思考練習。問題在於給定特定的語言定義來構建DFA。在構建DFA之前，第一個思考練習是將語言定義轉換爲正則表達式。

所提供的字母是二進制數{0，1}

該語言定義是相當非正式：

定義所述一組二進制串中長度爲3的每個子串具有作爲語言至少一個零

所以符合這個定義的字符串的例子是000，001，1010等等。

我的麻煩是提出一個正則表達式來匹配這個語言定義。我試着在http://regexr.com/上玩，但我只發現'..0'在結尾處每三個字符匹配一個零。我不確定如何按照語言定義的方式匹配每個子字符串，或者甚至可能。

有沒有辦法爲這個問題構造一個正則表達式？

Answer 1

需要橫向思維。不要爲非正式語言定義實現正則表達式，而是爲該定義所暗示的屬性實現。

擾流板（懸停在它的溶液）：

提示1：

如果任意3-長度子必須具有一個0 - 數位，那麼它不可能有連續3位數字，即1 -digits。

提示2：

這意味着每個0之間 - 數位存在的1 -digits至多2。

提示3：

這使得其中後0-2 1 -digits，有自帶基團組成的0 - 數位的一個可能是無限量的語言和0-2 1-數字。

解決方案：

^1{0,2}(01{0,2})*$，或等價多數學，^(11?)?(0(11?)?)*$