언어에 주어진 크기의 단어가 있는지 확인

Question

한다고 가정 $L$ 알파벳 위의 어떤 언어인가 $\시그마$.나는 다음 언어가 결정 가능하다는 것을 보여 달라는 요청을 받았습니다.

$$ l '= {w in sigma^* | text {단어가 있습니다} w ' in l text {was} | w'| leq | w | } $$

즉., $w \in L'$ 만약에 $L$ 다음보다 길이가 짧은 단어가 있습니다. $|w|$.

제가 보여주고자 했던 방식은 관찰하는 것이었습니다. $L \cap\시그마^{|w|}$ 유한하고, $(L \cap \Sigma) \cup (L \cap \Sigma^2) \cup \ldots\cup (L\cap \Sigma^{|w|})$ 역시 유한하므로 결정 가능합니다.하지만 제가 고민하고 있는 가장 중요한 문제는 알고리즘이 어떻게 $L'$ 어떤지 알아 $u \in L$?이것은 결정할 수 없으므로 어떤 알고리즘이 어떻게 작동하는지 불분명합니다. $L'$ 실제로 어떤 단어가 있는지 확인할 수 있습니다 $L$

Answer 1

두 가지 경우가 있습니다:

1. $L$ 비었다.이 경우, $L' = \빈 집합$ 사소하게 결정 가능합니다.
2. $L$ 비어 있지 않습니다.허락하다 $m$ 단어의 최소 길이 $L$.그 다음에 $L'$ 적어도 길이가 긴 모든 단어로 구성됩니다. $m$, 그리고 다시 사소하게 결정 가능합니다(일정한 시간에!).

보시다시피 실제로는 알고리즘이 필요하지 않습니다. $L$.

---

마찬가지로 다음 언어는 항상 결정 가능합니다.

$$ l ''= {w in sigma^* mid text {$ | w '| geq | w | $} }. $$

이제 세 가지 경우가 있습니다.

1. $L$ 비었다.이 경우, $L'' = \빈 집합$ 사소하게 결정 가능합니다.
2. $L$ 무한하다.이 경우, $L'' = \시그마^*$ 다시 한 번 사소한 결정이 가능합니다.
3. $L$ 유한하다.허락하다 $M$ 단어의 최대 길이 $L$.그 다음에 $L''$ 최대 길이의 모든 단어로 구성됩니다. $M$, 그리고 다시 (일정한 시간에) 사소하게 결정 가능합니다.

---

이것은 당신이 좋아하지 않을 수도 있는 비구조적 증명의 예입니다.여기서 논의를 시작하는 대신 다음 사항을 참고하시기 바랍니다. 이 질문.