Распознается ли конечным автоматом язык

[debrod]

Распознается ли конечным автоматом язык в алфавите A={a,b}?

Насколько я понял, язык нерегулярный, и, чтобы это доказать, нужно использовать лемму о накачке.

[iifat]

Ну дык попробуйте же ж.
Ну или попробуйте разбить язык на части. Какие части вам кажутся наиболее естественными?

[debrod]

Поправьте меня, пожалуйста. Нужно разбить слово на блоки xyz, взять некое натуральное n. Тогда |xy|<=n, y можно накачать k раз, что слово будет принадлежать языку L. Но как разбить слово на эти блоки x,y,z и показать ,что при некотором k слово не принадлежит L?

-- 14.01.2017, 13:20 --

Поправьте меня, пожалуйста. Нужно разбить слово на блоки xyz, взять некое натуральное n. Тогда |xy|<=n, y можно накачать k раз, что слово будет принадлежать языку L. Но как разбить слово на эти блоки x,y,z и показать ,что при некотором k слово не принадлежит L?

[Lia]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы);


Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.