問題タブ [formal-languages]

質問は次のとおりです。

次のことを示します。

L = {0m1n, m > 1, n > 1, n < m }、ここで m & n は上付き文字です

規則的ではありません。

この状況で上付き文字が何を意味するのかわかりませんか? 次のような意味ですか？

PS SOで上付き文字を表示するにはどうすればよいですか??

以下で構成される言語の正規表現を作成しようとしています。

• 任意の数の a の後に 1 つの b と
• 任意の数の a の後に 1 つの b が続き、その後に偶数の a が続く文字列。

と思い(b | ((a^+)b)^* ) U (a | ( (b^+) a)* )ましたが違いました。

どこが間違っているか知っている人はいますか？

文字列が文脈自由文法の一部であるかどうかを検証するにはどうすればよいですか? 仮想だけでなく、そのためのアルゴリズムを構築しますか?

次のような規則を持つ文脈自由文法が与えられた場合、

• V-> v1v2
• v1->1 | 1v1
• v2-> 2 | 2対2

これが言語 1^n 2^n であることは明らかです。しかし、実際にそうであるかどうかを検証するアルゴリズムをどのように使用しますか。私はJavaでこれを達成しようとしています。

Formal Languages と Automata Theory を勉強していますが、本の中で答えられていない問題について質問があります。質問は：

この言語はコンテキストフリー、レギュラー、またはコンテキストセンシティブですか?

L= {a ⁿ w w ^R b ⁿ | w は ( a+b )*、w ^Rは w の逆、n>=0 }

この言語は状況依存だと思います。受け入れるには少なくとも 2 つのスタックが必要だからです。

誰もそれについてコメントできますか？

ありがとう。

言語とオートマトンに関する本を読んでいますが、チューリング マシンについて理解していません。DFA の NFA と Pushdown Automata については独学で問題なく学習できました。誰かがこれが何をしているのか説明してもらえますか?

B = {w#w|w ∈ {0, 1}*}

次の図には、入力 011000#011000 で開始されたときにステージ 2 と 3 で計算している Ml のテープのスナップショットがいくつか含まれています。

どうもありがとう！

1 つの問題を解決しようとしていますが、1 つの問題を解決するためのヒントが緊急に必要です。

以下の言語が文脈自由であることを示すために、union の下でクロージャーを使用します。

{a ^m b ⁿ c ^p d ^q : n=q または m <= p または m+n=p+q }

これがオーバーフローに属していない場合は申し訳ありませんが、今年の大学で Z を学ぶようになったので、Z を使用して仕様を作成し続けたいという強い衝動があります。

LinuxまたはSunOSで通常使用されていることを現在理解しているため、Mac PCでダウンロードできるかどうかを知りたかったのですが、自宅にはどちらもありません。グーグルで見つけられなかったので、ダウンロードできる場所へのリソースを大いに感謝します。zans animator と ztc type checker もインストールしたいです。

前もって感謝します。

言語は { A ⁿ B ⁽²ⁿ⁾ C ⁿ | ここで n>=0 }

A をプッシュ、B をプッシュ、C がスタックから 3 回ポップされるたびに、C がなくスタックが空の場合は true を返し、それ以外の場合は false を返します。