언어가 무한한 경우 표시 방법, L의 단어 길이에 상한이 없습니까?

Question

L은 유한 알파벳 이상의 언어입니다. L이 무한대이면 L 내의 단어 길이에 상한이 없음을 보여주는 방법은 무엇입니까?

누군가 나를 증명할 수 있도록 도와 줄 수 있습니까?

Answer 1

L의 단어 길이에 상한 = n이 있다고 가정합니다.
Σ를 알파벳으로 둡니다.

따라서 길이가 0 인 문자열 번호 = | Σ | 길이 1 문자열^0 = 1

번호 = | Σ |^1
등 길이 스트링 번호까지 N = | Σ |^n

따라서 총 문자열 수 = | Σ |^0 + | Σ |^1 + ... | Σ |^n = (| Σ |^n-1)/(| Σ | -1) (기하 급수적으로) n은 유한이기 때문에 유한 수이다.

그러나 언어는 무한합니다. 그러므로 이것은 우리의 가정과 모순된다.