Е.И.ЧИГАРИНА, М.А. ШАМАШОВ
ТЕОРИЯ КОНЕЧНЫХ
АВТОМАТОВ
И ФОРМАЛЬНЫХ ЯЗЫКОВ
2007
САМАРА
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АЭРОКОСМИЧЕСКИЙ
УНИВЕРСИТЕТ имени академика С.П. КОРОЛЕВА» <...> Е.И.ЧИГАРИНА, М.А.ШАМАШОВ
ТЕОРИЯ КОНЕЧНЫХ
АВТОМАТОВ
И ФОРМАЛЬНЫХ ЯЗЫКОВ
Допущено учебно-методическим советом по прикладной математике
и информатике УМО по классическому университетскому образованию
в качестве учебного пособия для студентов высших учебных заведений,
обучающихся по специальности и направлению «Прикладная математика
и информатика» и по направлению «Информационные технологии»
САМАРА
Издательство СГАУ
2007
УДК 004.43(075)
ББК 32.973
Ч586
ЦИ
ОНАЛЬ
НЫ
ПР
ТЕТНЫЕ
Е
Н
А
О
РИ
ОЕКТЫ
Инновационная образовательная программа
"Развитие центра компетенции и подготовка
специалистов мирового уровня в области аэрокосмических и геоинформационных технологий"
ПР
И
Рецензенты: д-р техн. наук, проф. <...> Теория конечных автоматов и формальных языков: учеб.
пособие / Е.И. Чигарина, М.А. Шамашов. <...> Синтаксический анализ фразы можно записать в виде дерева грамматического
разбора. <...> Обрубив в дереве часть листьев и ветвей, мы
получим сентенциальную форму (выводимую цепочку). <...> 5
<предложение>
<группа подлежащего> <группа сказуемого>
<подлежащее> <сказуемое> <дополнение>
Мать любит дочь
<дополнение> <сказуемое> <подлежащее>
<группа сказуемого> <группа подлежащего>
<предложение>
Эта фраза двусмысленна, так как имеет два варианта синтаксического
разбора. <...> Допустим существование пустой цепочки ε, не содержащей ни одного
символа. <...> Языком L в алфавите A называется множество цепочек в A. <...> Множество { ε }, содержащее только
пустую цепочку, также является языком. <...> a1= a,
Итак, язык L – это некоторое множество цепочек в некотором алфавите A. <...> Грамматика языка – множество объектов: G = <S, VT, VN, R>
S – начальный, выделенный символ грамматики ( аксиома грамматики <...>
Теория_конечных_автоматов_и_формальных_языков.pdf
Е.И.ЧИГАРИНА, М.А. ШАМАШОВ
ТЕОРИЯ КОНЕЧНЫХ
АВТОМАТОВ
И ФОРМАЛЬНЫХ ЯЗЫКОВ
2007
САМАРА
Стр.1
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АЭРОКОСМИЧЕСКИЙ
УНИВЕРСИТЕТ имени академика С.П. КОРОЛЕВА»
Е.И.ЧИГАРИНА, М.А.ШАМАШОВ
ТЕОРИЯ КОНЕЧНЫХ
АВТОМАТОВ
И ФОРМАЛЬНЫХ ЯЗЫКОВ
Допущено учебно-методическим советом по прикладной математике
и информатике УМО по классическому университетскому образованию
в качестве учебного пособия для студентов высших учебных заведений,
обучающихся по специальности и направлению «Прикладная математика
и информатика» и по направлению «Информационные технологии»
С А М А Р А
Издательство СГАУ
2007
Стр.2
УДК 004.43(075)
ББК 32.973
Ч586
Инновационная образовательная программа
"Развитие центра компетенции и подготовка
специалистов мирового уровня в области аэрокосмических
и геоинформационных технологий"
Рецензенты: д-р техн. наук, проф. А. А. К а л е н т ь е в,
д-р техн. наук, проф. М. А. К о р а б л и н
Чигарина Е.И.
Ч586
Теория конечных автоматов и формальных языков: учеб.
пособие / Е.И. Чигарина, М.А. Шамашов. – Самара: Изд-во
Самар. гос. аэрокосм. ун-та, 2007. – 96 с. : ил.
ISBN 978-5-7883-0506-6
В данном учебном пособии изложены основные концепции,
методы и алгоритмы теории формальных языков - науки, изучающей
математические модели языков и имеющей практическую
ориентацию на конструирование программной поддержки
интеллектуальных языковых интерфейсов для общения человека с
ЭВМ в самых различных областях науки и техники.
Пособие ориентировано на студентов очной и заочной форм
обучения, изучающих информатику и компьютерные науки, и
специалистов, связанных с задачами проектирования системного и
прикладного программного обеспечения автоматизированных систем
самой различной ориентации. Рекомендуется в качестве учебного
пособия для студентов высших учебных заведений, обучающихся по
специальностям: 010500 – Прикладная математика и информатика,
010400 – Информационные технологии по курсам «Языки
программирования и методы трансляции», «Теория конечных
автоматов и формальных языков».
Утверждено редакционно-издательским советом университета в
качестве учебного пособия
ISBN 978-5-7883-0506-6
© Чигарина Е.И., Шамашов М.А., 2007
© Самарский государственный
аэрокосмический университет, 2007
2
П
Р
И
О
Р
И
Т
Т
К
Е
Т
О
Н
Ы
Е
Н
А
Ц
И
О
А
Н
Л
Ь
Н
Ы
Е
П
Р
Е
Ы
Стр.3