Библиотека Рефераты Курсовые Дипломы Поиск
Библиотека Рефераты Курсовые Дипломы Поиск
сделать стартовой добавить в избранное
Кефирный гриб на сайте www.za4et.net.ru

Компьютеры, Программирование Компьютеры, Программирование

Проверка непротиворечивости исходных описаний конечных автоматов

Карабин, 6x60 мм.
Размеры: 6x60 мм. Материал: металл. Упаковка: блистер.
44 руб
Раздел: Карабины для ошейников и поводков
Ночник-проектор "Звездное небо, планеты", черный.
Оригинальный светильник-ночник-проектор. Корпус поворачивается от руки. Источник света: 1) Лампочка (от карманных фанариков); 2) Три
350 руб
Раздел: Ночники
Ночник-проектор "Звездное небо и планеты", фиолетовый.
Оригинальный светильник - ночник - проектор. Корпус поворачивается от руки. Источник света: 1) Лампочка (от карманных фонариков) 2) Три
330 руб
Раздел: Ночники

Ю.М. Вишняков В 60-70-х годах на теорию конечных автоматов (КА), как универсальный инструментарий описания и синтеза цифровых схем, возлагались большие надежды. Однако возможности технологического базиса и информационные технологии того времени ограничили практическое использование теории КА только рамками структурного синтеза. Абстрактный синтез так и остался предметом теоретических изысканий. Сегодня в автоматизированном проектировании происходит интенсивный переход к интегрированным инструментальным средствам, осуществляющим сквозную разработку проектов на всех уровнях. В таких системах наряду со стандартными средствами проектирования топологии и моделирования должны присутствовать и средства реализация проектных процедур логического синтеза. Таким образом сегодня сформированы практические потребности и имеются все условия, чтобы абстрактная теория КА заняла достойное место в автоматизированном проектировании. Однако в этом плане она должна быть переработана в контексте сквозного автоматизированного проектирования. В рамках этой цели предлагаемая работа развивает абстрактный синтез в части построения непротиворечивых описаний КА на языке регулярных выражений. Пусть заданы входной X={X1,X2,.,X } и выходной Y={Y1,Y2,.,Ym} алфавиты. КА перерабатывает входные слова (цепочки) aÎX в выходные bÎY в соответствии с алфавитным (автоматным) оператором b=F(a) (А-оператор). Доказано, что обрабатываемые КА множества цепочек, относятся к классу регулярных множеств (РМ), которые задаются через правила их порождения,  называемые регулярными выражениями (РВ) . В алгебре РВ по определению Æ, l (пустая цепочка), X1, X2, ., X являются элементарными РВ. Если e1, e2, e - РВ, то результаты операций e1 e2 - (конкатенации), e1 e2 (ИЛИ), {e} (Клини), (e) (круглые скобки) также являются РВ. Также отметим, что порождаемое множество цепочек или язык  РВ e обозначают через e . Представим А-оператор через систему РВ (СРВ). Для этого выделим в X подмножества регулярных цепочек E1, E2, ., Em  (в общем случае  бесконечных) таким образом, чтобы цепочка aÎE1 приводила к появлению на выходе КА буквы Y1, aÎE2 - буквы Y2, aÎEm -.Ym. Для случая aÎX (E1E2.Em) определим дополнительную букву Ym 1. Также введем условие непротиворечивости EiEj= (i,j=1.m, i¹j). Представим каждое множество Ei порождающим его регулярным выражением (РВ) ei  ( ei = Ei). Тогда представляющая КА система соотношений вида (1) и  называется СРВ:                     (1) Поскольку взаимно однозначное соответствие между языком и порождающим его РВ отсутствует (например, РВ а{a} и {a}a порождают различными способами один и тот же язык), построение непротиворечивой CРВ требует далеко нетривиальных действий. И в этой связи можно предположить, что средства исследования непротиворечивости СРВ нужно искать вне алгебры РВ. Ближайшей моделью к РВ, которой может быть промоделирован разбор цепочек, является система переходов (СП), дуги которой взвешены буквами входного алфавита. КА с выходным алфавитом Y={0,1}, распознающий язык e , называют конечным распознавателем (КР).

