10

機械が言語を認識して決定するということの意味を理解するのに苦労しています。私は定義に近いと思いますが、正しくありません。

チューリング マシンTが言語を認識すると言うときL、

L = { <A> | A is a DFA }

ここで、DFA = 決定論的有限オートマトン

私の理解では、これは、あらゆる種類の入力 (文字列、車、人など) が与えられたときに、入力として与えたものが DFA であるかどうかを判断できるチューリング マシンを構築できることを意味します。 . つまり、 は常に DFA を受け入れ、DFA 以外の入力を常に拒否します。

つまり、その入力が のメンバーである場合ですL。他の例として、男 X は自分の父親を認識していると言うでしょう。あなたが彼の前に置くものは何でも、彼は自分の前にあるものが彼の父親であるかどうかをあなたに伝えることができるからです。これは正しいです？正しくないのはどの部分ですか？

一方、deciderオーバー言語はチューリング マシンのように見えloopsます。つまり、どんな入力に対しても受け入れ状態または拒否状態で常に停止することはありません。これは、レコグナイザーについて上で説明したことと似ているか、同じではないでしょうか?

ありがとう

4

4 に答える 4

13

少し勉強した後、私は2つの違いがわかったと思います。

いつものように、悪魔は細部に宿ります。

まず、決定可能な言語は常に認識可能な言語です。

認識可能な言語とは、その言語をその言語として持つマシンが少なくとも 1 つ存在する言語です。最初は、これはもう 1 つの循環定義のように思えるかもしれませんが、..

簡単に言えば、すべての文字列を受け入れることができるマシンを考えることができれば、その言語は認識可能です。

例

本当に簡単な言語を考えてみましょう:

L = { abc }

この言語は abc という単語だけで構成されています。つまり、この言語が認識可能であることを証明するには、それを受け入れるマシンを 1 つ作成する必要があります。非公式に行います。

M は、入力として abc が与えられたときに受け入れるマシンであり、それ以外の場合は無限ループします。

このマシンは、言語 L のすべてのメンバーを受け入れるため、L の認識機能を備えています。すべての入力を受け入れる/拒否するマシンが存在する場合、この言語は決定可能な言語のクラスの一部になる可能性もあります。建てることはできますか？

(ネタバレ注意!!!11@#$!1)

M' は、入力として abc が指定された場合に受け入れ、それ以外の場合は拒否するマシンです。

つまり、L を認識するマシンがあり、L に与える入力が何であれ、常に受け入れるか拒否するため、言語は決定可能であると見なされます。

さらに、ある日、L を認識するマシンを構築することに興味がある場合は、abc を受け入れることができるが、他の場合に惨めに失敗するという問題に遭遇することなく、常にそれを行うことができるマシンが少なくとも 1 つあることを知っているでしょう。 、永遠にぶら下がっています！

于 2011-03-15T04:48:06.093 に答える
2

私が考える簡単な答えは次のとおりです。

ディサイダーは常に停止し、承認または拒否します

しかし

Recognizer は常に停止するとは限りません。Machine は受け入れ、拒否、またはループすることができます。ループとは、マシンが停止しないことを意味します。

レコグナイザーの場合、ディサイダーを使用して決定することがあります。マシンがループしている場合、ディサイダーは説明に従って拒否します。

于 2012-12-19T09:31:59.993 に答える
0

チューリング マシンが L のような言語を認識するということは、チューリング マシンが L を構成する DFA と同じ入力をすべて受け入れるということだと思います。したがって、それらはある意味で同等です。

于 2011-03-14T04:23:22.333 に答える