alt text

Что у меня получилось: (1*(00)*1*)*

задан 10 Сен 19:05

изменен 10 Сен 19:05

10|600 символов нужно символов осталось
1

Я так понимаю, что помимо нахождения регулярного выражения, нужно ещё указать число слов языка длины N. Само выражение -- верное, так как слово можно разбить на части, в каждую из которых входит чётное число нулей подряд в обрамлении нескольких единиц. Можно было также рассмотреть выражение $%\{00,1\}^{\ast}$%, если синтаксис это позволяет.

Для подсчёта можно, наверное, использовать какую-то общую технику, а можно рассуждать и непосредственно. Пусть $%a_n$% -- искомое число слов длины $%n$%. Ясно, что $%a_0=a_1=1$%. Пусть $%n\ge2$%. Слово длиной $%n$% оканчивается либо на $%1$%, либо на $%00$%. После отсечения остаётся слово из того же языка длиной $%n-1$% или $%n-2$% соответственно. Это даёт рекуррентную формулу $%a_n=a_{n-1}+a_{n-2}$%, то есть получаются числа Фибоначчи.

ссылка

отвечен 10 Сен 21:31

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×25

задан
10 Сен 19:05

показан
34 раза

обновлен
10 Сен 21:31

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

по почте:

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

по RSS:

Ответы

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

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