Главная Кибернетика [ 0 ] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] кибернетика Предлагаемая книга Артура Гилла - доктора наук по электротехнике, преподавателя Калифорнийского университета- содержит систематическое изложение основных вопросов теории конечных автоматов. В книге дается строгое определение конечного автомата, как модели реального устройства, с иллюстрацией на примерах. Автор, сохраняя математическую строгость, в доступной для широкого круга читателей форме, ясно и последовательно излагает различные способы представления конечных автоматов (таблицы, графы, матрицы переходов), методы минимизации автоматов, теорию экспериментов над автоматами и ряд других вопросов. Принятое расположение материала облегчает его усвоение инженерно-техническими работниками, имеющими дело с реальными объектами, так как при абстрактном представлении позволяет сохранять связь с привычными для инженера реальными устройствами. Основным отличием книги от существующих является подробное и систематическое изложение достижений в области теории экспериментов, которая начинает находить широкое применение при решении задач технической диагностики дискретных устройств и систем с памятью, в том числе вычислительных и управляющих машин. Каждая глава книги содержит примеры и заканчивается задачами, что облегчает глубокую проработку и усвоение ее содержания. Книга является хорошим учебным пособием для студентов, инженеров и научных работников, занимающихся изучением теории конечных автоматов и ее практическими приложениями. П. Пархоменко ПРЕДИСЛОВИЕ Последние годы явились свидетелями возникновения новой научной дисциплины, известной под названием теория систем. Появление этой дисциплины в большой степени было обусловлено проницательностью исследователей в различных областях науки и техники, нашедших общий язык в процессе ее формирования. Цель этой теории состояла в том, чтобы создать арсенал идей и средств, которые были бы в равной степени полезны специалистам во многих различных областях, таких, как электрэтехника, механика, физиология и лингвистика. Она была достигнута путем рассмотрения системы (которая может представлять собой живой организм, промышленное предприятие, управляемый снаряд) не через ее внутреннюю структуру, а через математические законы, определяющие ее наблюдаемое поведение. При использовании такого подхода, называемого методом «черного ящика», было найдено, что системы, представляющие совсем разные физические построения, могут все же быть охарактеризованы в одинаковых терминах и проанализированы с помощью одного и того же набора правил. Хотя понятие о теории систем как о независимой дисциплине возникло совсем недавно, большинство ее составных частей - это установившиеся отрасли знаний. Теорию информации, теорию линейных систем, теорию управления и теорию конечных автоматов можно рассматривать в качестве основных составных частей теории систем ввиду того, что они затрагивают самые разнообразные области науки и техники. Из четырех дисциплин, указанных выше, теория конечных автоматов является наиболее новой дисциплиной, которая в отличие от других до сих пор еще не обобщена в виде отдельной книги. По мере расширения применения систем с дискретными состояниями вообще, и цифровых вычислительных машин в частности, потребность в такой книге как со стороны научных работников, так и со стороны промышленности непрерывно возрастала. Настоящая книга, представляющая собой вводное изложение понятий и методов, лежащих в основе теории синхронных детерминированных автоматов с конечным числом состояний, предназначена для того, чтобы отчасти удовлетворить эту потребность. Как вводное руководство по теории машин с конечным числом состояний, настоящая книга охватывает лишь малую, но очень важную ее часть, известную под названием «теория автоматов». Таким образом, книга ограничивается основными теоретико-системными аспектами конечных автоматов, такими, как: задание условий работы автоматов, матрицы переходов, эквивалентность состояний и автоматов, минимизация автомата, эксперименты по распознаванию состояний и автоматов и по распознаванию неисправностей, - а также аспектами автоматов без потерь информации и автоматов с конечной памятью. Материал в значительной степени базируется на работах, выполненных за последнее десятилетие Хаффменом, Муром, Ауфенкампом, Хоном, Гинзбургом, Заде, Симоном, Поллом и Ангером (более подробные ссылки распределены в сносках по всей книге). Особое внимание в книге уделено методам анализа. Вопросы синтеза конечных автоматов здесь не рассматриваются. Причина этого состоит в том, что методы синтеза по своему существу являются специализированными и требуют полных знаний относительно данной исследуемой системы и компонент, которые можно использовать для ее реализации; с другой стороны, методы анализа могут быть сделаны вполне общими и применимыми к любой системе [ 0 ] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] 0.0017 |