問題タブ [finite-automata]

R自明言語とは何ですか? つまり、定義は何ですか？

R自明なモノイドとは何ですか?

コンテキスト: 形式言語。確かに、R-自明な言語はスターフリー言語のサブセットです。

私は主に形式言語とオートマトン理論のバックグラウンドを持っていますが、構文的なモノイドの特徴付けについてはあまり知りません。したがって、そのような言語の小さな例で基本的な定義を示すとよいでしょう。

（QAサイトを置き去りにしたくないため、複数のQAサイトをサポートし、その質問もそこに表示するために、この質問を他のサイトにも投稿しました：cstheory.stackexchange.com、math .stackexchange.com , mathoverflow.net . 一般に、私はクロスポストに反対していますが、この場合、特定の分野の質問の完全な参照になるという同じ目標を持っているため、質問をクロスポストすることが最善の方法ですできるよ。）

それらがどのように機能するかを理解するために、単純なレクサーを作成しようとしています。あらゆるタイプのOpeningHTMLタグをキャッチできる優れたPOSIX文字列を見つけようとしています。ほぼ機能するものを作成しましたが、メタタグなどのより複雑なタグでは失敗します。これまでのところ、これは私が持っているものです：

このPOSIX文字列は多くのタグをキャッチしますが、メタタグやDOCタグなどの一部を見逃しています。失敗したタグは次のとおりです。

どんな助けでも大歓迎です。これはレクサーを作成するための最良の方法ではないかもしれませんが、これは正規表現がどのように機能するかを理解するのに役立つだけです。

与えられた 2 つの DFA の結合を構築するためのアルゴリズムの簡単な説明を誰かが持っていますか? たとえば、{0,1} に 2 つの DFA があるとします。

ユニオンを次のように示す結果の遷移テーブルがあります。

講義ノートに解決策の図を載せていますが、他の人がそれをどのように説明するかを知りたいです。このことから、状態値を使用してこれら 2 つの元のテーブルを本質的に「乗算」して、より大きな遷移テーブルを作成していることがわかります。したがって、結果のテーブルから DFA を引き出すことができます。これは正しく聞こえますか?また、すべての DFA ケースで機能するはずですか?それとも何か不足していますか?

NFA から DFA への変換アルゴリズムを SO コミュニティに簡潔に説明するよりもはるかに優れた人がいるでしょうか? (できれば 500 語以内で。) 私はかつて知っていたと思っていたことを混乱させるだけの図や講義を見てきました。状態図から最初の NFA 遷移テーブルを生成することにはほぼ自信がありますが、その後、イプシロンとサブセットで DFA を失います。

1) 遷移 (デルタ) テーブルで、新しい DFA 状態を表す列はどれですか? 生成された状態の最初の列ですか?

2) 以下の例の列 0 の行 {2,3} で、状態図に関して NFA について {2,3} は何を意味しますか? (申し訳ありませんが、写真で考えなければなりません。) そして、DFA で「入力 0 のループバック」になると思いますか?

3) テーブルから DFA への取得、または結果の DFA の受け入れ状態の認識に関する簡単な「経験則」はありますか?

有限自律

編集：これはドット形式の上記の表です。Regexidentを乾杯します。

そして、ここでレンダリングされた形式で：

注:この表には、状態の受け入れに関する情報が欠けているため、グラフにも含まれています。

反復によって解決できる解決策がある問題がありますが、正規表現とsplit()

本質的にコンマで区切られた文字列（Excelがクリップボードに入れている）があります。セル値にコンマが含まれている場合、セル全体が引用符で囲まれていることに注意してください (おそらく、その文字列内のコンマをエスケープするため)。文字列の例は次のとおりです。

さて、この文字列を個々のセルにエレガントに分割したいのですが、値にコンマを含むセルを分割するため、コンマを区切り文字として使用する通常の分割式を使用できないという問題があります。この問題のもう 1 つの見方は、コンマの前に偶数個の引用符がある場合にのみ、コンマで分割できるということです。

これはループで解決するのは簡単ですが、このロジックをキャプチャできる正規表現.split関数があるかどうか疑問に思っています。この問題を解決するために、ロジック用の決定論的有限オートマトン (DFA) を構築しました。

問題は次のようになります: DFA で最終状態 (ここでは状態 4) に到達するたびに新しい配列要素 (/s に対応) が生成されるように、この文字列を分割する方法はありますか?

有限オートマトンから正規表現を作成しようとしていますが、自分自身がこれに完全に固執していることに気づきました。使用する正規表現は次のようになります。

？=0または1
*=0以上
+=1以上
| =または
_=空の文字列
@=空のセット
（）=括弧

私が理解しているように、文字列は「b*」で終わる「a*」または「a+ bb +」で終わる必要があります。
私が今持っているのは((b*(a+(bb))*)*) 、「a」で終わる文字列を考慮していません。

言ったように、私はこれに100％立ち往生していて、これをどのように扱うべきかについて頭を悩ませることはできません。

画像： http： //img593.imageshack.us/img593/2563/28438387.jpg

コード：
オートマトン
FA のタイプ

状態
q1q2q3
q4
_
_

アルファベット ab
_

初期状態
q3

最終 状態
q3q4

遷移
q1aq2
q1 b q3
q2 a q2
q2 b q2
q3 a q4
q3 b q3
q4 a q4
q4 b q1

解決策やヒントをいただければ幸いです。

有限状態変換器とは何か教えてください。

ウィキペディアの記事を読みましたが、何もわかりません。

I was reading a book named "An introduction to Formal Languages and Automata" by Peter Linz. In one of it's questions, it asked me to, "Design an acceptor for integers in a programming language C" Can some one please tell me how can I obtain an answer for this. Any help would be greatly appreciated

アルファベット { a } を持つ言語Lの定義は、次のように与えられます。

L = {a ^nk | k > 0; n は正の整数定数です }

Lを認識するために DFA で必要な状態の数は?

私の意見では、k + 1 にする必要がありますが、よくわかりません。

非決定論的有限状態オートマトン (NFA) を決定論的有限状態オートマトン (DFA) に変換するプログラムに取り組んでいます。これを行うには、イプシロン遷移を持つ NFA 内のすべての状態のイプシロン クロージャを計算する必要があります。私はすでにこれを行う方法を考え出していますが、私が最初に考えるのは、通常、何かを行う最も効率の悪い方法であると常に想定しています。

単純なイプシロン クロージャを計算する方法の例を次に示します。

遷移関数の入力文字列: 形式は startState、symbol = endState です。

EPS はイプシロン遷移です

1、EPS = 2

新しい状態 { 12 } になります

明らかに、これは非常に単純な例です。任意の数の状態から任意の数のイプシロン遷移を計算できる必要があります。この目的のために、私の解決策は、イプシロン遷移がある状態を見て、指定された状態のイプシロン クロージャーを計算する再帰関数です。その状態にイプシロン遷移がある場合、関数は for ループ内で、イプシロン遷移と同じ数だけ再帰的に呼び出されます。これで作業は完了しますが、おそらく最速の方法ではありません。だから私の質問はこれです:Javaでイプシロンクロージャーを計算する最速の方法は何ですか?