L = { 1 ^ n (n+1) / 2 } не зависит от контекста?

Question

L = { 1 ^ n (n+1) / 2 } не зависит от контекста?

Я заметил, что язык L генерирует слова с длиной, которая представляет числа треугольника: 1,3,6,10,15 и т. Д.

Я пытаюсь использовать лемму Пемпингта для w=1^(p(p+1), но я нигде не доходил..

Может кто-нибудь помочь или дать мне представление, как это решить?

Спасибо!:)

0

context-free-language

Источник

user6015228 29 окт '17 в 17:13

1 ответ

Другие вопросы по тегам context-free-language

user6034255 30 окт '17 в 08:16 2017-10-30 08:16 · Answer 1 · 2017-10-30 08:16

Все контекстно-свободные языки, состоящие из однобуквенного алфавита, являются обычными. Так что, если бы L был свободен от контекста, это также было бы регулярно. Все обычные языки, состоящие из однобуквенного алфавита, в конечном итоге являются периодическими, чего нет у L, потому что пропуски все время увеличиваются.

Или с леммой прокачки: любая прокачка приводит к языку uv ^ iwx ^ i y. Поскольку все буквы одинаковы, мы можем обмениваться множителями, и это равно uyw v ^ ix ^ i = uyw (vx) ^ i. В L расстояние между одним словом и следующим будет больше любого |vx|^i с ростом n.