1. Дан граф с 7 вершинами и 8 рёбрами, имеющими все возможные натуральные длины от 1 до 8. Каким может быть: а) наименьший; б) наибольший вес остовного дерева этого графа?

  2. Дана грамматика:

A ::= B|C|D

B ::= bB||dD|A

C ::= cC|dD|A

D ::= dD|A

а) удовлетворяет ли эта грамматика условию однозначности ветвления по первому символу?

б) постройте регулярное выражение, задающее описанной этой грамматикой язык.

в) Найдите количество слов длины 10 в этом языке.

г) Постройте автомат, распознающий этот язык.

д) Постройте детерминированный автомат, распознающий этот язык.

3) Образует ли множество всех несамодвойственных булевых функций: а) полный набор?; б) замкнутый класс?

задан 20 Янв 12:43

изменен 20 Янв 13:11

1) Если граф связен, то остовное поддерево там есть, и оно имеет 6 рёбер. Сумма их весов находится между 1+2+...+6 и 3+4+...+8. Ясно, что границы достигаются.

3) Штрих Шеффера несамодвойственен, и система из него полная. Замыкание класса состоит из всех функций, то есть класс не замкнут.

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

Ваш ответ

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

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

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

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

отмечен:

×827
×48

задан
20 Янв 12:43

показан
60 раз

обновлен
21 Янв 8:23

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

по почте:

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

по RSS:

Ответы

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

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