Решите следующую задачу использовав индукцию по построению формулы. Рассмотрим индуктивное определение правильной скобочной последовательности с двумя типами скобок. Пустая последовательность является правильной. Если последовательности s и t правильные, то (s), [s] и st также правильные. Правильными являются все последовательности, которые можно построить за конечное число применений этих правил, начиная с пустых слов. Докажите, исходя из этого определения, что последовательность ([)] не является правильной.

задан 15 Окт 20:20

Всякая правильная последовательность содержит равное число скобок ( и ), а также скобок [ и ]. Это доказывается по индукции. Отсюда ясно, что ([)] не могла быть построена по правилу st. Как бы мы ни разделили строку на части, где-то нарушится "паритет". Также понятно, что строка не получена по правилу (s), так как в конце нет круглой скобки. Аналогично для [s]. Значит, она не могла быть построена.

(15 Окт 20:30) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×911

задан
15 Окт 20:20

показан
40 раз

обновлен
15 Окт 20:30

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru