regex - アルファベット {a, b} の上に部分文字列 aba を含む文字列の正規表現を見つけますか? (形式言語論)

Question

質問は、アルファベット {a, b} の上に部分文字列 aba を含む文字列の正規表現を見つけることを求めています。

これは、正規表現が次のようになるように、何でも aba に先行/先行できることを意味しますか?

(aUb)*(aba)*(aUb)*

または、質問は単に探しています:

(aba)*

注: U は結合を意味し、* は 0 回以上を意味します。

Answer 1

* は 0 以上を意味するので、ε は第一言語にありますが、必要ありません (aba は含まれません)。を探してい(aUb)*aba(aUb)*ます。

Answer 2

部分文字列は次のように定義されます

名詞

長い文字列の一部である文字列

また、2 番目の式は最初の式のサブセットであることに注意してください。

Answer 3

前者:aba少なくとも 1 回含まれる任意の文字列。