Войти в систему

Home
    - Создать дневник
    - Написать в дневник
       - Подробный режим

LJ.Rossia.org
    - Новости сайта
    - Общие настройки
    - Sitemap
    - Оплата
    - ljr-fif

Редактировать...
    - Настройки
    - Список друзей
    - Дневник
    - Картинки
    - Пароль
    - Вид дневника

Сообщества

Настроить S2

Помощь
    - Забыли пароль?
    - FAQ
    - Тех. поддержка



Пишет lol҉ ([info]mao) в [info]programming
@ 2011-04-27 17:16:00
Previous Entry  Add to memories!  Tell a Friend!  Next Entry
Может кто-нибудь подсказать, как доказать, что языки с "циклической" структурой (где для выражения токенов используется рекурсия) не могут являться регулярными ?

(Добавить комментарий)


[info]maxmornev.livejournal.com
2011-04-27 18:21 (ссылка)
> языки с "циклической" структурой
Можете пояснить, что это значит?
Что язык КС?

Обычно, вот этот аргумент (http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages) используют,
но, подозреваю, что вы о нем в курсе.

(Ответить) (Ветвь дискуссии)


[info]mao
2011-04-28 19:03 (ссылка)
> Можете пояснить, что это значит?
> Что язык КС?
Хм, нет. Я не знаю как это формально называется, например XML, или LISP.

> Обычно, вот этот аргумент используют,
> но, подозреваю, что вы о нем в курсе.
Нет, не в курсе, спасибо. То что надо.

(Ответить) (Уровень выше)


[info]pzz
2020-06-01 04:31 (ссылка)
Рекурсия требует стека. Регулярный автомат имеет конечное число состояний, и для выражения текущего достаточно одной целочисленной переменной.

(Ответить)