turing-machines - チューリングマシンを使用して同じ長さの2本の弦を受け入れる

Question

この問題はNET試験で尋ねられます。

この問題の解決方法を教えてください。問題は、同じ長さの2つの文字列を受け入れることです。

この形式で{q0==>[q0、b、a]のようなチューリングマシンテーブル}で答えたいと思います。

shubhadaa

Answer 1

試験の目的は、アルゴリズムを考案し、それをチューリングの表記法で表現できることを示すことです。そのため、マシン テーブルを提供することは非生産的です。ただし、両方の文字列が同じテープにエンコードされていると仮定すると、単純な文字マーキング アルゴリズムで十分です。