2

{ab} をアルファベット セットとして、次の正規表現を記述します。

1) a の数と b の数が両方とも奇数であるすべての単語の言語。

2) 長さが奇数で部分文字列 ab を含むすべての単語の言語。

また、可能であれば、そのような問題を解決する方法についての理解を深めるために、それぞれの表現を 2 つ見つけてください。

4

1 に答える 1

3

最初のものについては、言語を認識するために構築できる簡単な 4 状態の DFA があります。次に、Kleene の定理 (FA によって認識されるすべての言語は RE によって生成されると彼が言う部分) から回復可能なアルゴリズムを使用して、機能する RE を取得することができます... または単に図からそれを推論します。

2 番目の例では、(ab) が RE の一部であることを知っています。ここで、奇数の文字をこれ (表または裏) に追加する独自の方法をすべて考え、これらすべての可能性を + で接続して、簡単で正しい正規表現を作成する必要があります。

ただ答えを出すという考えが特に好きな人はいないと思います。

編集：

しばらく時間が経ったので、最初の質問への回答に取り組み、関心のある読者にその方法を示します。

最初の FA は次のとおりです。

   Q s f(Q, s)
  -- - -------
  EE a     OE
  EE b     EO
  OE a     EE
  OE b     OO
  EO a     OO
  EO b     EE
  OO a     EO
  OO b     OE

これから状態を削除し、その状態をカバーするために s を正規表現に置き換えます。簡単なものから始めましょう... OE を取り除きましょう。これがそのためのテーブルです...

   Q                  regex f(Q, s)
  -- ---------------------- -------
  EE                     aa      EE
  EE                     ab      OO
  EE                      b      EO
  EO                      a      OO
  EO                      b      EE
  OO                      a      EO
  OO                     ba      EE
  OO                     bb      OO

続行する前に、これが正しいことを確信してください。次に、EO を取り除きます。

   Q                  regex f(Q, s)
  -- ---------------------- -------
  EE                  aa+bb      EE
  EE                  ab+ba      OO
  OO                  ab+ba      EE
  OO                  aa+bb      OO

次のステップを簡単にするために、新しい開始セット X と新しい受け入れ状態 Y を導入します。OOはもう受け付けていません。オブジェクト指向の必要性を排除します。

   Q                        regex f(Q, s)
  -- ---------------------------- -------
   X                        empty      EE
  EE aa+bb+(ab+ba)(aa+bb)*(ab+ba)      EE
  EE              (ab+ba)(aa+bb)*       Y

したがって、最終的な正規表現は

  (aa+bb+(ab+ba)(aa+bb)*(ab+ba))*(ab+ba)(aa+bb)*

基本的な健全性チェックと同様に、これが生成する最小の文字列をリストすることから始めます: {ab, ba, aaab, aaba, bbab, bbba, abaa, abbb, baaa, babb, ...}

各ステップで削減するためのルールを形式化することも、慎重な推論を適用して正しいことを確実に行うこともできます。慎重な分析のためにクリーネの定理の証明を確認してください。また、Martin's Introduction to Formal Languages などには、このアルゴリズムを使用した良い例があります。

于 2011-10-02T14:43:45.050 に答える