Главная Случайная страница


Полезное:

Как сделать разговор полезным и приятным Как сделать объемную звезду своими руками Как сделать то, что делать не хочется? Как сделать погремушку Как сделать так чтобы женщины сами знакомились с вами Как сделать идею коммерческой Как сделать хорошую растяжку ног? Как сделать наш разум здоровым? Как сделать, чтобы люди обманывали меньше Вопрос 4. Как сделать так, чтобы вас уважали и ценили? Как сделать лучше себе и другим людям Как сделать свидание интересным?


Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






Алгоритм распознавания однозначности кодирования





Используя нетривиальные разложения элементарных кодов, опишем алгоритм для схемы кодирования Σ.

1.Для каждого элементарного кода выполним всевозможные нетривиальные разложения.

2. Строим множество М следующим образом. В него включаем пустой символ L, а также каждое слово типа β, которое встречается в нетривиальных разложениях элементарных кодов как в роли префикса, так и в роли окончания. В разных ролях это слово не обязательно используется в разложении одного и того же элементарного кода.

3. Каждому слову из М сопоставляем вершину графа. Пусть слова , содержатся в М. Выделим среди нетривиальных разложений элементарных кодов схемы Σ разложения вида . Для каждого из них проведем дугу из в , пометив ее элементарными кодами . Полученный граф обозначим G(Σ).

4. Анализируем граф G(Σ), отыскивая в нем ориентированный цикл, содержащий вершину L. Если цикл существует, то кодирование не однозначно, иначе кодирование однозначно.

 

Т5.1. Множество S не выполнимо, если и только если не выполнимы два множества: È и È .

Доказательство следует из того факта, что рассматриваемые множества получаются из S фиксированием значения p (p = и, p = л соответственно).

Т3.1. Класс L (A, , S) конечноавтоматн языков замкнут относительно опер 1–8.

Date: 2015-09-05; view: 1200; Нарушение авторских прав; Помощь в написании работы --> СЮДА...



mydocx.ru - 2015-2024 year. (0.005 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию