regex - これらの言語の正規表現を作成しますか?

Question

アルファベット Σ = {0, 1} の次の言語はすべて正則です。

L = { w | w は偶数の長さで、01 で始まります }

L = { w | w の 1 の数は 3 の倍数です }

L = { w | w には部分文字列 10 が含まれていません }

これらの言語の正規表現を書くように頼まれましたが、その方法がわかりません。これらの問題にアプローチする方法について誰かアドバイスをもらえますか?

Answer 1

ここにいくつかのヒントがあります：

1. (0 ∪ 1) は「0 または 1」を意味し、(0 ∪ 1)(0 ∪ 1) は「任意の 2 文字の文字列」を意味します。それらの式の 2 番目からすべての偶数長の正規表現を作成できますか? そこから必要な言語に到達する方法がわかりますか?

2. 3 の倍数である 1 の数を持つ任意の文字列は、小さな文字列の束に細分化できます。各文字列は、0 が点在する 3 つの 1 で構成されます。ちょうど 3 つの 1 を含むすべての文字列を作成できますか? そこから、必要な言語を取得できますか?

3. これは実際には最も簡単です。10 を含まない文字列をいくつか書き出してください。ヒントとして、これを 4 文字で行うことができます。

お役に立てれば！

Answer 2

L = { w | w は偶数の長さで、01 で始まります }

答え: 01((0 + 1)(0 + 1))*

説明:それ自体は偶数の長さであり、 s とs01で構成される偶数の長さの文字列にサフィックスを付けることができます。01

L = { w | w の 1 の数は 3 の倍数です }

答え: (0*10*10*10*)*

説明:0文字列のどこにでも何回でも出現する可能性があり1ます。 *1

L = { w | w には部分文字列 10 が含まれていません}

答え: 0*1*

説明: 文字列に含める10ことはできません。つまり、任意の後にのみ1許可されます1。