Читать онлайн «Основы теории конечных автоматов и формальных языков»

МИНОБРНАУКИ РОССИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «ПЕНЗЕНСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ» СИСТЕМА ОТКРЫТОГО ОБРАЗОВАНИЯ Л. И. Федосеева, Р. М. Адилов, М. Н. Шмокин ОСНОВЫ ТЕОРИИ КОНЕЧНЫХ АВТОМАТОВ И ФОРМАЛЬНЫХ ЯЗЫКОВ Рекомендовано федеральным государственным бюджетным образовательным учреждением высшего профессионального образования “Московский государственный технический университет имени Н. Э. Баумана” в качестве учебного пособия для студентов высших учебных заведений, обучающихся по направлению “Информатика и вычислительная техника” Пенза ПГТА 2013 1 УДК 519. 713 Рецензент – Уполномоченная Министерством образования и науки Российской Федерации организация Федерального Государственного бюджетного образовательного учреждения высшего профессионального образования “Московский государственный технический университет им. Н. Э. Баумана” (регистрационный номер рецензии 2319 от 24 апреля 2013 г. ) Федосеева, Л. И. Основы теории конечных автоматов и формальных языков : Учебное пособие / Л. И. Федосеева, Р. М. Адилов, М. Н. Шмокин. – Пенза : Изд-во Пенз. гос. технол. ун-та, 2013. – 136 с. : 79 ил. , 62 табл. , библиогр. 25 назв. Рассматриваются основы теории конечных автоматов и формальных грамматик, операторных схем алгоритмов, способы задания и общие методы абстрактного и структурного синтеза цифровых автоматов. Уделяется внимание разработке цифровых схем комбинационного действия и схем с памятью. В начале каждой главы приводится краткое изложение теории, затем подробно рассматриваются примеры и задачи с решениями. Приводятся кон- трольные вопросы. Учебное пособие подготовлено на кафедре «Вычислительные машины и системы» Пензенского государственного технологического университета в соответствии с Федеральным государственным образовательным стандартом ВПО и предназначено для студентов, обучающихся по направлению подго- товки бакалавров 230101. 62 “Информатика и вычислительная техника”. УДК 519. 713 © Пензенский государственный технологический университет, 2013 © Федосеева Л. И. , Адилов Р. М. , Шмокин М. Н. , 2013 2  Предисловие “Теория автоматов” является одной из первых дисциплин, которая закладывает теоретическую базу для освоения специальных дисциплин. При её изучении студенты должны получить знания об основах теории формальных грамматик, о способах задания цифровых автоматах на на- чальных и на стандартных языках, об общих методах синтеза цифровых схем комбинационного действия и схем с памятью, а также о методах син- теза устройств управления на алгоритмическом и структурном уровнях.