問題タブ [pushdown-automaton]

このPDAを作成する必要がありますが、文字列インデックスxiおよびyiを追跡する方法について混乱していますか？前もって感謝します

{x＃y|を受け入れるPDAを構築します x、y in {0、1} *で、一部のiについてx≠yおよびxi = yi、1≤i≤min（| x |、| y |）}。

私はC＃で働いています

正規表現言語で特定の文字の関数を呼び出せるようにしたいのですが、これが可能かどうか疑問に思っていました。たとえば、7 が見つかったときに^[0-9]*$関数を呼び出したいので、パターンがあるとします。foo()したがって、文字列がある場合、関数は3 回"0129384927377"呼び出されます。foo

これを行う方法はありますか？

コンテキストが必要な場合は、DPDA (決定論的プッシュダウン オートマトン)をできるだけ簡単に構築しようとしていますが、それを行う最善の方法はわかりません。

PDA（プッシュダウンオートマトン）は、その言語の任意の文字列wに対して、スタックの方向を最大でk回回転させる場合、k回転であると言われます。また、言語Lは、1ターンのPDAによって受け入れられる場合は線形であることもよく知られています。さて、正規言語は0ターンのPDAによって受け入れられる言語であるというのは本当ですか？

{WW}-決定可能だが文脈自由ではない
{WW^R}-文脈自由だが正規言語ではない
Σ*-正規言語
どのクラスに属しているかをどのように判断できますか？

PDA が同じ長さの 0 と 1 の 2 つのブロックを比較し、後で使用するためにその長さを記憶できる可能性がないため、この言語は文脈自由ではないと思います。

残念ながら、それを証明する方法はわかりません。

ポンピング補題を使ってみましたが無駄でした...

私はまた、言語が文脈自由であると矛盾して仮定し、文脈自由言語と正規言語との共通部分も文脈自由であるという事実を使用しようとしました (神秘的な正規言語 L を見つけることによって)。 ) - 私のすべての努力は無駄でした...

どんな助けでもいただければ幸いです

これはこれの繰り返しですが、私はPDAの設計に関して話します。

これはよく知られている例であるため、私は間違っていることを知っていますが、以下のPDA設計でどこが間違っていたのでしょうか。

言語を受け入れたい{a^n b^n c^n: n>=0}

1に遭遇するたびにスタックに2つプッシュしa、1つをポップし、1つをbポップしcて、スタックが空かどうかを確認します。遷移関数（最小）を次のように定義しました：

(q0, a, Z) = (q0, 11Z)
(q0, a, 1) = (q0, 111)
(q0, b, 1) = (q1, delta)
(q1, c, 1) = (q2, delta)
(q2, delta, Z) = (q-Final, Z) (epsilon move)

Z is empty stack

このPDAはそのような言語を受け入れませんか？

私は最近、事前に作成した有限オートマトンに基づいたプッシュダウン オートマトンを作成するタスクを設定されました。（私は実際にはうまくいきませんでした。そのため、家庭教師から作業コピーが渡されました）

両方の図に含まれている部分がわかりません。

「最初は、矢印が状態に結合されているときに矢印が正確に何を意味するのかということです。これは、事前に入力された言語 (私の場合は 0-9) が正しいことを確認していると考えてよろしいですか? (この矢印は終末状態を指しています)""

私は自分の研究を試みましたが、残念ながら、基本的な用語でそれを本当に説明できるものは何も思いつきませんでした.「ダミーのための有限オートマトン」を試してみました. また、回答があり、何もない可能性のある質問も確認しました。

.Net で CASIO DTX30 用のアプリケーションを開発するにはどうすればよいですか?