問題タブ [finite-automata]

Perl で「正規表現」と呼ばれる文字列を解析するためのエンジンは、本で「正規表現」という用語で知られているものとは大きく異なります。

それで、私の質問は次のとおりです。Perlの正規表現の実装と、それが古典的なものと実際にどのように、どのように異なるかを説明するドキュメントはありますか（古典とは、通常のDFA / NFAに実際に変換できる正規表現を意味します）、どのようにできます？

ありがとうございました。

決定論的なスタックオートマトンをシミュレートする必要があるUVAの演習を読んで、特定の文字列が次の形式の特定のエントリでDSAによって受け入れられるかどうかを確認しました。

入力の最初の行は、テストケースの数を示す整数Cになります。各テストケースの最初の行には、5つの整数E、T、F、S、およびCが含まれています。ここで、Eはオートマトンの状態の数、Tは遷移の数、Fは最終状態の数、Sは初期状態、 Cそれぞれテスト文字列の数。次の行には、オートマトンの最終状態を表すF個の整数が含まれます。次に、それぞれ2つの整数IとJ、および3つの文字列L、T、Aを持つT行が表示されます。ここで、IとJ（0≤I、J <E）は、それぞれ遷移状態の起点と終点を表します。Lは、テープからトランジションに読み取られた文字を表します。Tはスタックの一番上にあるシンボルを表し、Aはこの遷移の終わりにスタックの一番上で実行するアクションを表します（パイルの一番下を表すために使用される文字は常にZです。文字列、または遷移文字のスタックの最上位を考慮しないアクションをアンスタックします£）。スタックのアルファベットは大文字になります。チェーンAの場合、シンボルは右から左にスタックされます（プログラムJFlapと同じ方法で、つまり、スタックの新しい一番上が左側の文字になります）。次に、それぞれに入力文字列が含まれるC行が表示されます。入力文字列には小文字と数字を含めることができます（必ずしもトランジションに存在する必要はありません）。または、遷移文字のスタックの最上位を考慮しないアクションをアンスタックします£）。スタックのアルファベットは大文字になります。チェーンAの場合、シンボルは右から左にスタックされます（プログラムJFlapと同じ方法で、つまり、スタックの新しい一番上が左側の文字になります）。次に、それぞれに入力文字列が含まれるC行が表示されます。入力文字列には小文字と数字を含めることができます（必ずしもトランジションに存在する必要はありません）。または、遷移文字のスタックの最上位を考慮しないアクションをアンスタックします£）。スタックのアルファベットは大文字になります。チェーンAの場合、シンボルは右から左にスタックされます（プログラムJFlapと同じ方法で、つまり、スタックの新しい一番上が左側の文字になります）。次に、それぞれに入力文字列が含まれるC行が表示されます。入力文字列には小文字と数字を含めることができます（必ずしもトランジションに存在する必要はありません）。

各テストケースの最初の行の出力には、次の文字列「Case G：」が表示されている必要があります。ここで、Gはテストケースの数（1から始まります）を表します。次に、オートマトンが文字列を受け入れる場合は「OK」、それ以外の場合は「拒否」という単語を印刷するC行。

例えば：

これは出力です：

助けが必要です。または、このDSAをシミュレートする方法についてのアイデアが必要です。自分でコードを作成したいので、問題を解決するコードを求めていません（アイデアは正しく学習することですか??）が、助けが必要です。 （いくつかのアイデアまたは擬似コード）実装を開始します。

私はFSMを使用していくつかのメニューを作成しましたが、非常に不格好なインターフェイスを使用しています。再配置を容易にするためにプログラミングから1年の長い休憩を取り、今夜、古いFSMコードを書き直しました。

ここで見ることができます

私のコードの問題は、実装を変更するたびに、StateMachineクラスとイベントプロセッサを大幅に作り直す必要があることです。これは組み込みデバイス上にあるため、BOOST :: FSMを使用できないため、メニューやプログラミングの真数などを処理するのに十分な堅牢性を備えた独自のクラスを作成したいと思います（たとえば、PICのICSPは単純なFSMです）。

ステートマシンをもっと使いやすくすることをどのように勧めますか？

ステートマシンを作成し、次のようなインターフェイスを使用したい場合：

そうすれば、私がstate1にいて、FSMがKey_UPを受信すると、プログラムは次のように出力します。

問題は、プログラマーが配列サイズを変更する必要なしに、状態と遷移情報をクラス内に格納する方法です。2D配列を使用して、通常のように状態テーブルにし、移植性を高めるために、必要に応じてベクトル型を使用してサイズを変更することで、イベントと状態の追加を処理できると考えていました。ベクトルの問題は、多くの組み込みデバイスがメモリ割り当て呼び出しを使用できないことです。2番目のオプションは、ステートマシンでコンストラクターを呼び出し、テーブルに必要なサイズを渡すことですが、新しい状態やイベントを追加する場合は、これらの値も変更する必要があります...

では、状態、イベント、関数ポインタをどのように保存すればよいのでしょうか。

特定のアルファベットにいくつの異なる遷移グラフがあるかをどのように判断しますか? たとえば、アルファベット {x, y} を超える TG の数。Daniel IA Cohen の著書「Introduction to computer theory」からの同様の質問のクラスを受講しています。TG を作成する方法の例はたくさんありますが、言語ごとに作成できる数を決定するものはありません。限られた量のTGを探していると思いますか？どうもありがとうございます！

2つのオートマトン間の同等性を判断するための最良または最も簡単な方法はどれですか？

つまり、2つの有限オートマトンAとBが与えられた場合、両方が同じ言語を認識するかどうかをどのように判断できますか？

それらは両方とも決定論的または両方とも非決定論的です。

明日の試験と教授は、その上にある質問を教えてくれます:)。

この図のコンテキストでは、L はイプシロン (空の文字列) であり、Z0 はスタックの空のシンボルです。

私は言語が生成する単語に関するいくつかのルールを決定する上である程度の進歩を遂げましたが、言語全体を特定することはできませんでした.

ありがとう！

次のような基本的な操作を実行できる、Python 用の最も完全な有限オートマトン ライブラリは何でしょうか。

• 最小化、
• 非決定性有限オートマトンの決定化
• これらのオートマトンが生成する言語の和集合、交点、積など。

私が見つけたすべてのライブラリは不完全であるか、プラグアンドプレイで動作しません。

私は今、計算理論のコースを取っています。概念はよく理解できます。私は問題を解決することができます。そして、実際のアプリケーションについて講師に尋ねたところ、これらの概念はコンパイラーの設計において確実に有用であり、不可欠であるとのことでした。しかし、少なくとも有意義な調査を行うには、これらの概念をコーディングでどのように使用できるかについての説明が必要です。

たとえば、独自の grep を設計したい場合。C で文字列関数を使用します。コーディングで正規表現を使用する方法がわかりません。

同じケースがチューリングマシンにも当てはまります。

2 つの数値を追加したい場合、なぜそれらの単項概念に従う必要があるのですか。ハードウェアはそれらの概念を実装していますか?