Представление КР в виде диаграммы состояний (рис.1), в которой начальная вершина S и конечная вершина Z связаны дугой e называется системой переходов (СП). Здесь любая цепочка aÎ e переводит КА из состояния S в состояние Z . СП элементарных РВ приведены на рис.2. В соответствии с алгеброй РВ СП любого РВ e можно представить в виде композиции элементарных СП. Такую СП будем называть приведенной и обозначать через СПп. Введем на СПп ряд понятий. Определение 1. Если из некоторого состояния Q исходит l-дуга в состояние A1, из состояния A1 в состояние A2 и т.д. до состояния Т, а из состояния Т нет исходящих l-дуг, то будем говорить, что состояние Q связано с состоянием Т линейным  l-путем. Определение 2. Если из некоторого состояния Q исходит l-дуга в состояние А1, а из состояния А1 в состояние А2 и т.д. состояния Ak, а из состояния Ak в состояние Q, то будем говорить, что состояние Q, A1, A2,., Ak  входят в один и тот же кольцевой  l-путь. Длиной l-пути будем называть число входящих в него l-дуг. Определение 3. Блоком состояний (БС) для некоторого состояния Q БС(Q) назовем множество состояний, включающих само состояние Q и все состояния , входящие в l-пути, исходящие из состояния Q. Если из состояния Q не исходит l-путей, то БС(Q)= {Q}. В дальнейшем БС(Q), включающий более чем одно состояние, будем обозначать l- БС(Q). Определение 4. Если из состояния Q исходит один или несколько l-путей единичной длины, то l- БС(Q) назовем простым, в противном случае составным. Введем на СП функцию разбора m, представляющую отображение {БС}Х ® БС. Ее по аналогии с функцией переходов запишем в виде БС=m(БС(Q),xi). Цепочка a допускается КА, если существует функция разбора вида БС(Zi)=m(БС(S),a), где S - начальное состояние, Zi - заключительное состояние СП КА. Пусть задана СРВ e1, e2, ., em  и для каждого РВ выполнено независимое построение СПп. Здесь S1, S2, ., Sm начальные и Z1, Z2, ., Zm заключительные состояния соответствующих СПп. Введем следующую проверочную таблицу (ПТ), на основе которой будем одновременно строить функцию разбора для всех РВ. ПТ содержит m 1 столбец, где 1,2,.,m столбцы, соответствуют буквам входного алфавита X, а 0-столбец представляет БС, именующие строки. Множество строк ПТ разбито на группы, каждая из которых может содержать до m строк по числу РВ, и  представляет БС для всех РВ, полученных на некотором шаге построения функции разбора. В клетку пересечения строки и столбца записывается вычисленное значение функции разбора для данного БС и входной буквы. Алгоритм проверки непротиворечивости СРВ. 1. Построить пустую ПТ, сформировать БС(S1), БС(S2),., БС(Sm) и поименовать ими первую группу строк; 2. Для всех букв xi Î X вычислить функцию разбора; 3. Образовать новую группу строк и поименовать их новыми БС, полученными в п.2 и не содержащими заключительных состояний Zi. 4. Повторять п.2 до тех пор, пока не перестанут образовываться новые БС, не содержащие заключительных состояний. Выход: СРВ противоречива, если на некотором шаге для одной и той же входной буквы получены более чем один БС, содержащий  заключительные состояния.

В качестве примера ниже представлены проверяемая на непротиворечивость СРВ, СП, входящих в нее РВ (рис.4), и соответствующая ПТ:                                    (2) Проверочная таблица Как это видно из построения ПТ СРВ (2) является непротиворечивой. Итак, предлагаемая в работе процедура проверки на непротиворечивость исходных описаний КА, может быть  положена в основу построения одной из функциональных частей программной подсистемы логического синтеза  интегрированной инструментальной среды САПР. Это позволит на ранних этапах проектирования выявить корректность исходного описания объекта проектирования. Список литературы Вавилов Е.Н., Портной Г.П. Синтез схем электронных цифровых машин. М.: Сов.радио, 1963. 440 с. Грис Д. Конструирование компиляторов для цифровых вычислительных машин. М.: Мир, 1975, 545 с. Вишняков Ю.М. Инструментарий разработчика СБИС. - Таганрог: ТРТУ, 1993. 178 с.

