問題タブ [nfa]

これが私のNFAです。

これが私の試みです。

• 新しい開始ノードと最終ノードを作成します
• 次に、左から2番目のノードを削除します。
• 次に、右から2番目のノードを削除します。これによりab*aが得られます。
• 次に、左から2番目のノードを削除します。これによりabb*bが得られます。
• 次に、右から2番目のノードを削除します。これによりb + ab*aが得られます。

これはabbb （b + ab a）*につながります

これは正解ですか？

NFA を使用して否定正規表現を実装しようとしています。

ab a|bNFA はとのような正規表現を簡単に組み合わせることができることを知っています。a*

そしてその多様[ab]性はに変換することができますa|b

[^ab]しかし、どうすればNFAフラグメントに変換できますか?

文脈自由文法: (e はイプシロンを表します)

それは正しい線形文法に変換できることを意味する通常の言語を生成できます。CFG を RLG に変換する一般的なルールはありますか?

RegEx を補完するために、DFA ダイアグラムと RegEx を表示するよう求められ(00 + 1)*ます。前の問題では、DFA の補数が閉じており、正規表現でもあることを証明する必要があったため、DFA の M を補数の M` に変換するには、最初の受け入れ状態と最終承認状態。

ただし、RegEx の最初の受け入れ状態は で{00, 1, ^}あり、最終的な受け入れ状態も{00, 1, ^}同様であるようです。したがって、それらを交換すると、まったく同じ RegEx と DFA が得られ、矛盾しているように見えます。

私は何か間違ったことをしていますか、それともこの正規表現には実際の補数がないはずですか?

ありがとうございました

変換の仕方が分からなくて困っています。

2 が 'a' の入力を取得した場合、空の文字列のために (1,4) または (1,2,4) になりますか?

ありがとう！

あるポイントから別のポイントに省略形がスキップされるメソッドを作成しようとしています。

現在のエッジでNFAを作成しました

私が達成しようとしていることの例は nrec("h-rd", nfa, 1)戻るべきですaccept

nrecNFAの文字列を処理し、それが受け入れるか拒否するかをチェックするメソッドです。

アカウントに略語を使用するメソッドを追加する必要があります。ある状態から別の状態にスキップする方法がよくわかりません。これは、クラスNFAに含まれるものです。

私はabrsの使用について考えましたが、次のような独自のabrsを定義しようとすると、常にエラーが発生します。

「TypeError：init（）が予期しないキーワード引数'abrs'を取得しました」というエラーを受け取りました。なぜそのエラーを受け取ったのですか？

変更のために私はこのようなことをするだろうと思った

賢い選択またはより良い解決策？

このnfaで略語を使用して、ある状態から別の状態に移行しようとしています。

NFAは次のように定義されます

文字列を処理するときにこの内部メソッドを作成しました。

test print =>を試してみるとprint nrec("h:d", nfa, 1)falseが返されます。これは、状態を作成していないということです。-signが表示されたら、これらすべての状態を与える必要がある:例からの状態を作成したい=> 、このタスクを実行するためにこのメソッドを変更するにはどうすればよいですか？これは、構造を作成した後に文字列を処理する定義済みのメソッドです。("h:z")('h'->'a'->'z'->'a'->'r'->'d')NFA

省略形を正しく機能させるにはどうすればよいですか？それはtrueを返しますか？

テスト文字列に一致するように、特定の正規表現からDFAを作成しました。発生する場合があり.*ます。（たとえば.*ab）。ここで、マシンが状態1にあるとします。DFAでは、 .*すべての文字のそれ自体への遷移と、状態1から「a」へのaの別の遷移を指します。テスト文字列に「a」が含まれている場合、状態1から、マシンはDFAでは不可能な2つの状態に移行する可能性があるため、遷移となる可能性があります。