問題タブ [automata]

次の言語を認識するPDAを作成します：bよりも多くのaを含む文字列の言語

私はこの質問に数日間苦労してきました、私は完全な精神的ブロックにぶつかったようです。この問題をどのように解決できるかについて、誰かがガイダンスや指示を提供できるでしょうか？

私は完全に立ち往生しているポンピングレンマの質問があります...

L = {w ∈ {a, b, c}∗ : na (w) < nb (w) < nc (w)}

それはCFLですか？

これらの条件をすべて記憶するには、1 つのスタックだけでは十分ではないため、CFL ではないと考えています。na (w) < nb (w) または na (w)< nc (w),nb (w) < nc (w) であることを思い出すことができますが、na (w) < nb (w) < nc (w) ではありません。さらに、言語が a^pb^2pc^3p の場合と、|vy| の場合よりも p 回 L は CF ではありませんが、p 回ポンプアップすることは可能ですか?

または解決策のアイデアはありますか？

正規表現/オートマトンのヘルプを探しています。私は+またはクリーネスターに限定されています。3 進数 (2 進数のように 3 のみ) を表す文字列を解析する場合、結果が 1 から 4 の倍数より小さいかどうかを知る必要があります。

たとえば、120 = 0*1+2*3+1*9 = 9+6 = 15 = 16-1 = 4(n)-1.

パターンへのポインタでさえ本当に役に立ちます!

私はエッジとサーキュラー状態でオートマトンを描きたいと思っています。このような ものhttp://pop-art.inrialpes.fr/~girault/Cours/Automates/td5.html

文脈自由言語のコレクションの和集合は常に文脈自由ですか？あなたの答えを正当化してください.....

答えがイエスであることは知っていますが、どうすればそれを証明できますか？

if-elseアプローチとグラフアプローチを使用してDFAを実装できることは知っていますが、それらを実装する他の方法はありますか？実際、私は正規表現用のJavaCode Generatorを作成しています。これまで、2つの可能なアプローチ（if-elseとグラフアプローチ）を実行しましたが、より多くの可能な方法を提供したいと思います。トランジションのセットまたはマップとしていくつかのデータ構造を使用して実装できると思います。

1つの単純なプログラミング言語用のレクサーを作成しました。現在、正規表現（JavaではRegEx）の代わりに、決定性有限オートマトンを使用しています。オートマトンは、たとえばソースコードにmoduleclouds（モジュールとクラウドの両方がキーワード）がある場合にエラーを報告しないことを除いて、うまく機能します。代わりに、KW_MODULEとKW_CLOUDSという2つのトークンを作成します。オートマトンがKW_MODULEの最終状態にある場合、空白を先読みできると主張する人もいるかもしれません。しかし、それでは問題は解決しません。言語では、8-6（空白で区切られていない）のようなものがあり、トークンINTDASHINTに正しく変換される可能性があるためです。

パーサーの文法で空白を処理するのは良い考えではないことを私は知っています。

私のオートマトンはマトリックスとして実装されています（行は状態、列はアルファベットの文字、セルは遷移状態です）。オートマトンが最終状態になったら、オートマトンをリセットして開始状態から開始します。

問題は、このプログラミング言語がセミコロンを使用していないためだと思います。例えば：

モジュール; 雲;

代わりに、線を区切るために空白を使用します：モジュールクラウド

前もって感謝します。

よろしく。

PL/SQL、SQL92、SQL99 などの SQL の有限ステート マシン定義があるかどうかは誰にもわかりません。

SQLの文法定義があるかどうかわからない..

L をアルファベット {0,1} の文字列で構成される言語とし、1 と 0 を同数含む。

例えば：

L が正規言語ではないことをどのように証明できますか?

私はこの運動をしなければならず、その方法について完全に困惑しています。以前にいくつかのFAを作成しましたが、2進数を使用しています。どうすればこれを行うことができますが、10進数でも可能ですか？