48. Детерминированная и недетерминированная мт. Классы p и np - определение, связь с мт.

МТ называется детерминированной, если каждой комбинации состояния и ленточного символа соответствует не более одного правила.

Если существует пара «ленточный символ — состояние», для которой существует 2 и более команд, такая МТ называется недетерминированной.

К классу P относятся алгоритмы, выполняемые не более чем за полиноминальное время, и могут быть реализованы на детерминированной МТ

К классу NP относятся алгоритмы, которые можно за полиномиальное время решить на недетерминированной МТ

49. Язык, распознающая грамматика, порождающая грамматика - определения.

Язык-множество слов корректной структуры(слово-последовательность символов алфавита языка)

Распознающая грамматика-алгоритм распознающий корректность слова, поданного на вход

Порождающая грамматика- алгоритм строящий все корректные слова языка.

50-51. Иерархия Хомского. Пример КЗ-грамматики. Пример КС-грамматики.

Иерархия Хомского — классификация порождающих грамматик по типам правил вывода

-свободные грамматики

Тип: -свободные грамматики

Ограничений на правило вывода нет

Тип: - контекстно зависимые грамматики

,

Тип: - контекстно свободные грамматики

,

Тип: -автоматные(регулярные) грамматики

*леволинейные(леворекурсивные)

*праволинейные(праворекурсивные)

КЗ-грамм	КС-грамм
Язык { }	Язык {… …}

52-53. Конечный автомат - определение. Приведите примеры НКА и ДКА.

Конечный автомат — абстрактный автомат, число возможных внутренних состояний которого конечно.

Стартовое состояние:

Промежуточные состояния:

Конечные состояния:

Допустимая цепочка: последнее состояние

НЕ допустимая цепочка: последнее состояние или чтение не закончилось вовсе

(ДКА)Конечный автомат называют детерминированным если:

1По одному символу осуществляется переход строго в одно состояние

2 Переход по пустому символу запрещен

Недетерминированный конечный автомат (НКА) является обобщением детерминированного. 

НKA	ДКА

54-56. Нечеткие множества

Нечетким множеством  на универсальном множестве   называется совокупность пар (  ) где   - степень принадлежности элемента   к нечеткому множеству  .

Степень принадлежности - это число из диапазона [0, 1]. Чем выше степень принадлежности, тем в большей мерой элемент универсального множества соответствует свойствам нечеткого множества.

Объединение и пересечение.

Объединением нечетких множеств   заданных на  называется нечеткое множество с функцией принадлежности   для всех  .

Пересечением нечетких множеств    заданных на   называется нечеткое множество с функцией принадлежности   для всех  .

Второй вариант определения:

Сумма и произведение.

Треугольной нормой (  ) называется двуместная действительная функция   , отображающая две функции принадлежности нормальных нечетких множеств  в одну функцию принадлежности нормального нечеткого множества.

– симметричность;

– ассоциативность.

– монотонность;

Поведение в 1:

Треугольной нормой (  ) называется двуместная действительная функция   , отображающая две функции принадлежности нормальных нечетких множеств   в одну функцию принадлежности нормального нечеткого множества и удовлетворяющая следующим условиям:

– симметричность;

– ассоциативность.

– монотонность;

Поведение в 0:

Дополнение и включение

Дополнением нечеткого множества   заданного на   называется нечеткое множество   с функцией принадлежности   для всех

Включение нечеткого множества  заданного на   называется нечеткое множество   с функцией принадлежности   для всех