Основания когнитивной науки были заложены исследованиями математика А. Тьюринга по конечным автоматам ( 1936). Ему удалось показать, что для проведения любого вычисления достаточно повторения элемен- 264 КОЖЕВ тарных операции. Тем самым открылись перспективы для проверки и реализации известной идеи Т. Гоббса и Д. Буля, что мышление есть вычисление. Проверяя эту идею, математик К. Шеннон предположил в 1948, что каждый элемент информации может быть представлен как выбор одной из двух равновероятных альтернатив, а количество передаваемой через канал связи информации может быть измерено с помощью двоичной системы счисления (в битах). К. Шеннон также показал, что в электрических цепях выполняются операции алгебры логики, В дальнейшем эти результаты были применены к изучению мозга. Уже в 1948 У. Мак-Каллох и В. Питтс выдвинули гипотезу о том, что мышление как процесс обработки когнитивной информации в принципе может протекать в нейронных сетях. Несколько позднее ими же была разработана первая нейронная модель мозга, где взаимодействие между сетями нейронов имитировали логические операции пропозиционального исчисления

1. Синтез цифрового конечного автомата Мили - вариант 2

2. Синтез цифрового конечного автомата Мили

3. Синтаксический разбор строк и конечные автоматы

4. Абстрактный синтез конечного автомата

5. Разработка модуля проверки диапазона исходных данных и нахождения номера первого символа в строке

6. Разработка функциональной схемы конечного автомата
7. Метод конечных элементов
8. Краткое описание происхождения птиц и описание некоторых птиц кайнозойской эры

9. Описание Волго-Вятского экономического района

10. Объем и характеристики исходной информации для составления проектов разработки нефтяных и газовых месторождений (контрольная)

11. Выездная налоговая проверка

12. Сравнительное описание слоговых структур английского и каракалпакского языков

13. Сравнительное описание слоговых структур английского и каракалпакского языков

14. Методы компьютерной обработки статистических данных. Проверка однородности двух выборок

15. Построение verilog-модели ber-тестера для проверки каналов связи телекоммуникационных систем

16. Дефрагментация и проверка диска

Магнит "Harry Potter HBP" Death Eater Masks.
Маска "пожирателей смерти". Пожиратели Смерти — группа тёмных волшебников последователей лорда Волан-де-Морта, сражающиеся в
773 руб
Раздел: Прочие
Ручка перьевая "Silver Prestige", синяя, 0,8 мм, корпус черный.
Перьевая ручка Silver Prestige. Цвет корпуса: черный. Материал корпуса: металл. Материал пера: иридий.
361 руб
Раздел: VIP-ручки
Набор мебели игровой "Малыш-2".
Замечательный набор детской мебели "Малыш-2" отлично подойдет для деток от 2 до 6 лет. Набор включает в себя столик и стульчик.
2025 руб
Раздел: Наборы детской мебели

17. Синтаксический анализ языка НОРМА. Разбор описания

18. Создание и описание базы данных "СТУДЕНТЫ" (Отчет по курсу "Базы данных")

19. Norton Commander. Описание и возможности

20. Описание Adobe Acrobat

21. Устройство управления синхронного цифрового автомата

22. Теория автоматов (Разработать автомата для сложения в коде 8421 в обратном коде в формате с фиксированной запятой)
23. ПРОЕКТИРОВАНИЕ УПРАВЛЯЮЩЕГО АВТОМАТА
24. Метод конечных разностей или метод сеток

25. Определение законов распределения случайных величин и их числовых характеристик на основе опытных данных. Проверка статистических гипотез

26. Описанные и вписанные окружности

27. Облитерирующее заболевание сосудов нижних конечностей

28. Полное описание витаминов

29. Описание экзам препаратов, конспекты тем, + экзам тест по пат анатомии

30. Дидактические функции проверки и учета знаний и умений, учащихся по физике

31. Структура и формирование исходных данных, необходимых для расчета параметров технологических схем

32. Устройство, проверка и регулировка карбюратора К-151 автомобиля ГАЗ-3110 "Волга"

