Грамматики и автоматы

ТЕОРИЯ ФОРМАЛЬНЫХ ЯЗЫКОВ.

М. А. Шамашов

Учебное пособие

Самара

УДК 519.682:681.142

Теория формальных языков. Грамматики и автоматы. Учебное пособие./

М.А.Шамашов. Самара: Самарский муниципальный комплекс непрерывного

образования “Университет Наяновой”, 1996, 91 с.

Материал, изложенный в данном пособии, в течении целого ряда лет исполь­зо­вал­ся при чтении курсов лекций на факультете информатики Самарского аэро­кос­ми­чес­кого университета и математическом факультете университета Наяновой. Пособие освещает основные кон­цеп­ции, методы и алгоритмы теории формальных языков - науки, изучающей ма­те­ма­ти­ческие модели языков и имеющей практическую ориентацию на конструирование программной поддержки интеллектуальных языковых интерфейсов для обще­ния человека с ЭВМ в самых различных областях науки и техники.

Пособие, в первую очередь, ориентировано на студентов, изучающих информатику и компьютерные науки, и специалистов, связанных с задачами проектирования системного и прикладного программного обеспечения автоматизированных систем самой различной ориентации. Рекомендуется в качестве учебника для использования в учебном процессе специальностей "Прикладная математика и компьютерные науки", "Автоматизированные системы обработки информации и управления", "Автома­ти­зи­ро­ван­ные информационные системы", "Программное обеспечение вычислительных и автоматизированных систем". Выполнено на кафедре "Прикладной математики и компьютерных наук" университета Наяновой.

Ил. 38. Библ. 15 наим.

Печатается по решению редакционно-издательского совета Самарского муниципального комплекса непрерывного образования “Университет Наяновой”

ПРЕДИСЛОВИЕ

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

Математические понятия теории автоматов и формальных грамматик излогаются строго, но автор счел возможным опустить или схематизировать доказательства целого ряда теорем из-за ограниченных рамок пособия и стремления сделать его доступным широкому кругу читателей, включающих не только математиков, но и студентов технических университетов. Автор считает, что концепции теории формальных грамматик и автоматов служат прекрасной основой не только для обучения основам вычислимости и построения компиляторов, но и для реальной разработки предметно-ориентированных языков. Так, основываясь на этой теории, автор в 1988 году реализовал универсальный символьный процессор, различные модификации которого до сих пор используются при создании предметно-ориентированных языков и обучении.

Пособие рассчитано на студентов, ранее не знакомых с математической лингвистикой и теорией автоматов, поэтому каждое определение или теорема снабжена примерами. В конце большинства разделов даются контрольные вопросы и упражнения, которые могут использоваться при проведении практических занятий, лабораторных работ на ЭВМ, зачетов и экзаменов.

Разделы этого пособия возникли как конспекты курсов лекций, которые в течении ряда лет читаются автором в Самарском аэрокосмическом университете и университете Наяновой. Хочется поблагодарить слушателей, чьи критические замечания, вопросы и недоумевающие взгляды заставляли неоднократно перерабатывать курс. Автор благодарит своих коллег В.В.Куликова, Л.Ф.Штернберга и М.А.Кораблина, совместная работа с которыми способствовала его специализации в теоретических, учебно-методических и практических аспектах данной области знаний.

Дата добавления: 2015-06-27