1

L = {a^f(m) | m >= 1 }がf: Z^+ -> Z^+単調に増加し、その中のすべての要素nがそのようなものZ^+にm属していることに準拠しているとしましょう。Z^+f(m+1) - f(m) >= n

L が正規言語であることを証明することは可能ですか?

4

1 に答える 1

1

f(x) = 2^x とします。任意の正の n の場合、f(n+1) - f(n) >= n。

L = {a^f(m)} は正則ではありません。文字列 a^(2^x + 1) を考えてみましょう。FA がそのような文字列を処理した後、受け入れ状態につながる最小の文字列は a^(2^x - 1) で、長さは 2^x - 1 です。したがって、x の値ごとに個別の状態が必要になります。x (正の整数) の値は無限にあるため、L を認識する FA は存在しません。したがって、L は通常の言語ではありません。

于 2011-08-16T19:10:21.453 に答える