Часовой пояс: UTC + 3 часа [ Летнее время ]

Магазинные автоматы (автомат с магазинной памятью)
Онлайн-сервисы Нахождение НОД и НОК Разложение числа на простые множители Сравнения по модулю Операции над множествами Операции над векторами Разложение вектора по базису. Доказательство, что векторы образуют базис Чертёж треугольника по координатам вершин Решение треугольника Решение Пирамиды Построение Пирамиды по координатам вершин Чертёж многоугольника по координатам вершин Решение систем методом Крамера и Матричным Онлайн построение графика кривой 2-го порядка Определение вида кривой или поверхности 2-го порядка по инвариантам МНК и регрессионный анализ Онлайн + графики Онлайн число, сумма и дата прописью Алгоритмы JavaScript Алгоритмы поиска Алгоритмы сортировки Уникальные элементы массива Объединение, пересечение и разность массивов НОД и НОК Операции над матрицами Дата прописью Введение в анализ Функции: понятие, определение, графики Непрерывность функции Исследование функции и построение графика Теория множеств Множества: понятие, определение, примеры Точечные множества Замкнутые и открытые множества Мера множества Группы, кольца, поля в математике Поле комплексных чисел Кольцо многочленов Основная теорема алгебры и ее следствия Математическая логика Алгебра высказываний Аксиоматика и логические рассуждения Методы доказательств теорем Алгебра высказываний и операции над ними Формулы алгебры высказываний Тавтологии алгебры высказываний Логическая равносильность формул Нормальные формы для формул высказываний Логическое следование формул Приложение алгебры высказываний для теорем Дедуктивные и индуктивные умозаключения Решение логических задач Принцип полной дизъюнкции Булевы функции Множества, отношения и функции в логике Булевы функции от одного и двух аргументов Булевы функции от n аргументов Системы булевых функций Применение булевых функций к релейно-контактным схемам Релейно-контактные схемы в ЭВМ Практическое применение булевых функций Теория формального Формализованное исчисление высказываний Полнота и другие свойства формализованного исчисления высказываний Независимость системы аксиом формализованного исчисления высказываний Логика предикатов Логика предикатов Логические операции над предикатами Кванторные операции над предикатами Формулы логики предикатов Тавтологии логики предикатов Преобразования формул и следование их предикатов Проблемы разрешения для общезначимости и выполнимости формул Применение логики предикатов в математике Строение математических теорем Аристотелева силлогистика и методы рассуждений Принцип полной дизъюнкции в предикатной форме Метод полной математической индукции Необходимые и достаточные условия Логика предикатов и алгебра множеств Формализованное исчисление предикатов Неформальные и формаль- ные аксиоматические теории Неформальные аксиоматические теории Свойства аксиоматических теорий Формальные аксиоматические теории Формализация теории аристотелевых силлогизмов Свойства формализованного исчисления предикатов Формальные теории первого порядка Формализация математической теории Теория алгоритмов Интуитивное представление об алгоритмах Машины Тьюринга и тезис Рекурсивные функции Нормальные алгоритмы Маркова Разрешимость и перечислимость множеств Неразрешимые алгоритмические проблемы Теорема Гёделя о неполноте формальной арифметики Математическая логика и компьютеры Математическая логика и языки программирования Применение компьютеров для доказательства теорем математической логики Математическая логика и логическое программирование Математическая логика и информатика Математическая логика и искусственный интеллект Дискретная математика Множества и отношения Теория множеств: понятия и определения Операции над множествами Кортеж и декартово произведение множеств Соответствия и бинарные отношения на множествах Операции над соответствиями на множествах Семейства множеств Специальные свойства бинарных отношений Отношения эквивалентности на множестве Упорядоченные множества Теорема о неподвижной точке Мощность множества Парадокс Рассела Метод характеристических функций Группы и кольца Алгебраические структуры и операции Группоиды, полугруппы, группы Кольца, тела, поля Области целостности в теории колец Модули и линейные пространства Подгруппы и подкольца Теорема Лагранжа о порядке конечной группы Гомоморфизмы групп и нормальные делители Гомоморфизмы и изоморфизмы колец Алгебра кватернионов Полукольца и булевы алгебры Полукольца: определение, аксиомы, примеры Замкнутые полукольца Полукольца и системы линейных уравнений Булевы алгебры и полукольца Решетки и полурешетки Алгебраические системы Алгебраические системы: модели и алгебры Подсистемы алгебраических систем Конгруэнции и фактор-системы Гомоморфизмы алгебраических систем Прямые произведения алгебраических систем Конечные булевы алгебры Многосортные алгебры Теория графов Теория графов: основные понятия и определения Способы представления графов Неориентированные и ориентированные деревья Остовное дерево и алгоритм Краскала Методы систематического обхода вершин графа Алгоритмы поиска в глубину и ширину в графах Задача о путях во взвешенных ориентированных графах Изоморфизм, гомоморфизм и автоморфизм графов Топологическая сортировка вершин графа Элементы цикломатики в теории графов Булева алгебра и функции Булевы функции и булев куб Таблицы булевых функций и булев оператор Равенство булевых функций. Фиктивные переменные Формулы и суперпозиции булевых функций Дизъюнктивные и конъюнктивные нормальные формы Построение минимальных ДНФ Теорема Поста и классы Критерий Поста Схемы из функциональных элементов Конечные автоматы и регулярные языки Конечные автоматы и регулярные языки Алфавит, слово, язык в программировании Порождающие грамматики (грамматики Хомского) Классификация грамматик и языков Регулярные языки и регулярные выражения Конечные автоматы Допустимость языка конечным автоматом Теорема Клини Детерминизация конечных автоматов Минимизация конечных автоматов Лемма о разрастании для регулярных языков Обоснование алгоритма детерминизации автоматов Конечные автоматы с выходом Морфизмы и конечные подстановки Машины Тьюринга Контекстно-свободные языки Контекстно-свободные языки и грамматики Приведенная форма КС-грамматики Лемма о разрастании для КС-языков Магазинные автоматы (автомат с магазинной памятью) Алгоритм построения МП-автомата по КС-грамматике Алгоритм построения КС-грамматики по МП-автомату Алгебраические свойства КС-языков Основное свойство суперпозиции КС-языков Пересечение контекстно-свободных языков Методы синтаксического анализа КС-языков Восходящий синтаксический анализ и LR(k)-грамматики Семантика формальных языков Принцип индукции по неподвижной точке Графовое представление МП-автоматов Интегральное исчисление Неопределённый и определённый Неопределенный и определенный интегралы Свойства интегралов Интегрирование по частям Интегрирование методом замены переменной Интегрирование различных рациональных функций Интегрирование различных иррациональных функций Интегрирование различных тригонометрических функций Определенный интеграл и его основные свойства Необходимое и достаточное условие интегрируемости Теоремы существования первообразной Свойства определенных интегралов Несобственные интегралы Интегральное определение логарифмической функции Приложения интегралов Вычисление площадей плоских фигур Площади фигур в различных координатах Вычисление объемов тел с помощью интегралов Объём тела вращения Вычисление длин дуг кривых Формулы длины дуги регулярной кривой Кривизна плоской кривой Площадь поверхности вращения тела Интегралы в физике Статические моменты и координаты центра тяжести Теоремы Гульдина–Паппа Вычисление моментов инерции Другие приложения интегралов в физике Основные интегралы Интеграл Ньютона-Лейбница Интеграл Римана Интеграл Лебега Вариационное исчисление Примеры вариационных задач Дифференциальное уравнение Эйлера Функционалы, зависящие от нескольких функций Задача о минимуме кратного интеграла Финансовый анализ Анализ эффективности Критерии и показатели эффективности предприятия Методы анализа эффективности деятельности Факторный анализ прибыли от операционной деятельности Анализ безубыточности предприятия Операционный рычаг и эффект финансового рычага Анализ и оценка состава, структуры и динамики доходов и расходов Анализ рентабельности и резервов устойчивого роста капитала Анализ распределения прибыли предприятия Анализ и оценка чувствительности показателей эффективности Анализ устойчивости Финансовая устойчивость и долгосрочная платежеспособность Характеристика типов финансовой устойчивости Рыночная активность Финансовый анализ рыночной активности Методика анализа рыночной активности Анализ и оценка дивидендного дохода на одну акцию Инвестиционная деятельность Инвестиции: экономическая сущность и классификация Государственное регулирование инвестиционной деятельности Источники финансовых ресурсов на капитальные вложения Инвестиции в основные фонды Оценка состояния основных фондов Амортизация основных фондов Капитальное строительство в инвестиционном процессе Планирование инвестиций в форме капитальных вложений Экономическая эффективность инвестиций Финансирование капитальных вложений Кредитование капитальных вложений Кредитоспособность Финансирование и кредитование затрат Финансирование и кредитование инвестиционной деятельности потребительской кооперации Финансирование и кредитование капитальных вложений потребительской кооперации Инвестиционное строительное проектирование Анализ инвестиций Инвестиции и инвестиционная деятельность предприятия Задачи финансового анализа инвестиций предприятия Учет фактора времени в инвестиционной деятельности Аннуитет и финансовая рента в инвестициях Учет фактора инфляции при инвестировании Оценка фактора риска инвестиционного проекта Методы оценки эффективности инвестиций Показатели эффективности инвестиционного проекта Стоимость компании Концепция построения международных стандартов финансовой отчетности (МСФО) Экономическое содержание международных стандартов финансовой отчётности Цели и принципы оценки стоимости акций и активов компании Оценка акций и активов предприятия по справедливой стоимости Методы оценки справедливой стоимости акций предприятия Затратный подход к оценки стоимости компаний и акций Сравнительный подход к оценки стоимости предприятий и акций Доходный подход к оценке стоимости компании и акций Выбор ставки дисконтирования при инвестировании в акции Метод капитализации прибыли Сравнение подходов к оценке стоимости компаний и пакетов акций Форвардные контракты Форвардный контракт и цена Форвардная цена акции на бирже Цена форвардного контракта инвестора Форвардная цена акции с учетом величины дивиденда Форвардная цена акции с учетом ставки дивиденда Форвардная цена валюты на рынке форекс Форвардный валютный курс и инфляция на рынке Форвардная цена товара и спотовый рынок Форвардная цена при различии ставок по кредитам и депозитам Синтетический форвардный контракт на акции и валюту Теория вероятностей Основные понятия теории вероятностей Зависимые и независимые случайные события Повторные независимые испытания Формула Бернулли Одномерные случайные величины Многомерные случайные величины Функции случайных величин Законы распределения целочисленных случайных величин Законы распределения непрерывных случайных величин Предельные теоремы теории вероятностей Закон больших чисел и предельные теоремы Вероятностные закономерности Математическая статистика Элементы математической статистики Выборочный метод Оценки параметров генеральной совокупности Статистические гипотезы Критерии согласия Теоретические и эмпирические частоты Теория очередей (СМО) Определение системы массового обслуживания Уравнения Колмогорова Предельные вероятности состояний Определение СМО с отказами Определение СМО с ожиданием (очередью) Аналитическая геометрия Векторная алгебра Метрические понятия и аксиомы геометрии Равенство и подобие геометрических фигур Бинарные отношения Вектор, его направление и длина Линейные операции над векторами Линейная зависимость и независимость векторов Отношение коллинеарных векторов Проекции векторов на прямую и на плоскость Угол между векторами Ортогональные проекции векторов Координата вектора на прямой и базис Координаты вектора на плоскости и базис Координаты вектора в пространстве и базис Операции над векторами в координатной форме Ортогональный и ортонормированный базисы Cкалярное произведение векторов и его свойства Выражение скалярного произведения через координаты векторов Векторное произведение векторов и его свойства Смешанное произведение векторов и его свойства Ориентированные площади и объемы Двойное векторное произведение и его свойства Применение векторов в задачах на аффинные свойства фигур Применение произведений векторов при решении геометрических задач Применение векторной алгебры в механике Системы координат Прямоугольные координаты Преобразования прямоугольных координат Полярная система координат Цилиндрическая система координат Сферические координаты Аффинные координаты Аффинные преобразования координат Аффинные преобразования плоскости Примеры аффинных преобразований плоскости Аффинные преобразования пространства Многомерное координатное пространство Линейные и аффинные подпространства Скалярное произведение n-мерных векторов Преобразования систем координат Геометрия на плоскости Алгебраические линии на плоскости Общие уравнения геометрических мест точек Алгебраические уравнения линий на плоскости Уравнения прямой, проходящей через точку перпендикулярно вектору Уравнения прямой, проходящей через точку коллинеарно вектору Уравнения прямой, проходящей через две точки Уравнения прямой с угловым коэффициентом Взаимное расположение прямых Примеры задач с прямыми на плоскости Системы неравенств с двумя неизвестными Системы линейных уравнений с двумя неизвестными Линии 2-го порядка Канонические уравнения линий второго порядка Порядок приведения уравнения линии к каноническому виду Эллипс Гипербола Парабола Квадратичные неравенства с двумя неизвестными Применение линий 1-го и 2-го порядков в задачах на экстремум функций Инварианты линий Классификация линий 2-го порядка по инвариантам Приведение уравнения линии к каноническому виду по инвариантам Геометрия в пространстве Способы задания ГМТ в пространстве Алгебраические уравнения поверхностей Уравнения плоскости, проходящей через точку перпендикулярно вектору Уравнения плоскости, компланарной двум неколлинеарным векторам Уравнения плоскости, проходящей через три точки Взаимное расположение плоскостей Типовые задачи с плоскостями Уравнения прямых в пространстве Взаимное расположение прямых в пространстве Типовые задачи с прямыми в пространстве Поверхности 2-го порядка Канонические уравнения поверхностей Порядок приведения уравнения поверхности к каноническому виду Поверхности второго порядка Эллипсоиды Гиперболоиды Конусы Параболоиды Применение поверхностей 1-го и 2-го порядков в задачах на экстремум функций Инварианты поверхностей Классификация поверхностей 2-го порядка по инвариантам Квадратичные неравенства с тремя неизвестными Приведение уравнения поверхности к канониче-скому виду по инвариантам Линейная алгебра Матрицы и операции Линейные операции над матрицами Умножение матриц Возведение матриц в степень Многочлены от матриц Транспонирование и сопряжение матриц Блочные матрицы Произведение и сумма матриц Кронекера Метод Гаусса приведения матрицы к ступенчатому виду Элементарные преобразования матриц Определители Определители матриц и их основные свойства Формула полного разложения определителя Формула Лапласа полного разложения определителя Определитель произведения матриц Методы вычисления определителей Ранг матрицы Линейная зависимость и линейная независимость строк (столбцов) матрицы Ранг матрицы и базисный минор матрицы Методы вычисления ранга матрицы Ранг системы столбцов (строк) Обратная матрица Обратные матрицы и их свойства Ортогональные и унитарные матрицы Способы нахождения обратной матрицы Матричные уравнения Односторонние обратные матрицы Скелетное разложение матрицы Полуобратная матрица Псевдообратная матрица Системы уравнений Системы линейных алгебраических уравнений Метод Гаусса решения систем линейных уравнений Структура общего решения системы уравнений Решение систем с помощью полуобратных матриц Псевдорешения системы линейных уравнений Функциональные матрицы Функциональные матрицы скалярного аргумента Производные матриц по векторному аргументу Линейные и квадратичные формы и их преобразования Приведение форм к каноническому виду Закон инерции вещественных квадратичных форм Знакоопределенность форм вещественных квадратичных Формы и исследование функций на экстремум Многочленные матрицы Многочленные матрицы (лямбда-матрицы) Операции над лямбда-матрицами Простые преобразования многочленных матриц Инвариантные множители многочленной матрицы Функции от матриц Собственные векторы и значения матрицы Подобие числовых матриц Характеристический многочлен матрицы Минимальный многочлен матрицы Теорема Гамильтона-Кэли Жорданова форма матрицы Приведение матрицы к жордановой форме Многочлены от матриц Применение многочленов от матриц Функции от матриц Линейные пространства Линейные пространства: определение и примеры Линейная зависимость и независимость n-мерных векторов Размерность и базис линейного пространства Преобразования координат в линейном пространстве Изоморфизм линейных пространств Подпространства Подпространства линейного пространства Пересечение и сумма подпространств Способы описания подпространств Нахождение дополнения и суммы подпространств Нахождение пересечения подпространств Линейные отображения Линейные многообразия Линейные отображения Матрица линейного отображения Ядро и образ линейного отображения Линейные операторы Линейные операторы (преобразования) Инвариантные подпространства Собственные векторы и значения оператора Свойства собственных векторов операторов Канонический вид линейного оператора Методика приведения линейного преобразования к каноническому виду Евклидовы пространства Евклидовы пространства Ортогональные векторы евклидова пространства Ортогональный базис евклидова пространства Ортонормированный базис евклидова пространства Ортогональные дополнения в евклидовом пространстве Задача о перпендикуляре Матрица и определитель Грама и его свойства Линейные преобразования евклидовых пространств Канонический вид ортогонального оператора евклидова пространства Сопряженные операторы евклидова пространства Самосопряженные операторы евклидова пространства Приведение квадратичной формы к главным осям Унитарные пространства и их линейные преобразования Комплексный анализ Комплексные числа Комплексные числа в алгебраической форме Комплексные числа в тригонометрической и показательной формах Множества на комплексной плоскости Последовательности и ряды комплексных чисел Комплексные функции Функции комплексного переменного. Предел, непрерывность и производная Элементарные функции комплексного переменного Дифференцирование функций комплексного переменного Аналитические функции и их свойства Конформные отображения и их свойства Интегрирование функций комплексного переменного Функциональные ряды в комплексной области Функциональные ряды и последовательности Степенные ряды и их свойства Разложение функций в степенные ряды Нули аналитических функций Ряд Лорана и разложение функций по целым степеням Особые точки, Вычеты Изолированные особые точки функций и полюсы Вычеты и их применение Вычисление интегралов с помощью вычетов Вычеты и расположение нулей многочлена Операционное исчисление Преобразование Лапласа и его свойства Решение ДУ операционным методом Анализ выходных процессов линейных стационарных систем Z-преобразование и его свойства Дифференциальные уравнения ДУ первого порядка Основные понятия и определения ДУ Метод изоклин для ДУ 1-го порядка Метод последовательных приближений ДУ с разделяющимися переменными Однородные ДУ Линейные ДУ 1-го порядка Дифференциальное уравнение Бернулли ДУ в полных дифференциалах Интегрирующий множитель ДУ, не разрешенные относительно производной Дифференциальное уравнение Риккати Составление ДУ семейств линий Задачи на траектории Особые решения ДУ ДУ высших порядков Понятия и определения ДУ высших порядков ДУ, допускающие понижение порядка Линейная независимость функций Определители Вронского и Грама Однородные и неоднородные дифференциальные уравнения Задача Коши и Уравнение Эйлера Линейные ДУ с переменными коэффициентами Метод Лагранжа решения ДУ Краевые задачи для ДУ высших порядков Разложение решения ДУ в степенной ряд Разложение решения ДУ в обобщенный степенной ряд Нахождение периодических решений ДУ Асимптотическое интегрирование ДУ Системы ДУ Системы ДУ: понятия и определения Сведение системы ДУ к одному уравнению Нахождение интегрируемых комбинаций Интегрирование однородных линейных систем ДУ Методы интегрирования неоднородных систем ДУ Преобразование Лапласа и решение ДУ и систем Теория устойчивости Устойчивость решений ДУ по Ляпунову Простейшие типы точек покоя Метод функций Ляпунова Устойчивость решений ДУ по первому приближению Критерии устойчивости Рауса–Гурвица и Михайлова ДУ с малым параметром при производной Численные методы Методы алгебры Численные методы линейной алгебры Численные методы решения СЛАУ Итерационный метод Шульца обратной матрицы Методы решения задач о собственных значениях и векторах матрицы Методы решения нелинейных уравнений Методы решения систем нелинейных уравнений Методы теории приближений Методы приближения сеточных функций Методы функциональной интерполяции Методы интегрально-дифференциальной интерполяции Методы интегрального сглаживания Методы интерполяции и сглаживания сплайнами Методы численного дифференцирования и интегрирования Методы численного дифференцирования Методы численного интегрирования Методы решения обыкновенных ДУ Численные методы решения задачи Коши Разностные схемы для решения задачи Коши Составные схемы для решения задачи Коши Экстраполяционные методы решения задачи Коши Непрерывно-дискретные методы решения задачи Коши Численные методы решения краевых задач Методы решения ДУ в частных производных Численные методы решения уравнений математической физики с двумя переменными Принципы построения разностных схем для уравнений в частных производных Разностные схемы решения уравнений в частных производных 1-го порядка Разностные схемы решения уравнений в частных производных 2-го порядка Численные методы решения уравнений в частных производных Численные методы решения уравнений математической физики с тремя переменными	Магазинные автоматы (автомат с магазинной памятью) Автоматы с магазинной памятью, или магазинные автоматы (сокращенно — МП-автоматы), образуют класс распознающих моделей для КС-языков точно так же, как конечные автоматы являются распознающими моделями в классе регулярных языков. Понятие МП-автомата является частным случаем общего интуитивного понятия автомата, которое мы ввели ранее. Как и всякий автомат, МП-автомат — это устройство, имеющее блок управления, входную ленту, головку и блок внутренней памяти в виде магазина МП-автомата (или стека). Блок управления в каждый момент времени находится в одном из конечного множества $Q$ состояний. Входная лента предполагается "полубесконечной", т.е. она имеет начало ("левый край"), но не имеет конца. Лента разделена на ячейки, пронумерованные от крайней левой ячейки натуральными числами, начиная с единицы; в каждой ячейке может быть записан символ алфавита $V$ , называемого входным алфавитом МП-автомата. В каждый момент времени читающая головка обозревает (или читает) некоторую ячейку входной ленты. Если в этой ячейке записан некоторый входной символ, т.е. символ входного алфавита, то его называют обозреваемым (в данный момент) входным символом (рис. 8.28). Предполагается, что если на ленте записана некоторая непустая цепочка $x=x(1)x(2)\ldots x(k)$ во входном алфавите, то ее символы последовательно записаны в ячейках от первой до k-й, без пропусков, так, что символ $x(i)$ записан в i-й ячейке (рис. 8.29). МП-автомат может читать цепочку $x$ , продвигая головку только в одном направлении, слева направо, по шагам, причем за каждый шаг головка переходит от обозреваемой ячейки к следующей. Если в какой-то момент времени обозревается символ $x(i),~1\leqslant i\leqslant k$ , записанной на ленте цепочки $x$ , то непрочитанной частью входной цепочки $x$ будет подцепочка $x(i+1)\ldots x(k)$ . В частности, при $i=k$ непрочитанная часть совпадает с пустой цепочкой, и тогда говорят, что цепочка $x$ полностью прочитана МП-автоматом (рис. 8.30). Устройство и работа магазина МП-автомата Магазин МП-автомата устроен и работает следующим образом. Как и входная лента, магазин является полубесконечным и разделенным на пронумерованные ячейки, в каждой из которых может быть записан символ алфавита $\Gamma$ , называемого магазинным алфавитом МП-автомата. Входной и магазинный алфавиты МП-автомата могут пересекаться и даже совпадать друг с другом. Символы алфавита $\Gamma$ называют магазинными символами. Первую ячейку магазина называют его верхней ячейкой (иногда просто верхом магазина). Символ, в данный момент записанный в верхней ячейке магазина, называют верхним символом магазина. Таким образом, в неформальном описании МП-автомата лента читается "слева направо", а магазин — "сверху вниз". Единственная операция, которую МП-автомат может реализовать с магазином, состоит в следующем: верхний символ $Z$ магазина заменяется некоторой цепочкой $\gamma$ магазинных символов. При этом если цепочка $\gamma$ непустая, то она записывается в первых $m$ ячейках, где $m=\|\gamma\|$ (длине цепочки $\gamma$ ), так, что ее первый символ становится верхним символом магазина. Если до замены $Z$ цепочкой $\gamma$ под верхней ячейкой (т.е. в ячейках, начиная со второй) была записана какая-то цепочка а, то после замены она сдвигается "в глубь" магазина и оказывается записанной уже в ячейках, начиная с (m+1)-й (рис. 8.31). Полагают, что, как и символы цепочек на входной ленте, символы цепочек, записанных в магазин, располагаются в последовательных ячейках "сверху вниз" без пропусков ячеек. Если же верхний символ $Z$ заменяется пустой цепочкой $\lambda$ , то после такой замены верхним символом магазина становится первый символ цепочки $\alpha$ (записанной под верхней ячейкой магазина), т.е. цепочка $\alpha$ "поднимается" на одну ячейку. В случае, когда $\alpha$ — пустая цепочка, замена верхнего символа магазина пустой цепочкой $\gamma$ приводит к опустошению магазина (ни в одной из ячеек магазина не записан магазинный символ). Заметим, что, по определению, с пустым магазином МП-автомат не может производить никаких операций. Описанная выше операция с магазином составляет основу поведения МП-автомата, его, образно говоря, "динамику". Эта "динамика" определяется системой команд МП-автомата, которая, аналогично системе команд конечного автомата, определяется как конечное множество $\delta$ команд, каждая из которых записывается в виде $qaZ\to r\gamma,$ (8.8) где $q$ и $r$ — состояния из множества $Q$ ; $a$ — входной символ или пустая цепочка; $Z$ — магазинный символ; $\gamma$ — цепочка магазинных символов (может быть и пустая). Если в системе команд $\delta$ МП-автомата $M$ есть команда (8.8), то $M$ может в данный момент времени выполнить эту команду, если и только если в данный момент времени его блок управления находится в состоянии $q$ , головка обозревает входной символ $a$ (при условии, что $a\ne\lambda$ ), а верхним символом магазина является символ $Z$ . Выполнение команды (8.8) состоит в замене верхнего символа магазина цепочкой $\gamma$ (как это описано выше), переходе блока управления в состояние $r$ (которое может и совпадать с состоянием $q$ ) и в продвижении головки на одну ячейку вправо (если а в команде (8.8) не есть пустая цепочка $\lambda$ ) (рис. 8.32). Если же в команде (8.8) $a=\lambda$ , то такую команду МП-автомат может выполнить всякий раз, когда его блок управления окажется в состоянии $q$ , а верхним символом магазина будет символ $Z$ . В этом случае выполнение команды никак не зависит от содержимого входной ленты, а после ее выполнения головка остается на прежнем месте. Рассмотренную выше процедуру выполнения команды вида (8.8) называют шагом (или тактом) работы МП-автомата (при $a=\lambda$ такт работы называют λ-тактом). Предположим теперь, что в множестве состояний $Q$ блока управления МП-автомата $M$ с системой команд $\delta$ фиксировано некоторое начальное состояние $q_0$ и подмножество заключительных состояний $F$ . Пусть в какой-то начальный момент времени блок управления МП-автомата $M$ находится в начальном состоянии $q_0$ , налейте записана непустая цепочка $x$ , головка обозревает первую ячейку ленты и, следовательно, первый символ цепочки $x$ является обозреваемым, а в магазине записан только один специальный символ $Z_0$ , называемый начальным символом магазина. Тогда, если МП-автомат $M$ , выполняя некоторую последовательность команд из $\delta$ , прочитывает полностью цепочку $x$ , в результате чего блок управления переходит в некоторое заключительное состояние $q_f\in F$ , говорят, что МП-автомат $M$ допускает (распознает, воспринимает) цепочку $x$ , которую называют допустимой цепочкой МП-автомата. Множество всех допустимых цепочек МП-автомата $M$ образует язык, допускаемый этим МП-автоматом. Далее мы докажем, что язык любого МП-автомата является КС-языком и, наоборот, любой КС-язык есть язык некоторого МП-автомата. В этом смысле мы и говорим об МП-автоматах как о "распознавателях" КС-языков: всякий МП-автомат допускает те и только те цепочки входных символов, которые порождаются некоторой КС-грамматикой. Но чтобы доказывать какие-либо утверждения об МП-автоматах, нужно сначала дать строгое математическое определение этого понятия, не апеллируя уже к наглядным, но не определенным формально идеям ленты, магазина, головки и т.п. Формализация изложенного выше описания проводится во многом аналогично построению определения порождающей грамматики. Определение 8.7. МП-автомат задается упорядоченной семеркой $M=(Q,V,\Gamma,q_0,F,Z_0,\delta),$ где $Q$ — конечное множество состояний; $V$ — алфавит, называемый входным алфавитом; $\Gamma$ — алфавит, называемый магазинным алфавитом; $q_0\in Q$ — начальное состояние; $F\subseteq Q$ — подмножество заключительных состояний; $Z_0\in\Gamma$ — начальный магазинный символ; $\delta$ — система команд, определенная как конечное множество команд, каждая из которых записывается в виде (8.8): $qaZ\to r\gamma$ , где знак " $\to$ " (стрелка) — внешний символ (не принадлежащий ни одному из указанных алфавитов); $q,r\in Q;\qquad a\in V\cup\{\lambda\};\qquad Z\in\Gamma;\qquad \gamma\in \Gamma^{\ast}.$ Замечание 8.8. Нелишне обратить внимание на то, что упоминание о ленте и магазине в приведенном выше формальном определении совершенно необязательно. Формально для определения МП-автомата достаточно задать два алфавита, конечное множество состояний, выделив в нем начальное состояние и подмножество заключительных состояний, а также систему команд. Образы ленты, магазина, да и сам термин "состояние", являются метафорами, которые позволяют связать формальное определение с его содержательной интерпретацией, идеей некоего "устройства" для чтения слов, с описания которого мы начали этот параграф. Любую цепочку в алфавите $V$ будем называть входной цепочкой, а сами элементы входного алфавита — входными символами; точно так же любую цепочку в алфавите $\Gamma$ будем называть магазинной цепочкой, а символы этого алфавита — магазинными символами. Упорядоченную тройку до знака " $\to$ " (стрелки) в записи команды называют левой частью команды, а упорядоченную пару после знака " $\to$ " — правой частью команды. Пример 8.14. Рассмотрим МП-автомат $M_1=(\{q_0,q_1,q_2\}, \{0;1\}, \{Z,0\}, q_0, \{q_0\},Z,\delta_1)$ с таким множеством команд $\delta_1\colon$ $q_00Z\to q_1\,0Z,\quad q_000\to q_1\,00,\quad q_110\to q_2\lambda,\quad q_210\to q_2\lambda,\quad q_2\lambda Z\to q_0\lambda.$ На рис. 8.33 проиллюстрировано выполнение первых двух команд. При записи системы команд этого конкретного МП-автомата мы в правых частях первых двух команд отделили магазинную цепочку от состояния пробелом для того, чтобы не возник соблазн прочитать левую и правую части этих команд одинаково. Таким приемом записи мы хотим подчеркнуть, что левая часть команды МП-автомата — упорядоченная! тройка, а правая — упорядоченная пара. Замечание 8.9. Систему команд МП-автомата можно понимать как способ определения некоторой конечной функции, которую называют функцией переходов МП-автомата (по аналогии с функцией переходов конечного автомата). Эта функция может быть определена как отображение вида $\delta\colon Q\times(V\cup\{\lambda\})\times\Gamma\to \mathbf{Fin}(Q\times \Gamma^{\ast}),$ где использовано обозначение $\mathbf{Fin}(A)$ для множества всех конечных подмножеств множества $A$ . "Динамику" МП-автомата, т.е. процесс перехода его из одного состояния в другое в соответствии с обозреваемыми символами на ленте и содержимым магазина, удобнее всего описывать в терминах конфигураций. Для этого общее понятие конфигурации автомата, которое на интуитивном уровне было введено в 7.5, необходимо уточнить применительно к МП-автомату и определить также отношение выводимости на множестве конфигураций. Определение 8.8. Конфигурацией МП-автомата $M$ называют упорядоченную тройку вида $(q,x,\beta)$ , где $q\in Q$ — состояние, $x\in V^{\ast}$ — входная цепочка, $\beta$ — магазинная цепочка. Конфигурацию $C'=(r,w,\gamma\alpha)$ называют непосредственно выводимой из конфигурации $C=(q,aw,Z\alpha)$ , если в множестве команд МП-автомата есть команда (8.8). Отношение непосредственной выводимости на множестве конфигураций МП-автомата $M$ обозначаем $\vdash_M$ , используя запись $C\vdash_{M}C'$ (и опуская, если это не вредит пониманию, обозначение самого МП-автомата). Итак, непосредственная выводимость $(q,aw,Z\alpha)\vdash_{M}(r,w,\gamma\alpha)$ (8.9) имеет место тогда и только тогда, когда в системе $\delta$ команд МП-автомата $M$ есть команда (8.8), которую в этом случае называют применимой к конфигурации $(q,aw,Z\alpha)$ . Таким образом, неформально конфигурация показывает состояние блока управления, непрочитанную часть входной цепочки (первый символ этой цепочки, если она не пуста, является обозреваемым) и содержимое магазина (первый символ магазинной цепочки $\beta$ , если она не пуста, есть верхний символ магазина). Если вторая компонента конфигурации — пустая цепочка, то это означает, что входная цепочка прочитана полностью. Если же пуста третья компонента, то это означает, что пуст магазин. На рис. 8.33 изображены (в терминах приведенного выше содержательного описания) две конфигурации МП-автомата из примера 8.14, причем вторая конфигурация непосредственно выводится из первой. Понятие непосредственной выводимости, таким образом, формализует данное выше понятие такта '(или шага) работы МП-автомата. Заметим, что если в (8.9) и в команде (8.8) $a=\lambda$ , т.е. имеет место λ-такт, то команда (8.8) применима к любой конфигурации, у которой (говоря неформально) состояние блока управления есть $q$ , а верхний символ магазина — $Z$ , причем, подчеркнем это, независимо от содержимого входной ленты (т.е. для любой входной цепочки $w$ ). Если же $a$ есть входной символ, то применимость команды к конфигурации определяется состоянием, обозреваемым символом на ленте и верхним символом магазина. Любую конфигурацию вида $(q_0,x,Z_0)$ называют начальной, а любую конфигурацию вида $(q_f,\lambda,\lambda)$ , где $q_f\in F$ , — заключительной. Обратим внимание на то, что заключительная конфигурация — это конфигурация с пустым магазином. Множество всех заключительных конфигураций находится, таким образом, во взаимно однозначном соответствии с множеством заключительных состояний МП-автомата. Из заключительной конфигурации не может быть выведена ни одна конфигурация, так как к ней не применима ни одна команда. Конфигурацию МП-автомата, не являющуюся заключительной и к которой не применима ни одна команда, называют тупиковой. Определение 8.9. Выводом на множестве конфигураций МП-автомата $M$ называют последовательность $C_0,C_1,\ldots,C_n,\ldots$ (конечную или бесконечную) таких его конфигураций, что для любого $i\geqslant0$ имеет место $C_i\vdash C_{i+1}$ , если $C_{i+1}$ существует. Если вывод конечен и $C_n$ — его последняя конфигурация, то число $n$ называют длиной вывода. В этом случае будем говорить, что вывод $C_0,C_1,\ldots,C_n$ связывает конфигурацию $C_0$ с конфигурацией $C_n$ . Конфигурацию $C'$ называют выводимой из конфигурации $C$ , обозначая это как $C\vdash^{\ast}C'$ , если существует вывод, связывающий $C$ с $C'$ , т.е. вывод $C_0,C_1,\ldots,C_n$ такой, что $C_0=C$ , а $C_n=C'$ . В частности, при $n=0$ получаем, что любая конфигурация выводится сама из себя; при $n=1$ получаем непосредственную выводимость $C'$ из $C$ . В общем случае говорят, что конфигурация $C'$ выводится из конфигурации $C$ за $n$ шагов, записывая при этом $C\vdash^nC'$ . Желая подчеркнуть, что существует вывод ненулевой длины конфигурации $C'$ из конфигурации $C$ , то есть $C\vdash^nC$ и $n>0$ , записывают $C\vdash^{+}C'$ . Таким образом, понятие выводимости для конфигураций МП-автомата вводится аналогично таковому для грамматики. И к тому же сохраняется полная аналогия с понятием достижимости в ориентированных графах. Строгое определение языка МП-автомата В терминах конфигураций может быть дано и строгое определение языка МП-автомата. Определение 8.10. Входную цепочку $x$ называют допустимой цепочкой МП-автомата $M$ (см. определение 8.7), если на множестве конфигураций $M$ существует вывод, связывающий начальную конфигурацию $(q_0,x,Z_0)$ с заключительной конфигурацией $(q_f,\lambda,\lambda)$ , где $q_f\in F$ , то есть $(q_0,x,Z_0)\vdash_{M}^{\ast}(q_f,\lambda,\lambda).$ Язык, допускаемый МП-автоматом $M$ (или просто язык МП-автомата $M$ ), — это множество всех его допустимых цепочек. МП-автоматы $M_1$ и $M_2$ называют эквивалентными, если их языки совпадают, т.е. $L(M_1)=L(M_2)$ . Любой вывод на множестве конфигураций МП-автомата, связывающий начальную конфигурацию С $C_0^x=(q_0,x,Z_0)$ с одной из заключительных, называют допускающей последовательностью конфигураций для цепочки $x$ . Цепочка $x$ принадлежит языку $L(M)$ тогда и только тогда, когда для нее существует допускающая последовательность конфигураций. Тем не менее может оказаться так, что даже в том случае, когда $x\in L(M)$ , из начальной конфигурации $C_0^x$ можно вывести отнюдь не только заключительную конфигурацию. Пример 8.15. Пусть МП-автомат $M=(\{q_0,q_1,q_2\},\{a,b\},\{Z,a,b\}, q_0,\{q_0\}, Z,\delta_2)$ определен множеством команд $\delta_2\colon$ $\begin{array}{lrlrlr}q_0aZ\to q_0aZ,&\quad (1)&\qquad q_0ab\to q_0ab,&\quad (5)&\qquad q_1aa\to q_1\lambda,&\quad (9)\\q_0bZ\to q_0bZ,&\quad (2)&\qquad q_0ba\to q_0ba,&\quad (6)&\qquad q_1bb\to q_1\lambda,&\quad (10)\\ q_0aa\to q_0aa,&\quad (3)&\qquad q_0bb\to q_0bb,&\quad (7)&\qquad q_1\lambda Z\to q_2\lambda.\\ q_0aa\to q_0\lambda,&\quad (4)&\qquad q_0bb\to q_1\lambda,&\quad (8)&\qquad &\quad (11){}&{} \end{array}$ Можно доказать, что этот МП-автомат допускает зеркальный язык $\{xx^R\in \{a,b\}^{\ast}\}$ , где $x^R$ обозначает инверсию цепочки $x$ . Приведем допускающую последовательность конфигураций для цепочки $abba:$ $\begin{aligned}(q_0,abba,Z)&\vdash_{(1)} (q_0,bba,aZ)\vdash_{(6)} (q_0,ba,baZ)\vdash_{(8)}\\ &\vdash_{(8)} (q_1,a,aZ)\vdash_{(9)} (q_1,\lambda,Z)\vdash_{(11)} (q_2,\lambda,\lambda)\end{aligned}$ (справа внизу под значками непосредственной выводимости подписаны номера применяемых команд). К начальной конфигурации $(q_0,abba,Z)$ применима только команда (1). После выполнения этой команды первый символ входной цепочки будет прочитан, а в магазине вместо одного символа $Z$ окажется цепочка $aZ$ , т.е. символ а станет верхним символом магазина. К полученной конфигурации $(q_0,bba,aZ)$ применима только команда (6), в результате выполнения которой будет прочитан еще один символ входной цепочки, т.е. ее второй символ $b$ , ив магазине окажется цепочка $baZ$ . К третьей конфигурации записанного выше вывода применимы две команды: (7) и (8). Выбирая команду (8), мы тем самым читаем третий символ входной цепочки, а верхний символ магазина, совпавший с указанным символом входной цепочки, "выталкиваем" из магазина, после чего верхним символом магазина окажется уже символ а, т.е. возникнет конфигурация $(q_1,a,aZ)$ . Заметим также, что после выполнения команды (8) МП-автомат $M_2$ окажется в новом состоянии $q_1$ . Применив к конфигурации $(q_1,a,aZ)$ единственную применимую к ней команду (9), получим конфигурацию $(q_1,\lambda,Z)$ , т.е. входная цепочка прочитана полностью, а в магазине остался символ $Z$ . Применяя опять-таки единственно возможную для такой конфигурацию команду (11), мы убираем символ $Z$ из магазина, тем самым опустошая его, и переходим в заключительное состояние $q_2$ . В то же время, если бы после третьей конфигурации было выбрано "неудачное продолжение", т.е. была бы применена команда (7), и автомат продолжал бы записывать в магазин вместо того, чтобы сравнивать магазин с лентой, то получился бы вывод $(q_0,ba,baZ)\vdash_{(7)} (q_0,a,bbaZ)\vdash_{(5)} (q_0,\lambda,abbaZ).$ Последняя конфигурация в этом выводе характеризуется тем, что входная цепочка прочитана, магазин не пуст, состояние не является заключительным и не применима ни одна команда, т.е. полученная конфигурация $(q_0,\lambda,abbaZ)$ МП-автомата $M_2$ является тупиковой. Рассмотренный пример показывает, что МП-автомат может попасть в тупиковую конфигурацию, читая даже "правильную" цепочку, т.е. цепочку, принадлежащую его языку. Это связано с недетерминированностью МП-автомата, т.е. с тем, что из данной конфигурации можно непосредственно вывести, вообще говоря, более чем одну конфигурацию. Тот факт, что входная цепочка принадлежит языку МП-автомата, означает лишь, что существует допускающая последовательность конфигураций для этой цепочки, но не всякая последовательность конфигураций, которая возникает при чтении этой цепочки, будет допускающей. Задача эффективного поиска допускающей последовательности конфигураций — одна из основных задач разработки алгоритмов синтаксического анализа на базе МП-автоматов. МП-автомат называют детерминированным, если из каждой его конфигурации непосредственно выводится не более чем одна конфигурация. Можно доказать, что, в отличие от конечного автомата, для МП-автомата невозможна процедура детерминизации и класс языков, допускаемых детерминированными МП-автоматами, строго включается в класс языков, допускаемых произвольными МП-автоматами. Как уже отмечалось, основное свойство языков, допускаемых МП-автоматами, состоит в том, что эти языки образуют класс, совпадающий с классом КС-языков. Но перед тем как доказывать этот основной результат теории МП-автоматов, аналогичной теореме Клини для конечных автоматов, установим одно весьма полезное свойство МП-автомата, состоящее в том, что "хвост" входной цепочки и "дно" магазина не влияют на работу МП-автомата с началом входной цепочки и верхом магазина, так как входная цепочка читается строго символ за символом без возвратов и забеганий вперед, а магазин обновляется только сверху. Приведем строгую формулировку. Теорема 8.5. Пусть в МП-автомате $M=(Q,V,\Gamma,q_0,F,Z_0,\delta)$ на множестве конфигураций для некоторых $q,r\in Q,~x,y\in V^{\ast}$ и $\alpha,\beta\in \Gamma^{\ast}$ имеет место выводимость $(q,xy,\alpha)\vdash_{M}^{\ast}(r,y,\beta).$ (8.10) Тогда для произвольных $z\in V^{\ast},~\gamma\in\Gamma^{\ast}$ имеет место выводимость $(q,xyz,\alpha\gamma)\vdash_{M}^{\ast}(r,yz,\beta\gamma).$ (8.11) Обратно, если для некоторых $q,r\in Q,~x,y,z\in V^{\ast}$ и $\alpha,\beta,\gamma\in \Gamma^{\ast}$ имеет место выводимость (8.11), то выполняется и выводимость (8.10). Индукцией по длине вывода, связывающего конфигурацию $(q,xy,\alpha)$ с конфигурацией $(r,y,\beta)$ в (8.10) докажем, что если эта выводимость имеет место, то имеет место и выводимость (8.11). Для вывода нулевой длины утверждение тривиально. Пусть доказываемое верно для любой длины вывода, связывающего конфигурации в (8.10), не превышающей $n-1$ . Предположим, что $(q,xy,\alpha)\vdash_{M}^{n} (r,y,\beta)$ . Рассмотрим первый шаг соответствующего вывода. Пусть он имеет вид $(q,ax'y,Z\alpha')\vdash_{M} (q',x'y,\sigma\alpha')$ , где $x=ax',~ \alpha= Z\alpha',~a\in V\in\{\lambda\}$ и $Z\in\Gamma$ . Это значит, что на этом шаге применена команда $qaZ\to q'\sigma.$ (8.12) Согласно предположению индукции, для произвольных $z\in V^{\ast}$ и $\gamma\in\Gamma^{\ast}$ имеет место выводимость $(q',x'yz,\sigma\alpha'\gamma)\vdash^{n-1}(r,yz,\beta\gamma).$ (8.13) Рассмотрим конфигурацию $(q,xyz,\alpha\gamma)=(q,ax'yz,Z\alpha'\gamma)$ и применим к ней команду (8.12). Получим $(q,ax'yz,Z\alpha'\gamma)\vdash_{M} (q',x'yz,\sigma\alpha'\gamma).$ Отсюда в силу (8.13), будем иметь $(q,ax'yz,Z\alpha'\gamma)\vdash (q',x'yz,\sigma\alpha'\gamma)\vdash_{M}^{n-1}(r,xy,\beta\gamma),$ т.е. при выводимости (8.10) за $n$ шагов имеет место и выводимость (8.11) также за $n$ шагов, что и требовалось доказать. Аналогично (но уже индукцией по длине вывода (8.11)) доказывается, что если имеет место выводимость (8.11), то имеет место и выводимость (8.10). Математический форум (помощь с решением задач, обсуждение вопросов по математике). Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.

Магазинные автоматы (автомат с магазинной памятью)

Онлайн-сервисы

Нахождение НОД и НОК Разложение числа на простые множители Сравнения по модулю Операции над множествами Операции над векторами Разложение вектора по базису. Доказательство, что векторы образуют базис Чертёж треугольника по координатам вершин Решение треугольника Решение Пирамиды Построение Пирамиды по координатам вершин Чертёж многоугольника по координатам вершин Решение систем методом Крамера и Матричным Онлайн построение графика кривой 2-го порядка Определение вида кривой или поверхности 2-го порядка по инвариантам МНК и регрессионный анализ Онлайн + графики Онлайн число, сумма и дата прописью

Алгоритмы JavaScript

Алгоритмы поиска Алгоритмы сортировки Уникальные элементы массива Объединение, пересечение и разность массивов НОД и НОК Операции над матрицами Дата прописью

Введение в анализ

Функции: понятие, определение, графики Непрерывность функции Исследование функции и построение графика

Теория множеств

Множества: понятие, определение, примеры Точечные множества Замкнутые и открытые множества Мера множества Группы, кольца, поля в математике Поле комплексных чисел Кольцо многочленов Основная теорема алгебры и ее следствия

Математическая логика

Алгебра высказываний

Аксиоматика и логические рассуждения Методы доказательств теорем Алгебра высказываний и операции над ними Формулы алгебры высказываний Тавтологии алгебры высказываний Логическая равносильность формул Нормальные формы для формул высказываний Логическое следование формул Приложение алгебры высказываний для теорем Дедуктивные и индуктивные умозаключения Решение логических задач Принцип полной дизъюнкции

Булевы функции

Множества, отношения и функции в логике Булевы функции от одного и двух аргументов Булевы функции от n аргументов Системы булевых функций Применение булевых функций к релейно-контактным схемам Релейно-контактные схемы в ЭВМ Практическое применение булевых функций

Теория формального

Формализованное исчисление высказываний Полнота и другие свойства формализованного исчисления высказываний Независимость системы аксиом формализованного исчисления высказываний

Логика предикатов

Логика предикатов Логические операции над предикатами Кванторные операции над предикатами Формулы логики предикатов Тавтологии логики предикатов Преобразования формул и следование их предикатов Проблемы разрешения для общезначимости и выполнимости формул Применение логики предикатов в математике Строение математических теорем Аристотелева силлогистика и методы рассуждений Принцип полной дизъюнкции в предикатной форме Метод полной математической индукции Необходимые и достаточные условия Логика предикатов и алгебра множеств Формализованное исчисление предикатов

Неформальные и формаль-
ные аксиоматические теории

Неформальные аксиоматические теории Свойства аксиоматических теорий Формальные аксиоматические теории Формализация теории аристотелевых силлогизмов Свойства формализованного исчисления предикатов Формальные теории первого порядка Формализация математической теории

Теория алгоритмов

Интуитивное представление об алгоритмах Машины Тьюринга и тезис Рекурсивные функции Нормальные алгоритмы Маркова Разрешимость и перечислимость множеств Неразрешимые алгоритмические проблемы Теорема Гёделя о неполноте формальной арифметики

Математическая логика и компьютеры

Математическая логика и языки программирования Применение компьютеров для доказательства теорем математической логики Математическая логика и логическое программирование Математическая логика и информатика Математическая логика и искусственный интеллект

Дискретная математика

Множества и отношения

Теория множеств: понятия и определения Операции над множествами Кортеж и декартово произведение множеств Соответствия и бинарные отношения на множествах Операции над соответствиями на множествах Семейства множеств Специальные свойства бинарных отношений Отношения эквивалентности на множестве Упорядоченные множества Теорема о неподвижной точке Мощность множества Парадокс Рассела Метод характеристических функций

Группы и кольца

Алгебраические структуры и операции Группоиды, полугруппы, группы Кольца, тела, поля Области целостности в теории колец Модули и линейные пространства Подгруппы и подкольца Теорема Лагранжа о порядке конечной группы Гомоморфизмы групп и нормальные делители Гомоморфизмы и изоморфизмы колец Алгебра кватернионов

Полукольца и булевы алгебры

Полукольца: определение, аксиомы, примеры Замкнутые полукольца Полукольца и системы линейных уравнений Булевы алгебры и полукольца Решетки и полурешетки

Алгебраические системы

Алгебраические системы: модели и алгебры Подсистемы алгебраических систем Конгруэнции и фактор-системы Гомоморфизмы алгебраических систем Прямые произведения алгебраических систем Конечные булевы алгебры Многосортные алгебры

Теория графов

Теория графов: основные понятия и определения Способы представления графов Неориентированные и ориентированные деревья Остовное дерево и алгоритм Краскала Методы систематического обхода вершин графа Алгоритмы поиска в глубину и ширину в графах Задача о путях во взвешенных ориентированных графах Изоморфизм, гомоморфизм и автоморфизм графов Топологическая сортировка вершин графа Элементы цикломатики в теории графов

Булева алгебра и функции

Булевы функции и булев куб Таблицы булевых функций и булев оператор Равенство булевых функций. Фиктивные переменные Формулы и суперпозиции булевых функций Дизъюнктивные и конъюнктивные нормальные формы Построение минимальных ДНФ Теорема Поста и классы Критерий Поста Схемы из функциональных элементов

Конечные автоматы и регулярные языки

Конечные автоматы и регулярные языки Алфавит, слово, язык в программировании Порождающие грамматики (грамматики Хомского) Классификация грамматик и языков Регулярные языки и регулярные выражения Конечные автоматы Допустимость языка конечным автоматом Теорема Клини Детерминизация конечных автоматов Минимизация конечных автоматов Лемма о разрастании для регулярных языков Обоснование алгоритма детерминизации автоматов Конечные автоматы с выходом Морфизмы и конечные подстановки Машины Тьюринга

Контекстно-свободные языки

Контекстно-свободные языки и грамматики Приведенная форма КС-грамматики Лемма о разрастании для КС-языков Магазинные автоматы (автомат с магазинной памятью) Алгоритм построения МП-автомата по КС-грамматике Алгоритм построения КС-грамматики по МП-автомату Алгебраические свойства КС-языков Основное свойство суперпозиции КС-языков Пересечение контекстно-свободных языков Методы синтаксического анализа КС-языков Восходящий синтаксический анализ и LR(k)-грамматики Семантика формальных языков Принцип индукции по неподвижной точке Графовое представление МП-автоматов

Интегральное исчисление

Неопределённый и определённый

Неопределенный и определенный интегралы Свойства интегралов Интегрирование по частям Интегрирование методом замены переменной Интегрирование различных рациональных функций Интегрирование различных иррациональных функций Интегрирование различных тригонометрических функций Определенный интеграл и его основные свойства Необходимое и достаточное условие интегрируемости Теоремы существования первообразной Свойства определенных интегралов Несобственные интегралы Интегральное определение логарифмической функции

Приложения интегралов

Вычисление площадей плоских фигур Площади фигур в различных координатах Вычисление объемов тел с помощью интегралов Объём тела вращения Вычисление длин дуг кривых Формулы длины дуги регулярной кривой Кривизна плоской кривой Площадь поверхности вращения тела

Интегралы в физике

Статические моменты и координаты центра тяжести Теоремы Гульдина–Паппа Вычисление моментов инерции Другие приложения интегралов в физике

Основные интегралы

Интеграл Ньютона-Лейбница Интеграл Римана Интеграл Лебега

Вариационное исчисление

Примеры вариационных задач Дифференциальное уравнение Эйлера Функционалы, зависящие от нескольких функций Задача о минимуме кратного интеграла

Финансовый анализ

Анализ эффективности

Критерии и показатели эффективности предприятия Методы анализа эффективности деятельности Факторный анализ прибыли от операционной деятельности Анализ безубыточности предприятия Операционный рычаг и эффект финансового рычага Анализ и оценка состава, структуры и динамики доходов и расходов Анализ рентабельности и резервов устойчивого роста капитала Анализ распределения прибыли предприятия Анализ и оценка чувствительности показателей эффективности

Анализ устойчивости

Финансовая устойчивость и долгосрочная платежеспособность Характеристика типов финансовой устойчивости

Рыночная активность

Финансовый анализ рыночной активности Методика анализа рыночной активности Анализ и оценка дивидендного дохода на одну акцию

Инвестиционная деятельность

Инвестиции: экономическая сущность и классификация Государственное регулирование инвестиционной деятельности Источники финансовых ресурсов на капитальные вложения Инвестиции в основные фонды Оценка состояния основных фондов Амортизация основных фондов Капитальное строительство в инвестиционном процессе Планирование инвестиций в форме капитальных вложений Экономическая эффективность инвестиций Финансирование капитальных вложений Кредитование капитальных вложений Кредитоспособность Финансирование и кредитование затрат Финансирование и кредитование инвестиционной деятельности потребительской кооперации Финансирование и кредитование капитальных вложений потребительской кооперации Инвестиционное строительное проектирование

Анализ инвестиций

Инвестиции и инвестиционная деятельность предприятия Задачи финансового анализа инвестиций предприятия Учет фактора времени в инвестиционной деятельности Аннуитет и финансовая рента в инвестициях Учет фактора инфляции при инвестировании Оценка фактора риска инвестиционного проекта Методы оценки эффективности инвестиций Показатели эффективности инвестиционного проекта

Стоимость компании

Концепция построения международных стандартов финансовой отчетности (МСФО) Экономическое содержание международных стандартов финансовой отчётности Цели и принципы оценки стоимости акций и активов компании Оценка акций и активов предприятия по справедливой стоимости Методы оценки справедливой стоимости акций предприятия Затратный подход к оценки стоимости компаний и акций Сравнительный подход к оценки стоимости предприятий и акций Доходный подход к оценке стоимости компании и акций Выбор ставки дисконтирования при инвестировании в акции Метод капитализации прибыли Сравнение подходов к оценке стоимости компаний и пакетов акций

Форвардные контракты

Форвардный контракт и цена Форвардная цена акции на бирже Цена форвардного контракта инвестора Форвардная цена акции с учетом величины дивиденда Форвардная цена акции с учетом ставки дивиденда Форвардная цена валюты на рынке форекс Форвардный валютный курс и инфляция на рынке Форвардная цена товара и спотовый рынок Форвардная цена при различии ставок по кредитам и депозитам Синтетический форвардный контракт на акции и валюту

Теория вероятностей

Основные понятия теории вероятностей Зависимые и независимые случайные события Повторные независимые испытания Формула Бернулли Одномерные случайные величины Многомерные случайные величины Функции случайных величин Законы распределения целочисленных случайных величин Законы распределения непрерывных случайных величин Предельные теоремы теории вероятностей Закон больших чисел и предельные теоремы Вероятностные закономерности

Математическая статистика

Элементы математической статистики Выборочный метод Оценки параметров генеральной совокупности Статистические гипотезы Критерии согласия Теоретические и эмпирические частоты

Теория очередей (СМО)

Определение системы массового обслуживания Уравнения Колмогорова Предельные вероятности состояний Определение СМО с отказами Определение СМО с ожиданием (очередью)

Аналитическая геометрия

Векторная алгебра

Метрические понятия и аксиомы геометрии Равенство и подобие геометрических фигур Бинарные отношения Вектор, его направление и длина Линейные операции над векторами Линейная зависимость и независимость векторов Отношение коллинеарных векторов Проекции векторов на прямую и на плоскость Угол между векторами Ортогональные проекции векторов Координата вектора на прямой и базис Координаты вектора на плоскости и базис Координаты вектора в пространстве и базис Операции над векторами в координатной форме Ортогональный и ортонормированный базисы Cкалярное произведение векторов и его свойства Выражение скалярного произведения через координаты векторов Векторное произведение векторов и его свойства Смешанное произведение векторов и его свойства Ориентированные площади и объемы Двойное векторное произведение и его свойства Применение векторов в задачах на аффинные свойства фигур Применение произведений векторов при решении геометрических задач Применение векторной алгебры в механике

Системы координат

Прямоугольные координаты Преобразования прямоугольных координат Полярная система координат Цилиндрическая система координат Сферические координаты Аффинные координаты Аффинные преобразования координат Аффинные преобразования плоскости Примеры аффинных преобразований плоскости Аффинные преобразования пространства Многомерное координатное пространство Линейные и аффинные подпространства Скалярное произведение n-мерных векторов Преобразования систем координат

Геометрия на плоскости

Алгебраические линии на плоскости Общие уравнения геометрических мест точек Алгебраические уравнения линий на плоскости Уравнения прямой, проходящей через точку перпендикулярно вектору Уравнения прямой, проходящей через точку коллинеарно вектору Уравнения прямой, проходящей через две точки Уравнения прямой с угловым коэффициентом Взаимное расположение прямых Примеры задач с прямыми на плоскости Системы неравенств с двумя неизвестными Системы линейных уравнений с двумя неизвестными

Линии 2-го порядка

Канонические уравнения линий второго порядка Порядок приведения уравнения линии к каноническому виду Эллипс Гипербола Парабола Квадратичные неравенства с двумя неизвестными Применение линий 1-го и 2-го порядков в задачах на экстремум функций

Инварианты линий

Классификация линий 2-го порядка по инвариантам Приведение уравнения линии к каноническому виду по инвариантам

Геометрия в пространстве

Способы задания ГМТ в пространстве Алгебраические уравнения поверхностей Уравнения плоскости, проходящей через точку перпендикулярно вектору Уравнения плоскости, компланарной двум неколлинеарным векторам Уравнения плоскости, проходящей через три точки Взаимное расположение плоскостей Типовые задачи с плоскостями Уравнения прямых в пространстве Взаимное расположение прямых в пространстве Типовые задачи с прямыми в пространстве

Поверхности 2-го порядка

Канонические уравнения поверхностей Порядок приведения уравнения поверхности к каноническому виду Поверхности второго порядка Эллипсоиды Гиперболоиды Конусы Параболоиды Применение поверхностей 1-го и 2-го порядков в задачах на экстремум функций

Инварианты поверхностей

Классификация поверхностей 2-го порядка по инвариантам Квадратичные неравенства с тремя неизвестными Приведение уравнения поверхности к канониче-скому виду по инвариантам

Линейная алгебра

Матрицы и операции

Линейные операции над матрицами Умножение матриц Возведение матриц в степень Многочлены от матриц Транспонирование и сопряжение матриц Блочные матрицы Произведение и сумма матриц Кронекера Метод Гаусса приведения матрицы к ступенчатому виду Элементарные преобразования матриц

Определители

Определители матриц и их основные свойства Формула полного разложения определителя Формула Лапласа полного разложения определителя Определитель произведения матриц Методы вычисления определителей

Ранг матрицы

Линейная зависимость и линейная независимость строк (столбцов) матрицы Ранг матрицы и базисный минор матрицы Методы вычисления ранга матрицы Ранг системы столбцов (строк)

Обратная матрица

Обратные матрицы и их свойства Ортогональные и унитарные матрицы Способы нахождения обратной матрицы Матричные уравнения Односторонние обратные матрицы Скелетное разложение матрицы Полуобратная матрица Псевдообратная матрица

Системы уравнений

Системы линейных алгебраических уравнений Метод Гаусса решения систем линейных уравнений Структура общего решения системы уравнений Решение систем с помощью полуобратных матриц Псевдорешения системы линейных уравнений

Функциональные матрицы

Функциональные матрицы скалярного аргумента Производные матриц по векторному аргументу Линейные и квадратичные формы и их преобразования Приведение форм к каноническому виду Закон инерции вещественных квадратичных форм Знакоопределенность форм вещественных квадратичных Формы и исследование функций на экстремум

Многочленные матрицы

Многочленные матрицы (лямбда-матрицы) Операции над лямбда-матрицами Простые преобразования многочленных матриц Инвариантные множители многочленной матрицы

Функции от матриц

Собственные векторы и значения матрицы Подобие числовых матриц Характеристический многочлен матрицы Минимальный многочлен матрицы Теорема Гамильтона-Кэли Жорданова форма матрицы Приведение матрицы к жордановой форме Многочлены от матриц Применение многочленов от матриц Функции от матриц

Линейные пространства

Линейные пространства: определение и примеры Линейная зависимость и независимость n-мерных векторов Размерность и базис линейного пространства Преобразования координат в линейном пространстве Изоморфизм линейных пространств

Подпространства

Подпространства линейного пространства Пересечение и сумма подпространств Способы описания подпространств Нахождение дополнения и суммы подпространств Нахождение пересечения подпространств

Линейные отображения

Линейные многообразия Линейные отображения Матрица линейного отображения Ядро и образ линейного отображения

Линейные операторы

Линейные операторы (преобразования) Инвариантные подпространства Собственные векторы и значения оператора Свойства собственных векторов операторов Канонический вид линейного оператора Методика приведения линейного преобразования к каноническому виду

Евклидовы пространства

Комплексный анализ

Комплексные числа

Комплексные числа в алгебраической форме Комплексные числа в тригонометрической и показательной формах Множества на комплексной плоскости Последовательности и ряды комплексных чисел

Комплексные функции

Функции комплексного переменного. Предел, непрерывность и производная Элементарные функции комплексного переменного Дифференцирование функций комплексного переменного Аналитические функции и их свойства Конформные отображения
и их свойства Интегрирование функций комплексного переменного

Функциональные ряды в комплексной области

Функциональные ряды и последовательности Степенные ряды и их свойства Разложение функций в степенные ряды Нули аналитических функций Ряд Лорана и разложение функций по целым степеням

Особые точки, Вычеты

Изолированные особые точки функций и полюсы Вычеты и их применение Вычисление интегралов с помощью вычетов Вычеты и расположение нулей многочлена

Операционное исчисление

Преобразование Лапласа и его свойства Решение ДУ операционным методом Анализ выходных процессов линейных стационарных систем Z-преобразование и его свойства

Дифференциальные уравнения

ДУ первого порядка

Основные понятия и определения ДУ Метод изоклин для ДУ 1-го порядка Метод последовательных приближений ДУ с разделяющимися переменными Однородные ДУ Линейные ДУ 1-го порядка Дифференциальное уравнение Бернулли ДУ в полных дифференциалах Интегрирующий множитель ДУ, не разрешенные относительно производной Дифференциальное уравнение Риккати Составление ДУ семейств линий Задачи на траектории Особые решения ДУ

ДУ высших порядков

Понятия и определения ДУ высших порядков ДУ, допускающие понижение порядка Линейная независимость функций Определители Вронского и Грама Однородные и неоднородные дифференциальные уравнения Задача Коши и Уравнение Эйлера Линейные ДУ с переменными коэффициентами Метод Лагранжа решения ДУ Краевые задачи для ДУ высших порядков Разложение решения ДУ в степенной ряд Разложение решения ДУ в обобщенный степенной ряд Нахождение периодических решений ДУ Асимптотическое интегрирование ДУ

Системы ДУ

Системы ДУ: понятия и определения Сведение системы ДУ к одному уравнению Нахождение интегрируемых комбинаций Интегрирование однородных линейных систем ДУ Методы интегрирования неоднородных систем ДУ Преобразование Лапласа и решение ДУ и систем

Теория устойчивости

Устойчивость решений ДУ по Ляпунову Простейшие типы точек покоя Метод функций Ляпунова Устойчивость решений ДУ по первому приближению Критерии устойчивости Рауса–Гурвица и Михайлова ДУ с малым параметром при производной

Численные методы

Методы алгебры

Численные методы линейной алгебры Численные методы решения СЛАУ Итерационный метод Шульца обратной матрицы Методы решения задач о собственных значениях и векторах матрицы Методы решения нелинейных уравнений Методы решения систем нелинейных уравнений

Методы теории приближений

Методы приближения сеточных функций Методы функциональной интерполяции Методы интегрально-дифференциальной интерполяции Методы интегрального сглаживания Методы интерполяции и сглаживания сплайнами Методы численного дифференцирования и интегрирования Методы численного дифференцирования Методы численного интегрирования

Методы решения обыкновенных ДУ

Численные методы решения задачи Коши Разностные схемы для решения задачи Коши Составные схемы для решения задачи Коши Экстраполяционные методы решения задачи Коши Непрерывно-дискретные методы решения задачи Коши Численные методы решения краевых задач

Методы решения ДУ в частных производных

Численные методы решения уравнений математической физики с двумя переменными Принципы построения разностных схем для уравнений в частных производных Разностные схемы решения уравнений в частных производных 1-го порядка Разностные схемы решения уравнений в частных производных 2-го порядка Численные методы решения уравнений в частных производных Численные методы решения уравнений математической физики с тремя переменными

Магазинные автоматы (автомат с магазинной памятью)

Автоматы с магазинной памятью, или магазинные автоматы (сокращенно — МП-автоматы), образуют класс распознающих моделей для КС-языков точно так же, как конечные автоматы являются распознающими моделями в классе регулярных языков.

Понятие МП-автомата является частным случаем общего интуитивного понятия автомата, которое мы ввели ранее. Как и всякий автомат, МП-автомат — это устройство, имеющее блок управления, входную ленту, головку и блок внутренней памяти в виде магазина МП-автомата (или стека).

Блок управления в каждый момент времени находится в одном из конечного множества $Q$ состояний.

Входная лента предполагается "полубесконечной", т.е. она имеет начало ("левый край"), но не имеет конца. Лента разделена на ячейки, пронумерованные от крайней левой ячейки натуральными числами, начиная с единицы; в каждой ячейке может быть записан символ алфавита $V$ , называемого входным алфавитом МП-автомата. В каждый момент времени читающая головка обозревает (или читает) некоторую ячейку входной ленты.

Если в этой ячейке записан некоторый входной символ, т.е. символ входного алфавита, то его называют обозреваемым (в данный момент) входным символом (рис. 8.28).

Предполагается, что если на ленте записана некоторая непустая цепочка $x=x(1)x(2)\ldots x(k)$ во входном алфавите, то ее символы последовательно записаны в ячейках от первой до k-й, без пропусков, так, что символ $x(i)$ записан в i-й ячейке (рис. 8.29).

МП-автомат может читать цепочку $x$ , продвигая головку только в одном направлении, слева направо, по шагам, причем за каждый шаг головка переходит от обозреваемой ячейки к следующей. Если в какой-то момент времени обозревается символ $x(i),~1\leqslant i\leqslant k$ , записанной на ленте цепочки $x$ , то непрочитанной частью входной цепочки $x$ будет подцепочка $x(i+1)\ldots x(k)$ . В частности, при $i=k$ непрочитанная часть совпадает с пустой цепочкой, и тогда говорят, что цепочка $x$ полностью прочитана МП-автоматом (рис. 8.30).

Устройство и работа магазина МП-автомата

Магазин МП-автомата устроен и работает следующим образом. Как и входная лента, магазин является полубесконечным и разделенным на пронумерованные ячейки, в каждой из которых может быть записан символ алфавита $\Gamma$ , называемого магазинным алфавитом МП-автомата. Входной и магазинный алфавиты МП-автомата могут пересекаться и даже совпадать друг с другом. Символы алфавита $\Gamma$ называют магазинными символами. Первую ячейку магазина называют его верхней ячейкой (иногда просто верхом магазина*). Символ, в данный момент записанный в верхней ячейке магазина, называют верхним символом магазина.

*Таким образом, в неформальном описании МП-автомата лента читается "слева направо", а магазин — "сверху вниз".

Единственная операция, которую МП-автомат может реализовать с магазином, состоит в следующем: верхний символ $Z$ магазина заменяется некоторой цепочкой $\gamma$ магазинных символов. При этом если цепочка $\gamma$ непустая, то она записывается в первых $m$ ячейках, где $m=|\gamma|$ (длине цепочки $\gamma$ ), так, что ее первый символ становится верхним символом магазина.

Если до замены $Z$ цепочкой $\gamma$ под верхней ячейкой** (т.е. в ячейках, начиная со второй) была записана какая-то цепочка а, то после замены она сдвигается "в глубь" магазина и оказывается записанной уже в ячейках, начиная с (m+1)-й (рис. 8.31).

**Полагают, что, как и символы цепочек на входной ленте, символы цепочек, записанных в магазин, располагаются в последовательных ячейках "сверху вниз" без пропусков ячеек.

Если же верхний символ $Z$ заменяется пустой цепочкой $\lambda$ , то после такой замены верхним символом магазина становится первый символ цепочки $\alpha$ (записанной под верхней ячейкой магазина), т.е. цепочка $\alpha$ "поднимается" на одну ячейку.

В случае, когда $\alpha$ — пустая цепочка, замена верхнего символа магазина пустой цепочкой $\gamma$ приводит к опустошению магазина (ни в одной из ячеек магазина не записан магазинный символ). Заметим, что, по определению, с пустым магазином МП-автомат не может производить никаких операций.

Описанная выше операция с магазином составляет основу поведения МП-автомата, его, образно говоря, "динамику". Эта "динамика" определяется системой команд МП-автомата, которая, аналогично системе команд конечного автомата, определяется как конечное множество $\delta$ команд, каждая из которых записывается в виде

$qaZ\to r\gamma,$

(8.8)

где $q$ и $r$ — состояния из множества $Q$ ; $a$ — входной символ или пустая цепочка; $Z$ — магазинный символ; $\gamma$ — цепочка магазинных символов (может быть и пустая).

Если в системе команд $\delta$ МП-автомата $M$ есть команда (8.8), то $M$ может в данный момент времени выполнить эту команду, если и только если в данный момент времени его блок управления находится в состоянии $q$ , головка обозревает входной символ $a$ (при условии, что $a\ne\lambda$ ), а верхним символом магазина является символ $Z$ . Выполнение команды (8.8) состоит в замене верхнего символа магазина цепочкой $\gamma$ (как это описано выше), переходе блока управления в состояние $r$ (которое может и совпадать с состоянием $q$ ) и в продвижении головки на одну ячейку вправо (если а в команде (8.8) не есть пустая цепочка $\lambda$ ) (рис. 8.32).

Если же в команде (8.8) $a=\lambda$ , то такую команду МП-автомат может выполнить всякий раз, когда его блок управления окажется в состоянии $q$ , а верхним символом магазина будет символ $Z$ . В этом случае выполнение команды никак не зависит от содержимого входной ленты, а после ее выполнения головка остается на прежнем месте.

Рассмотренную выше процедуру выполнения команды вида (8.8) называют шагом (или тактом) работы МП-автомата (при $a=\lambda$ такт работы называют λ-тактом).

Предположим теперь, что в множестве состояний $Q$ блока управления МП-автомата $M$ с системой команд $\delta$ фиксировано некоторое начальное состояние $q_0$ и подмножество заключительных состояний $F$ .

Пусть в какой-то начальный момент времени блок управления МП-автомата $M$ находится в начальном состоянии $q_0$ , налейте записана непустая цепочка $x$ , головка обозревает первую ячейку ленты и, следовательно, первый символ цепочки $x$ является обозреваемым, а в магазине записан только один специальный символ $Z_0$ , называемый начальным символом магазина.

Тогда, если МП-автомат $M$ , выполняя некоторую последовательность команд из $\delta$ , прочитывает полностью цепочку $x$ , в результате чего блок управления переходит в некоторое заключительное состояние $q_f\in F$ , говорят, что МП-автомат $M$ допускает (распознает, воспринимает) цепочку $x$ , которую называют допустимой цепочкой МП-автомата. Множество всех допустимых цепочек МП-автомата $M$ образует язык, допускаемый этим МП-автоматом.

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

Определение 8.7. МП-автомат задается упорядоченной семеркой

$M=(Q,V,\Gamma,q_0,F,Z_0,\delta),$

где $Q$ — конечное множество состояний; $V$ — алфавит, называемый входным алфавитом; $\Gamma$ — алфавит, называемый магазинным алфавитом; $q_0\in Q$ — начальное состояние; $F\subseteq Q$ — подмножество заключительных состояний; $Z_0\in\Gamma$ — начальный магазинный символ; $\delta$ — система команд, определенная как конечное множество команд, каждая из которых записывается в виде (8.8): $qaZ\to r\gamma$ , где знак " $\to$ " (стрелка) — внешний символ (не принадлежащий ни одному из указанных алфавитов);

$q,r\in Q;\qquad a\in V\cup\{\lambda\};\qquad Z\in\Gamma;\qquad \gamma\in \Gamma^{\ast}.$

Замечание 8.8. Нелишне обратить внимание на то, что упоминание о ленте и магазине в приведенном выше формальном определении совершенно необязательно. Формально для определения МП-автомата достаточно задать два алфавита, конечное множество состояний, выделив в нем начальное состояние и подмножество заключительных состояний, а также систему команд. Образы ленты, магазина, да и сам термин "состояние", являются метафорами, которые позволяют связать формальное определение с его содержательной интерпретацией, идеей некоего "устройства" для чтения слов, с описания которого мы начали этот параграф.

Любую цепочку в алфавите $V$ будем называть входной цепочкой, а сами элементы входного алфавита — входными символами; точно так же любую цепочку в алфавите $\Gamma$ будем называть магазинной цепочкой, а символы этого алфавита — магазинными символами. Упорядоченную тройку до знака " $\to$ " (стрелки) в записи команды называют левой частью команды, а упорядоченную пару после знака " $\to$ " — правой частью команды.

Пример 8.14. Рассмотрим МП-автомат $M_1=(\{q_0,q_1,q_2\}, \{0;1\}, \{Z,0\}, q_0, \{q_0\},Z,\delta_1)$ с таким множеством команд $\delta_1\colon$

$q_00Z\to q_1\,0Z,\quad q_000\to q_1\,00,\quad q_110\to q_2\lambda,\quad q_210\to q_2\lambda,\quad q_2\lambda Z\to q_0\lambda.$

На рис. 8.33 проиллюстрировано выполнение первых двух команд. При записи системы команд этого конкретного МП-автомата мы в правых частях первых двух команд отделили магазинную цепочку от состояния пробелом для того, чтобы не возник соблазн прочитать левую и правую части этих команд одинаково. Таким приемом записи мы хотим подчеркнуть, что левая часть команды МП-автомата — упорядоченная! тройка, а правая — упорядоченная пара.

Замечание 8.9. Систему команд МП-автомата можно понимать как способ определения некоторой конечной функции, которую называют функцией переходов МП-автомата (по аналогии с функцией переходов конечного автомата). Эта функция может быть определена как отображение вида

$\delta\colon Q\times(V\cup\{\lambda\})\times\Gamma\to \mathbf{Fin}(Q\times \Gamma^{\ast}),$

где использовано обозначение $\mathbf{Fin}(A)$ для множества всех конечных подмножеств множества $A$ .

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

Определение 8.8. Конфигурацией МП-автомата $M$ называют упорядоченную тройку вида $(q,x,\beta)$ , где $q\in Q$ — состояние, $x\in V^{\ast}$ — входная цепочка, $\beta$ — магазинная цепочка.

Конфигурацию $C'=(r,w,\gamma\alpha)$ называют непосредственно выводимой из конфигурации $C=(q,aw,Z\alpha)$ , если в множестве команд МП-автомата есть команда (8.8). Отношение непосредственной выводимости на множестве конфигураций МП-автомата $M$ обозначаем $\vdash_M$ , используя запись $C\vdash_{M}C'$ (и опуская, если это не вредит пониманию, обозначение самого МП-автомата).

Итак, непосредственная выводимость

$(q,aw,Z\alpha)\vdash_{M}(r,w,\gamma\alpha)$

(8.9)

имеет место тогда и только тогда, когда в системе $\delta$ команд МП-автомата $M$ есть команда (8.8), которую в этом случае называют применимой к конфигурации $(q,aw,Z\alpha)$ .

Таким образом, неформально конфигурация показывает состояние блока управления, непрочитанную часть входной цепочки (первый символ этой цепочки, если она не пуста, является обозреваемым) и содержимое магазина (первый символ магазинной цепочки $\beta$ , если она не пуста, есть верхний символ магазина). Если вторая компонента конфигурации — пустая цепочка, то это означает, что входная цепочка прочитана полностью. Если же пуста третья компонента, то это означает, что пуст магазин.

На рис. 8.33 изображены (в терминах приведенного выше содержательного описания) две конфигурации МП-автомата из примера 8.14, причем вторая конфигурация непосредственно выводится из первой. Понятие непосредственной выводимости, таким образом, формализует данное выше понятие такта '(или шага) работы МП-автомата. Заметим, что если в (8.9) и в команде (8.8) $a=\lambda$ , т.е. имеет место λ-такт, то команда (8.8) применима к любой конфигурации, у которой (говоря неформально) состояние блока управления есть $q$ , а верхний символ магазина — $Z$ , причем, подчеркнем это, независимо от содержимого входной ленты (т.е. для любой входной цепочки $w$ ). Если же $a$ есть входной символ, то применимость команды к конфигурации определяется состоянием, обозреваемым символом на ленте и верхним символом магазина.

Любую конфигурацию вида $(q_0,x,Z_0)$ называют начальной, а любую конфигурацию вида $(q_f,\lambda,\lambda)$ , где $q_f\in F$ , — заключительной. Обратим внимание на то, что заключительная конфигурация — это конфигурация с пустым магазином. Множество всех заключительных конфигураций находится, таким образом, во взаимно однозначном соответствии с множеством заключительных состояний МП-автомата. Из заключительной конфигурации не может быть выведена ни одна конфигурация, так как к ней не применима ни одна команда. Конфигурацию МП-автомата, не являющуюся заключительной и к которой не применима ни одна команда, называют тупиковой.

Определение 8.9. Выводом на множестве конфигураций МП-автомата $M$ называют последовательность $C_0,C_1,\ldots,C_n,\ldots$ (конечную или бесконечную) таких его конфигураций, что для любого $i\geqslant0$ имеет место $C_i\vdash C_{i+1}$ , если $C_{i+1}$ существует.

Если вывод конечен и $C_n$ — его последняя конфигурация, то число $n$ называют длиной вывода. В этом случае будем говорить, что вывод $C_0,C_1,\ldots,C_n$ связывает конфигурацию $C_0$ с конфигурацией $C_n$ .

Конфигурацию $C'$ называют выводимой из конфигурации $C$ , обозначая это как $C\vdash^{\ast}C'$ , если существует вывод, связывающий $C$ с $C'$ , т.е. вывод $C_0,C_1,\ldots,C_n$ такой, что $C_0=C$ , а $C_n=C'$ .

В частности, при $n=0$ получаем, что любая конфигурация выводится сама из себя; при $n=1$ получаем непосредственную выводимость $C'$ из $C$ . В общем случае говорят, что конфигурация $C'$ выводится из конфигурации $C$ за $n$ шагов, записывая при этом $C\vdash^nC'$ . Желая подчеркнуть, что существует вывод ненулевой длины конфигурации $C'$ из конфигурации $C$ , то есть $C\vdash^nC$ и $n>0$ , записывают $C\vdash^{+}C'$ .

Таким образом, понятие выводимости для конфигураций МП-автомата вводится аналогично таковому для грамматики. И к тому же сохраняется полная аналогия с понятием достижимости в ориентированных графах.

Строгое определение языка МП-автомата

В терминах конфигураций может быть дано и строгое определение языка МП-автомата.

Определение 8.10. Входную цепочку $x$ называют допустимой цепочкой МП-автомата $M$ (см. определение 8.7), если на множестве конфигураций $M$ существует вывод, связывающий начальную конфигурацию $(q_0,x,Z_0)$ с заключительной конфигурацией $(q_f,\lambda,\lambda)$ , где $q_f\in F$ , то есть

$(q_0,x,Z_0)\vdash_{M}^{\ast}(q_f,\lambda,\lambda).$

Язык, допускаемый МП-автоматом $M$ (или просто язык МП-автомата $M$ ), — это множество всех его допустимых цепочек.

МП-автоматы $M_1$ и $M_2$ называют эквивалентными, если их языки совпадают, т.е. $L(M_1)=L(M_2)$ .

Любой вывод на множестве конфигураций МП-автомата, связывающий начальную конфигурацию С $C_0^x=(q_0,x,Z_0)$ с одной из заключительных, называют допускающей последовательностью конфигураций для цепочки $x$ . Цепочка $x$ принадлежит языку $L(M)$ тогда и только тогда, когда для нее существует допускающая последовательность конфигураций. Тем не менее может оказаться так, что даже в том случае, когда $x\in L(M)$ , из начальной конфигурации $C_0^x$ можно вывести отнюдь не только заключительную конфигурацию.

Пример 8.15. Пусть МП-автомат $M=(\{q_0,q_1,q_2\},\{a,b\},\{Z,a,b\}, q_0,\{q_0\}, Z,\delta_2)$ определен множеством команд $\delta_2\colon$

$\begin{array}{lrlrlr}q_0aZ\to q_0aZ,&\quad (1)&\qquad q_0ab\to q_0ab,&\quad (5)&\qquad q_1aa\to q_1\lambda,&\quad (9)\\q_0bZ\to q_0bZ,&\quad (2)&\qquad q_0ba\to q_0ba,&\quad (6)&\qquad q_1bb\to q_1\lambda,&\quad (10)\\ q_0aa\to q_0aa,&\quad (3)&\qquad q_0bb\to q_0bb,&\quad (7)&\qquad q_1\lambda Z\to q_2\lambda.\\ q_0aa\to q_0\lambda,&\quad (4)&\qquad q_0bb\to q_1\lambda,&\quad (8)&\qquad &\quad (11){}&{} \end{array}$

Можно доказать, что этот МП-автомат допускает зеркальный язык $\{xx^R\in \{a,b\}^{\ast}\}$ , где $x^R$ обозначает инверсию цепочки $x$ .

Приведем допускающую последовательность конфигураций для цепочки $abba:$

$\begin{aligned}(q_0,abba,Z)&\vdash_{(1)} (q_0,bba,aZ)\vdash_{(6)} (q_0,ba,baZ)\vdash_{(8)}\\ &\vdash_{(8)} (q_1,a,aZ)\vdash_{(9)} (q_1,\lambda,Z)\vdash_{(11)} (q_2,\lambda,\lambda)\end{aligned}$

(справа внизу под значками непосредственной выводимости подписаны номера применяемых команд).

К начальной конфигурации $(q_0,abba,Z)$ применима только команда (1). После выполнения этой команды первый символ входной цепочки будет прочитан, а в магазине вместо одного символа $Z$ окажется цепочка $aZ$ , т.е. символ а станет верхним символом магазина.

К полученной конфигурации $(q_0,bba,aZ)$ применима только команда (6), в результате выполнения которой будет прочитан еще один символ входной цепочки, т.е. ее второй символ $b$ , ив магазине окажется цепочка $baZ$ .

К третьей конфигурации записанного выше вывода применимы две команды: (7) и (8). Выбирая команду (8), мы тем самым читаем третий символ входной цепочки, а верхний символ магазина, совпавший с указанным символом входной цепочки, "выталкиваем" из магазина, после чего верхним символом магазина окажется уже символ а, т.е. возникнет конфигурация $(q_1,a,aZ)$ . Заметим также, что после выполнения команды (8) МП-автомат $M_2$ окажется в новом состоянии $q_1$ .

Применив к конфигурации $(q_1,a,aZ)$ единственную применимую к ней команду (9), получим конфигурацию $(q_1,\lambda,Z)$ , т.е. входная цепочка прочитана полностью, а в магазине остался символ $Z$ .

Применяя опять-таки единственно возможную для такой конфигурацию команду (11), мы убираем символ $Z$ из магазина, тем самым опустошая его, и переходим в заключительное состояние $q_2$ .

В то же время, если бы после третьей конфигурации было выбрано "неудачное продолжение", т.е. была бы применена команда (7), и автомат продолжал бы записывать в магазин вместо того, чтобы сравнивать магазин с лентой, то получился бы вывод

$(q_0,ba,baZ)\vdash_{(7)} (q_0,a,bbaZ)\vdash_{(5)} (q_0,\lambda,abbaZ).$

Последняя конфигурация в этом выводе характеризуется тем, что входная цепочка прочитана, магазин не пуст, состояние не является заключительным и не применима ни одна команда, т.е. полученная конфигурация $(q_0,\lambda,abbaZ)$ МП-автомата $M_2$ является тупиковой.

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

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

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

Приведем строгую формулировку.

Теорема 8.5. Пусть в МП-автомате $M=(Q,V,\Gamma,q_0,F,Z_0,\delta)$ на множестве конфигураций для некоторых $q,r\in Q,~x,y\in V^{\ast}$ и $\alpha,\beta\in \Gamma^{\ast}$ имеет место выводимость

$(q,xy,\alpha)\vdash_{M}^{\ast}(r,y,\beta).$

(8.10)

Тогда для произвольных $z\in V^{\ast},~\gamma\in\Gamma^{\ast}$ имеет место выводимость

$(q,xyz,\alpha\gamma)\vdash_{M}^{\ast}(r,yz,\beta\gamma).$

(8.11)

Обратно, если для некоторых $q,r\in Q,~x,y,z\in V^{\ast}$ и $\alpha,\beta,\gamma\in \Gamma^{\ast}$ имеет место выводимость (8.11), то выполняется и выводимость (8.10).

Индукцией по длине вывода, связывающего конфигурацию $(q,xy,\alpha)$ с конфигурацией $(r,y,\beta)$ в (8.10) докажем, что если эта выводимость имеет место, то имеет место и выводимость (8.11). Для вывода нулевой длины утверждение тривиально.

Пусть доказываемое верно для любой длины вывода, связывающего конфигурации в (8.10), не превышающей $n-1$ . Предположим, что $(q,xy,\alpha)\vdash_{M}^{n} (r,y,\beta)$ . Рассмотрим первый шаг соответствующего вывода. Пусть он имеет вид

$(q,ax'y,Z\alpha')\vdash_{M} (q',x'y,\sigma\alpha')$ , где $x=ax',~ \alpha= Z\alpha',~a\in V\in\{\lambda\}$ и $Z\in\Gamma$ .

Это значит, что на этом шаге применена команда

$qaZ\to q'\sigma.$

(8.12)

Согласно предположению индукции, для произвольных $z\in V^{\ast}$ и $\gamma\in\Gamma^{\ast}$ имеет место выводимость

$(q',x'yz,\sigma\alpha'\gamma)\vdash^{n-1}(r,yz,\beta\gamma).$

(8.13)

Рассмотрим конфигурацию $(q,xyz,\alpha\gamma)=(q,ax'yz,Z\alpha'\gamma)$ и применим к ней команду (8.12). Получим

$(q,ax'yz,Z\alpha'\gamma)\vdash_{M} (q',x'yz,\sigma\alpha'\gamma).$

Отсюда в силу (8.13), будем иметь

$(q,ax'yz,Z\alpha'\gamma)\vdash (q',x'yz,\sigma\alpha'\gamma)\vdash_{M}^{n-1}(r,xy,\beta\gamma),$

т.е. при выводимости (8.10) за $n$ шагов имеет место и выводимость (8.11) также за $n$ шагов, что и требовалось доказать.

Аналогично (но уже индукцией по длине вывода (8.11)) доказывается, что если имеет место выводимость (8.11), то имеет место и выводимость (8.10).

Математический форум (помощь с решением задач, обсуждение вопросов по математике).

Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.

Список статей » Список форумов

Часовой пояс: UTC + 3 часа [ Летнее время ]