L - язык над конечным алфавитом. Как показать, что если L бесконечно, то нет верхней границы длины слов внутри L?Как показать, является ли язык бесконечным, тогда нет верхней границы длины слов в L?
Может кто-нибудь помочь мне доказать это.
Предположим, что существует верхняя граница = n, по длине слов в L.
Пусть Σ - алфавит.
Так количество строк с длиной 0 = | Е |^0 = 1
количества строк длиной 1 = | Е |^1
и так далее до числа строк длиной п = | Σ |^n
Поэтому общее число строк = | Σ |^0 + | Σ |^1 + ... | Σ |^n = (| Σ |^n -1)/(| Σ | -1) (по геометрической прогрессии), которое является конечным числом, так как n конечно.
Однако язык бесконечен. Поэтому это противоречит нашему предположению.
Этот вопрос, вероятно, лучше всего подходит для math.stackexchange.com – Esse
Попробуйте противоречие; что произойдет, если есть верхняя граница? Image, что верхняя граница X, то максимальное число строк меньше S^(X + 1) (где S - количество символов в алфавите) – okaram
Я голосую, чтобы закрыть этот вопрос как не по теме, потому что это лучше подходит для компьютерных наук SE! –