チューリングマシンを開発して文字列中のAとBの数を数えます

Question

与えられた言語は ですL = {a^nb^nここでn> = 0} 私はそれのチューリングマシンを開発する必要がありますが、論理。 aの後にaが続いていない場合にはbの場合は拒否状態を止めるが、aとbの数が等しいかどうかチェックする方法は？ はどんな応答に対しても非常に感謝します

Answer 1

チューリングマシンは、入力テープが最初に言語の文字列を含むときに停止受け入れ状態になると言語を決定し、それ以外の場合は停止拒否状態になります。

言語Lを決めるには、テープに文字列が含まれているときにTMがhalt-acceptで終わるように、そして停止が終わるように状態と遷移を定義する必要があります。そうでなければ拒否する

シングルテープTMを前提としており、入力テープを処理後に元の状態に復元する必要はありません（つまり、テープに保存する必要はありません。特定の場所でテープヘッドをクリーンアップまたは移動させる）。文字列が言語にあるかどうかを確実に知るために、テープを処理する戦略が必要です。あなたのケースでは、aとbの数が同じで、bの後にaが必要です。あなたが実生活でこの仕事をしなければならない場合、どのようにそれに近づくことができますか？

最初にaを数え、次にbを数えて、その数が等しいかどうかを調べることができます。しかし、2つの数字が等しいかどうかを知ることは実際にはある程度の方が問題ありません問題は2つの文字列が同じ長さであるかどうかを伝えることよりも問題です（{a、b} *の言語ww | wは^ nb^nはコンテキストフリーです）。

もう1つのアプローチは、海賊が、宝物と数学者を分割するときに、「私のためのもの、あなたのためのもの」というアプローチです：2セットに同じ数の要素があることを示すには、すべての要素がちょうど1組になっていること。これは、カウントするのと同じ問題を生じません。同じ問題を解決する必要はありません。もう1つの問題は、より小さな問題をもたらしますが、これは元の問題とまったく同じ困難を伴うものです。確かに、まったく同じ問題の小さなインスタンスです！ 1つを消去し、対応するbを消去することにより、サイズのいずれかにサイズnの問題を減らすことができます。このプロセスを繰り返すことによって、最終的にテープ全体を消去し、ペアにするシンボルを受け入れたり、枯渇したり、拒否したりします。

これは私たちのデザインです。実装には、初期状態が必要です。最初の状態から、空でない最初のテープ・セルがあればそれを見ていると仮定できます。テープ・セルが空白の場合、入力は空であり、^ 0 b^0はn = 0の言語になっているため、受け入れる必要があります。テープ・セルにbがある場合、もしあれば、最初に。テープセルにaがある場合は、対応するbを探して消去する必要があります。

ここでどのbを消去する必要がありますか？現在、最後の入力シンボルの直後に空白があるので、入力がどこで終了するかを知っています。ブランクを使用してその前にbを消去すると、現在空白のセルの右側に入力が増えているかどうかを知る良い方法がありません。消去されたセルのために新しいテープ記号Eを導入することによってこれを克服することができます。次に、消去するときは、空白の代わりにEを書いて消去を指示します。それで、あなたが消すbは本当に問題ではありません。ただし、新しいテープシンボルを使用したくない場合は、入力の最後にある空白の直前にbを消去して（代わりにaが見つかった場合は拒否して）、同じことを達成できます。

いずれの場合でも、対応するbを消去した後、テープの最初に戻って（ブランクセルは最初に左に移動した後に到達します）、受諾または拒否するまで繰り返し処理を繰り返します。ここで

は、サンプルの実装です：

Q T Q' T' D 
-- - -- -- - 

// accept on empty tape 
q0 B hA B  S 

// erase an a or reject if no a 
q0 a q1 B  R 
q0 b hR b  S 

// scan to end of input 
q1 B q2 B  L 
q1 a q1 a  R 
q1 b q1 b  R 

// erase last b or reject if none 
q2 B qR B  S 
q2 a qR a  S 
q2 b q3 B  S 

// scan to beginning of input, then repeat 
q3 B q0 B  R 
q3 a q3 a  L 
q3 b q3 b  L