Как доказать?

Genmaximus

Что язык 0^n1^n не является контекстно-зависимым? Или где прочитать?

JuLsJuLs

развe не достаточно показать, что язык задается конечным автоматом?

Genmaximus

Ну там немного сложнее.
Любой контекстно-зависимый язык задается Линейно-ограниченной недетерминированной машиной Тьюринга. Надо только понять, что такой не существует.

JuLsJuLs

а
протупил - подумал, что n разное у нуля и единицы

JuLsJuLs

чота я вообще перестал понимать вопрос
этот язык даже контекстно-свободный, не то что контекстно-зависимый
правила (контекстно-свободные, в частости контекстно-зависимые):
(начальный символ) \ту 0(начальный символ)1
(начальный символ) \ту 01
что не так?

Genmaximus

Ну вроде решилась задачка.
Просто бывают языки, которые контекстно свободные, но не контекстно-зависимые.
Потому что в КЗ языках нет е-правил, а в КС могут быть.

JuLsJuLs

эээ
ну если дело в этом, то
1) ты забыл сказать, что n\ge 0, а не n\ge 1
2) только пустым словом он и отличается от контекстно-зависимого
кто такое занудство спрашивает-то? отчет сдаешь?

Genmaximus

Ага, сдал. Все равно спасибо.
А если n>=1, то он вообще КЗ.

JuLsJuLs

А если n>=1, то он вообще КЗ.
Кхм. Я это и говорил, собсна..
Оставить комментарий
Имя или ник:
Комментарий: