問題タブ [finite-automata]

次の正規表現の同等性は真ですか? なぜですか、そうでないのですか？

(ab)* u (aba)* = (ab u aba)*

*=クリーネスター

u=Union (集合論)

(ab u aab u aba)*

私はそれをしましたが、その正しさについてのフィードバックが欲しいです:

正しければ: (ab u aab u aba)* をさらに単純化できますか?

そうでない場合: 何を見逃しましたか?

編集: 3 つの最終状態すべてから初期状態に戻る e トランジションが欠落しているようです。e トランジションで古い初期状態に移動する初期および最終の新しい状態が必要です。（クリーネスタールール）。

PS と を単純化することもできます(a u b)*aababか(a u b)*a(a u b)(a u b)(a u b)(a u b)。

単純化/最小化する方法がない場合、非常に長いDFAになるため、私が尋ねる理由...

明らかな選択は、すべての可能な入力を使い果たすことです。私はやったと思います。しかし、それが有効かどうかはよくわかりません。また、非決定性有限オートマトンの規則に違反していません。

私のNFAは次のように与えられます：(ab u aab u aba)*そして以下は私の図です。

私は何かを逃したことがありますか？

(E0*0*EUE1*E) になると思いますか? ここで、E は私のアルファベットのセットで、少なくとも 2 つの 0 と少なくとも 1 つの 1 があります

言い換えれば、なぜ私はそれについて学ぶ必要がありますか？いつ言うつもりですか...ああ、私はこれのためにオートマトンまたはチューリングマシンを押し下げることについて知る必要があります。

素材の用途がわかりません。ありがとう

行き詰まったように感じます、友達。「Pearls of Functional Algorithm Design」の第 11 章 (「最大セグメント合計ではない」) から方程式を選ぶことを誰かが説明してくれますか?

ここに問題があります (少し単純化されています) 与えられた遷移を持ついくつかの状態を考えてみましょう:

それでは、pick を定義しましょう。

著者は、次の 7 つの方程式が成り立つと主張しています。

誰か簡単な言葉で説明してくれませんか?なぜこれらの方程式が正しいのか、明らかな証明をどのように証明できるのでしょうか? S 方程式はほぼ理解できたように感じますが、全体としてこれはとらえどころのないままです。

私の C は少し不安定ですが、python のソース コードを調べたところ、ほとんどの python のreモジュールはステート マシンによって実装されているようです。正規表現は決定論的な有限状態マシンに還元できるため、これは当然のことです。

他の正規表現の実装も似ていると思います。しかし、現代の正規表現の実装が、教科書の定義に従って規則的であるものは、あるとしてもほとんどありません。では、後方参照などの不規則性をどのように説明するのでしょうか?

ファイルを解析するために独自のfsmを実装しています。私はfsmパターンに慣れていないので、それについて学ぼうとしています。

私のfsmクラスは、現在の状態とすべての受け入れ状態のコレクションとともに解析されているファイルのストリームを取得します。

今、私はいくつかのことについて混乱しています。

1. fsmはどのように状態を移動し、これまでに解析されたものを追跡しますか？

2. 状態オブジェクトはどのような情報を保存する必要がありますか？現在、それらはライン上で一致するパターンを持っており、fsmがこの状態に移行できるかどうかを確認します。

例：

解析するファイル：

ですから、私には、人の開始、年齢、場所、および終了者の状態があります。各状態オブジェクトにはパターンがあります。（正規表現）指定された行が受け入れられるかどうかを確認します。

しかし、fsmを使用してこのファイルを解析するときにPersonオブジェクトをどのように構築するのかということに固執していますか？

私はこの答えに近いと思いますが、それでも確認するために、実数の計算に取り組み、正確な結果を得ることができるチューリングマシン（少なくとも原理的には）を作成できますか？**たとえば、整数の平方根を見つけます。（その出力は実数になります）そのようなマシンを開発できないという私の論理は、実数は数え切れないほど無限であり、数え切れないほど無限の言語ではチューリングマシンを作成できないということです。

右から5番目の記号として「1」を持つ文字列を受け入れるためにDFAで必要な状態の最小数はいくつですか。文字列はアルファベット{0,1}の上に定義されます。