Набор из 2 раций "Секретные рации. Тачки".
В настоящих шпионских играх секретная рация — необходимый атрибут! Один аппарат оставь себе, а другой отдай напарнику — переговоры можно
715 руб
Раздел: Шпионские штучки
Декоративная наклейка-ростомер "Жираф", арт. EZG-1005.
Размер: 40x75 см.
366 руб
Раздел: Ростомеры
Фоторамка "Poster blue" (70х100 см).
Рамка настенная может располагаться как вертикально, так и горизонтально. Для фотографий размером: 70х100 см. Материал: пластик.
584 руб
Раздел: Размер 50x60 и более

33. Устройство, проверка и регулировка карбюратора К-126Г (отчет)

34. Методичка для курсового проектирования по ПТЦА (прикладная теория цифровых автоматов)

35. Синтез управляющего автомата операции умножения младшими разрядами вперед со сдвигом множимого над числами в форме с фиксированной точкой в формате {1,8} для автомата Мура

36. Автомат для дозарядки АБ

37. Отчеты аудиторов при проверке финансовой отчетности

38. Основные методы аудиторской проверки
39. Приемы и способы проведения аудиторской проверки
40. Работа по оргтехнике: описание художественного салона

41. Описания компьютеpов с нетpадиционной аpхитектуpой (70-е и 80-е годы)

42. Фрейд З. Анализ конечный и бесконечный

43. Описание природы в прозе XIX века

44. Принципы синхронного описания языка

45. Персонаж как объект аксиологического описания (на материале рассказов В. М. Шукшина)

46. Эпоха царствования Александра II и появление “новых людей”, описанных в романе Н. Чернышевского “Что делать?”

47. Оценивание параметров и проверка гипотез о нормальном распределении

48. Как непротиворечиво понимать

Подушка для автокресел, детская "Roxy".
Детские подушки-рогалики обеспечивают комфортный сон в автомобильном путешествии. Удобная форма рогалика поддерживает шею и не позволяет
322 руб
Раздел: Дорожные пледы, подушки
Кабриолет "Нимфа".
Отличительная черта этого авто — это гармонично подобранные премиальные цвета и матовые поверхности, подчеркивающие статус владельца
527 руб
Раздел: Машинки для девочек
Охлаждающие камни для виски.
Для быстрого охлаждения любых напитков, не вбирают запахи и не царапают стеклянные бокалы. Не изменяют вкус напитка, возможно использовать
651 руб
Раздел: Аксессуары для вина

49. Об использовании квазираспределения Глаубера-Сударшана для описания динамического хаоса

50. Анатомия (артерии верхней конечности)

51. Варикозное расширение вен нижних конечностей

52. Санитарно-гигиеническое описание: Коломенский колбасный завод

53. Соединения костей верхней конечности

54. Описание системы Бянь Чжичжуна
55. Описание стандарта MRPII
56. Налоговая проверка организаций

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

58. Экспериментальная проверка помехозащищенности американской спутниковой навигационной системы GPS.

59. Описание химико-технологической схемы производства метанола

60. Ферменты и белки живой клетки – это молекулярные биологические автоматы с программным управлением

61. Описание в библиотечных каталогах и библиографических указателях. Проблема их сближения

62. Проверка знаний и умений в обучении истории

63. Камеральные проверки: на что обратить внимание

64. Аудиторская проверка страховщика

Пеленка непромокаемая "Наша мама" детская (70х100 см).
Непромокаемая пеленка предназначена для использования: в кроватке, в коляске, на пеленальных столиках, в кровати родителей. Пеленка в
323 руб
Раздел: Пелёнки
Микрофон "Пой со мной! Песенки Владимира Шаинского".
Этот микрофончик светится под музыку, а на каждой его кнопочке записано 5 любимых песенок, включая «Пусть бегут неуклюже»,
314 руб
Раздел: Микрофоны
Шкатулка ювелирная "Moretto", 18x13x5 см.
Оригинальная шкатулка сохранит ваши ювелирные изделия в первозданном виде. С ней вы сможете внести в интерьер частичку
701 руб
Раздел: Шкатулки для украшений

65. О восприятии Мира в контексте бесконечно-конечного

66. Темперамент, его физиологические основы и психологическое описание

67. Методика обучения истории в схемах, таблицах, описаниях

68. Микросхема ПЗУ в управляющем автомате с МПУ выбрана неверно

69. Синтезирование управляющего автомата

