言語L = {0i0j0k/i <j <k}を受け入れるTMを構築する

Question

言語L = {0i0j0k/i <j < k}を受け入れるチューリングマシンを構築する方法。

Answer 1

これは言語0^i 0^j 0^k | i < j < kを意味すると解釈します。少なくとも、私はそれについての他の明白な解釈を見ない。

この言語の最短文字列は、i = 0,j = 1およびk = 2 'となります。これにより、言語で文字列000が生成されます。

も注意してください、我々は（n >= 3のため）i = 0、j = 1とk = n - 1を取ることができますので、以上の3ゼロのすべての文字列が言語でもあるということ。

したがって、私たちの言語は0^n | n >= 3です。この言語は定期的です。次のように、この言語のための最小限のDFAは次のとおりです。

ここ

Q s Q' 
q0 0 q1 
q1 0 q2 
q2 0 q3 
q3 0 q3 

、q3は受理状態であるとq0は初期状態です。これは、入力アルファベットが0のみで構成されていることを前提としています。もしそれ以上のものがあれば、死んだ状態と余分な作品が必要になります。

DFAからTMへの変換は、練習問題として残しています。