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

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

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

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

Благодаря ! :)

context-free-language,

0

Ответов: 1


1

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

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

контекстно-свободный язык,
Похожие вопросы
Яндекс.Метрика