0

クラスの宿題に取り組んでいて、この質問に行き着きました：

次の正規表現のそれぞれについて、表現で定義された言語にない最小限の長さの文字列を指定します。

  1. (bb)*(aa)*b*
  2. a*(bab)*∪b∪ab

私は最初のものについてのみ助けを得ようとし、2番目のものを理解できるかどうかを確認します. 私が知っていることは次のとおりです。Kleene * は、0 個以上の可能な要素を示します。集合の和集合は、集合 a と集合 b のすべての要素を含み、要素を繰り返さない集合です。ラムダを挿入することから始まる最初の問題に取り組むと、次のようになります。

1 回目: bbaab
2 回目: bbbbaabaabbaabbbbaab
3 回目: bbbbbbaabaabbaabbbbaabaabbbbaabaabbaabbbbaabbbbbbaabaabbaabbbbaab

長さが 0 から 5 の文字列よりも正しく実行している場合、言語には含まれていません。私はこれを正しくやっていますか？

4

1 に答える 1

3

最初の正規表現は、偶数の「b」（ゼロを含む）、偶数の「a」（ゼロはOK）、その後にいくつかの「b」で始まる任意の単語に一致します。

これは、空の文字列と文字列「b」がその言語に含まれていることを意味します。ただし、文字列「a」はその言語ではありません。

したがって、言語にないすべての最小長の文字列は「a」です。

2番目の正規表現は、「」、「a」、「aa」（a *（bab）*による）、および「b」と「ab」で一致します。ただし、「ba」と「bb」では一致しません。

したがって、最小の文字列の長さは2：「bb」と「ba」です。

于 2012-02-15T06:17:02.983 に答える