grammar - 非決定性チューリングマシンを使用した状況依存言語

Question

非決定性チューリングマシンを使用して、言語が状況依存であることをどのように示すことができますか？

線形拘束オートマトン（LBA）で受け入れられる言語は、状況依存言語であることを私は知っています。また、LBAは非決定性チューリングマシンです。

これらすべてをどのように関連付けて、言語が状況依存であることを示すことができますか？

Answer 1

templatetypedefの回答にはいくつかの欠陥があるため（コメントですぐに指摘します）、あなたの質問に簡単に回答します。

Lを定義する線形空間を使用して非決定性チューリングマシンを提供できる場合（およびその場合のみ）、言語は状況依存です。

任意の整数nに対してL={a ^ nb ^ na^n}とします。ここでのa^nは、記号aのn個の連結を意味します。これは典型的な状況依存言語です。CSGを指定する代わりに、LBAを指定して、Lがコンテキスト依存であることを示すことができます。

チューリングマシンM'は'（非決定性のおかげで）n [言い換えると、'非決定性探索木のすべてのブランチが別のnを試行する]と推測し、入力がa ^ nb ^ na^nと一致するかどうかをチェックします。nを格納するにはlognセルが必要です。マッチングには、別のlog nセルが必要になる場合があります（簡単に実装されている場合）。n + 2log n <2nであるため、このマシンは線形空間のみを必要とし、したがってLBAであるため、Lはコンテキストに依存します。

Answer 2

これは正確な答えではありませんが、状況依存言語は線形拘束オートマトン（テープにO（n）スペースがあるTM）によって受け入れられる言語であるため、状況依存言語は正確にDSPACE（n）の言語です。 ）。さらに、 NTIME（n）= DSPACE（n）であることがわかります。これは、ある言語Lのメンバーシップを決定する線形時間NTMを見つけることができる場合、その言語は状況依存でなければならないことを意味します。ただし、線形時間NTMを持たない状況依存言語がまだ存在する可能性があるため（これに対する決定的な答えがあるかどうか、またはこれが未解決の問題であるかどうかはわかりません）、これは正確な特性ではありません。

お役に立てれば！