問題タブ [automata-theory]

言語 L = {w | w を受け入れるチューリング マシンを設計しようとしています。a ⁿ b ²ⁿ } ここで、∑ = {a, b}。

たとえば、マシンは「aabbbb」という入力を受け入れますが、「aabb」は受け入れません。

私のコードはその言語について以下にあります。

問題は、これはチューリングマシンですか? または、チューリングマシンでスタックを使用できますか?

ありがとうございました

私は現在、オートマトンの理論のコースを受講していますが、次の問題が発生しました。私は1番目の質問の答えを思いつきましたが、2番目の質問のステートメントについて混乱しました.

(i) S = {aa,b} である言語 S* の再帰的定義を与えます。

ステップ 1: Lamba、aa、b は S にあります。

ステップ 2: x が S にある場合、bx と xb も S にある。

私は私の答えを確認したいです。

そして、次の質問は私が完全に混乱しており、答えを出すことができません。

(ii) T = {w1, w2, w3, w4} という言語 T* の再帰的な定義を与えてください。ここで、これらの w は特定の単語です。

私は正式な言語のクラスにいて、文法のクイズを控えています。みたいなのが出てくると思います。

アルファベット ∑ = {a, b, c} を考えてみましょう。言語 L = {bab^nabc^na^p : n ≥ 0, p ≥ 1} を生成する文法を構築します。開始変数を S とします。

2 つの正規表現が同等であることを証明しようとしています。同じ言語を定義している場合、2 つの正規表現が同等であることはわかっています。しかし、DFA を使用せずにそれを証明する方法はありません。

たとえば、次のものが同等であることを証明する問題があります。

これらは両方とも、少なくとも 1 つの 'a' と 1 つの 'b' を持つ言語を定義していることを知っています。

以下も同様です。

どんな助けでも大歓迎です。

ありがとう

正規言語 L の単語の反転も正規であることを示す

この質問にどのようにアプローチするかについて私は混乱しています。何時間も立ち往生しています。単語 x の場合、x^r を使用してその逆を示します。言語 L の場合、L^r を使用して {x^r (x は L のセット内)} を表します。L が正則なら L^r も正則であることを示す