70. Шпоры по теории автоматов
71. Синтез управляющего автомата операции умножения младшими разрядами вперед со сдвигом множимого над числами в форме с фиксированной точкой в формате {1,8} для автомата Мура
72. Описание работы электрической схемы охранного устройства с автодозвоном по телефонной линии

73. Прикладная теория цифровых автоматов

74. Структура и формирование исходных данных, необходимых для расчета параметров технологических схем

75. Физическое описание явления фильтрации жидкости

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

77. Философское исследование человека: проблема исходных допущений

78. Краткое описание химических элементов

79. Описание технологий очистки воздуха от вредных газов

80. Осмотр и описание объекта недвижимости

Чернильный картридж Parker для перьевой ручки. Темно-синий (5 штук).
Для использования в перьевых ручках Паркер. Чернила темно-синего цвета.
309 руб
Раздел: Стержни для ручек
Таз со стиральной доской.
Универсальный таз со встроенной рельефной поверхностью для ручной стирки. Таз изготовлен из высококачественного полипропилена,
451 руб
Раздел: Более 10 литров
Пистолет для подкачки шин, пневматический.
Инструмент предназначен для подкачки сжатым воздухом автомобильных колес, оборудован манометром для контроля давления. Оборудован клапаном
562 руб
Раздел: Насосы, компрессоры автомобильные

81. Проверка полноты и правильности синтетического учета по валютному счету

82. Исследования влияние системы учета затрат и формирования себестоимости на конечные результаты деятельности ООО «Пластик»

83. Методология прогнозирования и анализ конечного использования продукции

84. Теория коммуникативной грамматики и проблема системного описания русского синтаксиса

85. Семантико-структурное описание глагола то wear

86. Санитарная проверка
87. Методологические проблемы описания коммуникативных сигналов у птиц: попытка решения
88. Скелет пояса нижних конечностей

89. Влияние структуры исходной ПАН-нити на структуру и свойства углеродного волокна

90. Аудиторская проверка счетов организации в банках

91. Организация аудиторской проверки

92. Проверка формирования и использования финансовых результатов

93. Программа аудиторской проверки по материалам и МБП

94. Курганская область: описание

95. Краткое описание основных технологических процессов топливного производства

96. Характеристика исходной информации и режим атмосферных осадков (на примере метеостанции Лиски)

Домкрат гидравлический, подкатной, 2 т, 130-315 мм.
Домкрат гидравлический подкатной MIRAX, используется при проведении ремонтно-строительных работ. Эта модель домкрата одна из самых
1865 руб
Раздел: Домкраты, подставки
Дождевик Bambola для колясок прогулок с ручкой перекидной, пвх.
Прозрачный чехол для коляски - защита от дождя и снега.Выполнен из ПВХ - прочный, не трескается, не мутнеет. Подходит для прогулочных
333 руб
Раздел: Дождевики, чехлы для колясок
Рюкзак школьный с эргономичной спинкой "Neon. Модель Multi Pack".
Ранец с эргономичной спинкой. Жесткий каркас. Вмещает формат А4+. Размер: 40x32x18 см. Имеет два отделения на молнии, боковые карманы на
2306 руб
Раздел: Без наполнения

97. Сортировка карточек: полное описание метода

98. Создание меню без файла описания ресурсов на основе функции LoadMenuIndirect

99. Описание системы планер "Юниор"


Поиск Рефератов на сайте za4eti.ru Вы студент, и у Вас нет времени на выполнение письменных работ (рефератов, курсовых и дипломов)? Мы сможем Вам в этом помочь. Возможно, Вам подойдет что-то из ПЕРЕЧНЯ ПРЕДМЕТОВ И ДИСЦИПЛИН, ПО КОТОРЫМ ВЫПОЛНЯЮТСЯ РЕФЕРАТЫ, КУРСОВЫЕ И ДИПЛОМНЫЕ РАБОТЫ. 
Вы можете поискать нужную Вам работу в КОЛЛЕКЦИИ ГОТОВЫХ РЕФЕРАТОВ, КУРСОВЫХ И ДИПЛОМНЫХ РАБОТ, выполненных преподавателями московских ВУЗов за период более чем 10-летней работы. Эти работы Вы можете бесплатно СКАЧАТЬ.