問題タブ [automata]

言語A= {a^mb^n |を認識する PDA を構築するタスクがあります。m > n} with ∑ = {a, b} ..どうすればいいのか少し混乱しています..この質問を解決するのを手伝ってくれませんか? ありがとう

解析する必要がある不適切な形式の XML があります。上流で問題を修正することはできません。

(現在の) 問題は、アンパサンド文字が常に適切にエスケープされるとは限らないため、次のように変換する必要があることです&。&

が既にある場合&は、に変更したくありません&。一般に、整形式のエンティティが既にそこにある場合、それを破棄したくありません。一般に、特定の XML 文書に現れる可能性のあるすべてのエンティティーを知ることは不可能だと思います&<characters>;。

<characters>イニシャル&とクロージングの間のエンティティを定義する文字のセットはどこにありますか;。特に、<and>は、そうでなければ XML 要素を表すリテラルではありません。

ここで、解析中に&<characters>、;a (スペース)、行末、または別の&. <characters>なので原作をどうするか教えてくれるキャラクターを先を見ながら覚えておかなければいけないと思います&。

これを行うには、プッシュ ダウン オートマトンの力が必要だと思います。メモリ要件があると考えられるため、Finite State Machine が機能するとは思いません。それは正しいですか? PDA が必要な場合、呼び出しの正規表現は機能しString.replaceAll(String, String)ません。または、この問題を解決できる Java 正規表現はありますか?

注意: 1 行に複数の置換がある可能性があります。

(私はこの質問を認識していますが、私が探している答えを提供していません。)

cellualr Automata を使用して、グラフ (有向) 内のノードの到達可能性をテストできますか? 実際に考えているのは、CA を使用して、指定された頂点からノードの到達可能性をチェックするアルゴリズムを実装することです。それは可能ですか？CAはそれを行うことができますか？

何か案が？

足し算がプリミティブ再帰的であることを数字の例で示すにはどうすればよいですか。

証明を通してプリミティブ再帰的である理由は理解できますが、数字でプリミティブ再帰的にどのように機能するか想像できません。

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

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

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

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

この質問で述べたように、DFA を使用してすべてのコメント、文字列などを追跡しています。この DFA は 11 の状態で終了しました。

今、Java でキーワードを認識する DFA を作成しようとしています。

考え：

最初は pos=0 です。pos は遷移ごとに 1 ずつインクリメントされます。

iskeyword() は私自身の関数です。

isalnum() は、将来の要件に応じて、任意のユーザー定義関数に置き換えることができます。

(実際の DFA には存在しますが、関連のない多くのトランジションとセルフ ループは提供されません)。

(q0) -- !isalnum(pos)-------> (q1) ---iskeyword(pos,pos+len)---> (pos+=len)(q2)----- ! isalnum(pos)-------->(q3[読み取ったキーワードをBOLDにする])---iskeyword(pos,pos+len)-->(q2).

少なくとも 4 つの州が必要です。上記の方法は、通常の DFA の実装とはかなり異なります。

私の質問は....

1. 上記の方法でよろしいでしょうか？それに従うのは正しいですか？（それが機能する場合）
2. 上記の方法でこれを実装する必要がある場合、どうすればそれを行うことができますか? 読みやすさを向上させるために別の DFA を構築しますか? または、このDFAをコメント、文字列を認識するDFAと組み合わせることができますか（状態の数を減らすため）

NFAを設計し、JFLAPを使用してDFAに変換したシナリオがあります。

Javaでコーディングする方法を知る必要がありますか？

基本的に、Javaでこれらの状態遷移を実装する方法。switchステートメントとifステートメントを使用してこれを行う例をいくつか見てきましたが、DFA / NFAの設計と、それを使用してJavaで実装する方法との関係はわかりません。

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

プレゼンテーションのために、有限オートマトンのアプリケーションからトピックを選択する必要があります。コンピュータ サイエンスにおける有限オートマトンの応用例は何ですか? 彼らはプログラミングをしているかもしれません。