Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Объединение

Читайте также:
  1. ОБЪЕДИНЕНИЕ
  2. ОБЪЕДИНЕНИЕ ДО-СОВРЕМЕННОГО И СОВРЕМЕННОГО
  3. Объединение множеств
  4. Объединение нот
  5. Объединение ячеек
  6. Принцип обеспечения права работников и работодателей на объединение для защиты своих прав и интересов

Это сочетание определяется таким предписанием:

1) к исходному слову применить алгорифмы и (независимо друг от друга);

2) если оба слова и определены, то результатом считается слово .

 

Объединение нормальных алгорифмов также может быть задано схемой некоторого нормального алгорифма, т.е. доказывается следующая теорема:

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

.

 

Теорема об объединении доказывается уже с учетом доказанной теоремы о композиции, т.е. доказательство состоит в том, что объединение сводят к композиции. Это доказательство мы не приводим (даже «на уровне идеи»).

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

,

где «звездочка» (*) – буква, не принадлежащая объединению алфавитов
и .

Нормальный алгорифм , построенный согласно теореме об объединении, обозначают .

 


Дата добавления: 2015-07-15; просмотров: 74 | Нарушение авторских прав


Читайте в этой же книге: Определение | Эквивалентность алгорифмов | Теорема о переводе | Повторение |
<== предыдущая страница | следующая страница ==>
Теоремы сочетания| Разветвление

mybiblioteka.su - 2015-2024 год. (0.005 сек.)