Дано регулярное выражение (x+y+z)0(u+v)0, 0 - звезда клини Составьте грамматику для языка, задаваемого этим выражением. Сколько двенадцатибуквенных слов она задает?

задан 8 Янв 17:38

изменен 8 Янв 17:42

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

Данный регулярный язык устроен довольно просто. Сначала идёт какое-то слово над алфавитом {x,y,z}, потом вслед за ним идёт слово над алфавитом {u,v}. Слова при этом могут быть пустыми.

Пример регулярной грамматики, задающей данный язык:

S->xS, S->yS, S->zS, S->T, T->uT, T->vT, T->eps,

где eps -- пустое слово.

Слово длиной 12 является произведением слов AB, где |A|=k,|B|=12-k. При фиксированном k от 0 до 12, слово A может быть выбрано 3^k способами, и B выбирается 2^{12-k} способами. Получается сумма 3^{12}+3^{11}2+3^{10}2^{2}+...+2^{12}. Это сумма членов геометрической прогрессии, равная 3^{13}-2^{13}.

ссылка

отвечен 9 Янв 0:08

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

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

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

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

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

отмечен:

×546
×18

задан
8 Янв 17:38

показан
31 раз

обновлен
9 Янв 0:08

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

по почте:

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

по RSS:

Ответы

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

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