Предметный указатель

автомат детерминированный конечный, 18

недетерминированный конечный, 16, 24

алфавит, 7 алфавит входной, 19 гомоморфизм, 59

гомоморфный образ, 60 грамматика леволинейная, 51 праволинейная, 51 грамматики эквивалентные, 14 грамматический разбор, 76 граф зависимости, 94 диаграмма переходов, 19 длина строки, 7 дополнение, 9 замыкание Клини, 10 звездочка, 10 информация входная, 15 итерация языка, 9 конкатенация, 7

леворекурсивные продукции, 91 лемма о расширении для контекстно-свободных языков, 136

лемма о расширении регулярных языков, 64 минимизация конечных автоматов, 32

неоднозначность грамматик, 81 нетерминалы, 12 нисходящий разбор, 77 нормальные формы, 87 Грейбах, 87, 107 Хомского, 87, 103 обнуляемый нетерминал, 98 обращение, 7

однозначность грамматик, 81 подстрока, 8 полный перебор, 77

правила подстановки, 88 префикс строки, 8 продукция, 12 пустая строка, 8

распознаватель, 17, 18, 24 регулярное пересечение, 144 регулярный язык, 23 сентенциальная форма, 13 сентенция, 13 слово, 13 состояние внутреннее, 19 заключительное, 19 начальное, 19 недостижимое, 33 неразличимое, 33 различимое, 34

стандартное представление, 62 строка, 7 строка входная, 15 суффикс строки, 8 сцепление, 9 теорема Клини, 48 терминалы, 12

устройство временной памяти, 15

устройство управления, 15 формальный язык, 8 функция переходов, 19, 25 цепная продукция, 100 эквивалентные автоматы, 28 язык автоматный, 23 однозначный, 85

порождаемый грамматикой, 13 существенно неоднозначный, 85