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

Контекстно-свободные языки и грамматики
Онлайн-сервисы Нахождение НОД и НОК Разложение числа на простые множители Сравнения по модулю Операции над множествами Операции над векторами Разложение вектора по базису. Доказательство, что векторы образуют базис Чертёж треугольника по координатам вершин Решение треугольника Решение Пирамиды Построение Пирамиды по координатам вершин Чертёж многоугольника по координатам вершин Решение систем методом Крамера и Матричным Онлайн построение графика кривой 2-го порядка Определение вида кривой или поверхности 2-го порядка по инвариантам МНК и регрессионный анализ Онлайн + графики Онлайн число, сумма и дата прописью Алгоритмы JavaScript Алгоритмы поиска Алгоритмы сортировки Уникальные элементы массива Объединение, пересечение и разность массивов НОД и НОК Операции над матрицами Дата прописью Введение в анализ Функции: понятие, определение, графики Непрерывность функции Исследование функции и построение графика Теория множеств Множества: понятие, определение, примеры Точечные множества Замкнутые и открытые множества Мера множества Группы, кольца, поля в математике Поле комплексных чисел Кольцо многочленов Основная теорема алгебры и ее следствия Математическая логика Алгебра высказываний Аксиоматика и логические рассуждения Методы доказательств теорем Алгебра высказываний и операции над ними Формулы алгебры высказываний Тавтологии алгебры высказываний Логическая равносильность формул Нормальные формы для формул высказываний Логическое следование формул Приложение алгебры высказываний для теорем Дедуктивные и индуктивные умозаключения Решение логических задач Принцип полной дизъюнкции Булевы функции Множества, отношения и функции в логике Булевы функции от одного и двух аргументов Булевы функции от n аргументов Системы булевых функций Применение булевых функций к релейно-контактным схемам Релейно-контактные схемы в ЭВМ Практическое применение булевых функций Теория формального Формализованное исчисление высказываний Полнота и другие свойства формализованного исчисления высказываний Независимость системы аксиом формализованного исчисления высказываний Логика предикатов Логика предикатов Логические операции над предикатами Кванторные операции над предикатами Формулы логики предикатов Тавтологии логики предикатов Преобразования формул и следование их предикатов Проблемы разрешения для общезначимости и выполнимости формул Применение логики предикатов в математике Строение математических теорем Аристотелева силлогистика и методы рассуждений Принцип полной дизъюнкции в предикатной форме Метод полной математической индукции Необходимые и достаточные условия Логика предикатов и алгебра множеств Формализованное исчисление предикатов Неформальные и формаль- ные аксиоматические теории Неформальные аксиоматические теории Свойства аксиоматических теорий Формальные аксиоматические теории Формализация теории аристотелевых силлогизмов Свойства формализованного исчисления предикатов Формальные теории первого порядка Формализация математической теории Теория алгоритмов Интуитивное представление об алгоритмах Машины Тьюринга и тезис Рекурсивные функции Нормальные алгоритмы Маркова Разрешимость и перечислимость множеств Неразрешимые алгоритмические проблемы Теорема Гёделя о неполноте формальной арифметики Математическая логика и компьютеры Математическая логика и языки программирования Применение компьютеров для доказательства теорем математической логики Математическая логика и логическое программирование Математическая логика и информатика Математическая логика и искусственный интеллект Дискретная математика Множества и отношения Теория множеств: понятия и определения Операции над множествами Кортеж и декартово произведение множеств Соответствия и бинарные отношения на множествах Операции над соответствиями на множествах Семейства множеств Специальные свойства бинарных отношений Отношения эквивалентности на множестве Упорядоченные множества Теорема о неподвижной точке Мощность множества Парадокс Рассела Метод характеристических функций Группы и кольца Алгебраические структуры и операции Группоиды, полугруппы, группы Кольца, тела, поля Области целостности в теории колец Модули и линейные пространства Подгруппы и подкольца Теорема Лагранжа о порядке конечной группы Гомоморфизмы групп и нормальные делители Гомоморфизмы и изоморфизмы колец Алгебра кватернионов Полукольца и булевы алгебры Полукольца: определение, аксиомы, примеры Замкнутые полукольца Полукольца и системы линейных уравнений Булевы алгебры и полукольца Решетки и полурешетки Алгебраические системы Алгебраические системы: модели и алгебры Подсистемы алгебраических систем Конгруэнции и фактор-системы Гомоморфизмы алгебраических систем Прямые произведения алгебраических систем Конечные булевы алгебры Многосортные алгебры Теория графов Теория графов: основные понятия и определения Способы представления графов Неориентированные и ориентированные деревья Остовное дерево и алгоритм Краскала Методы систематического обхода вершин графа Алгоритмы поиска в глубину и ширину в графах Задача о путях во взвешенных ориентированных графах Изоморфизм, гомоморфизм и автоморфизм графов Топологическая сортировка вершин графа Элементы цикломатики в теории графов Булева алгебра и функции Булевы функции и булев куб Таблицы булевых функций и булев оператор Равенство булевых функций. Фиктивные переменные Формулы и суперпозиции булевых функций Дизъюнктивные и конъюнктивные нормальные формы Построение минимальных ДНФ Теорема Поста и классы Критерий Поста Схемы из функциональных элементов Конечные автоматы и регулярные языки Конечные автоматы и регулярные языки Алфавит, слово, язык в программировании Порождающие грамматики (грамматики Хомского) Классификация грамматик и языков Регулярные языки и регулярные выражения Конечные автоматы Допустимость языка конечным автоматом Теорема Клини Детерминизация конечных автоматов Минимизация конечных автоматов Лемма о разрастании для регулярных языков Обоснование алгоритма детерминизации автоматов Конечные автоматы с выходом Морфизмы и конечные подстановки Машины Тьюринга Контекстно-свободные языки Контекстно-свободные языки и грамматики Приведенная форма КС-грамматики Лемма о разрастании для КС-языков Магазинные автоматы (автомат с магазинной памятью) Алгоритм построения МП-автомата по КС-грамматике Алгоритм построения КС-грамматики по МП-автомату Алгебраические свойства КС-языков Основное свойство суперпозиции КС-языков Пересечение контекстно-свободных языков Методы синтаксического анализа КС-языков Восходящий синтаксический анализ и LR(k)-грамматики Семантика формальных языков Принцип индукции по неподвижной точке Графовое представление МП-автоматов Интегральное исчисление Неопределённый и определённый Неопределенный и определенный интегралы Свойства интегралов Интегрирование по частям Интегрирование методом замены переменной Интегрирование различных рациональных функций Интегрирование различных иррациональных функций Интегрирование различных тригонометрических функций Определенный интеграл и его основные свойства Необходимое и достаточное условие интегрируемости Теоремы существования первообразной Свойства определенных интегралов Несобственные интегралы Интегральное определение логарифмической функции Приложения интегралов Вычисление площадей плоских фигур Площади фигур в различных координатах Вычисление объемов тел с помощью интегралов Объём тела вращения Вычисление длин дуг кривых Формулы длины дуги регулярной кривой Кривизна плоской кривой Площадь поверхности вращения тела Интегралы в физике Статические моменты и координаты центра тяжести Теоремы Гульдина–Паппа Вычисление моментов инерции Другие приложения интегралов в физике Основные интегралы Интеграл Ньютона-Лейбница Интеграл Римана Интеграл Лебега Вариационное исчисление Примеры вариационных задач Дифференциальное уравнение Эйлера Функционалы, зависящие от нескольких функций Задача о минимуме кратного интеграла Финансовый анализ Анализ эффективности Критерии и показатели эффективности предприятия Методы анализа эффективности деятельности Факторный анализ прибыли от операционной деятельности Анализ безубыточности предприятия Операционный рычаг и эффект финансового рычага Анализ и оценка состава, структуры и динамики доходов и расходов Анализ рентабельности и резервов устойчивого роста капитала Анализ распределения прибыли предприятия Анализ и оценка чувствительности показателей эффективности Анализ устойчивости Финансовая устойчивость и долгосрочная платежеспособность Характеристика типов финансовой устойчивости Рыночная активность Финансовый анализ рыночной активности Методика анализа рыночной активности Анализ и оценка дивидендного дохода на одну акцию Инвестиционная деятельность Инвестиции: экономическая сущность и классификация Государственное регулирование инвестиционной деятельности Источники финансовых ресурсов на капитальные вложения Инвестиции в основные фонды Оценка состояния основных фондов Амортизация основных фондов Капитальное строительство в инвестиционном процессе Планирование инвестиций в форме капитальных вложений Экономическая эффективность инвестиций Финансирование капитальных вложений Кредитование капитальных вложений Кредитоспособность Финансирование и кредитование затрат Финансирование и кредитование инвестиционной деятельности потребительской кооперации Финансирование и кредитование капитальных вложений потребительской кооперации Инвестиционное строительное проектирование Анализ инвестиций Инвестиции и инвестиционная деятельность предприятия Задачи финансового анализа инвестиций предприятия Учет фактора времени в инвестиционной деятельности Аннуитет и финансовая рента в инвестициях Учет фактора инфляции при инвестировании Оценка фактора риска инвестиционного проекта Методы оценки эффективности инвестиций Показатели эффективности инвестиционного проекта Стоимость компании Концепция построения международных стандартов финансовой отчетности (МСФО) Экономическое содержание международных стандартов финансовой отчётности Цели и принципы оценки стоимости акций и активов компании Оценка акций и активов предприятия по справедливой стоимости Методы оценки справедливой стоимости акций предприятия Затратный подход к оценки стоимости компаний и акций Сравнительный подход к оценки стоимости предприятий и акций Доходный подход к оценке стоимости компании и акций Выбор ставки дисконтирования при инвестировании в акции Метод капитализации прибыли Сравнение подходов к оценке стоимости компаний и пакетов акций Форвардные контракты Форвардный контракт и цена Форвардная цена акции на бирже Цена форвардного контракта инвестора Форвардная цена акции с учетом величины дивиденда Форвардная цена акции с учетом ставки дивиденда Форвардная цена валюты на рынке форекс Форвардный валютный курс и инфляция на рынке Форвардная цена товара и спотовый рынок Форвардная цена при различии ставок по кредитам и депозитам Синтетический форвардный контракт на акции и валюту Теория вероятностей Основные понятия теории вероятностей Зависимые и независимые случайные события Повторные независимые испытания Формула Бернулли Одномерные случайные величины Многомерные случайные величины Функции случайных величин Законы распределения целочисленных случайных величин Законы распределения непрерывных случайных величин Предельные теоремы теории вероятностей Закон больших чисел и предельные теоремы Вероятностные закономерности Математическая статистика Элементы математической статистики Выборочный метод Оценки параметров генеральной совокупности Статистические гипотезы Критерии согласия Теоретические и эмпирические частоты Теория очередей (СМО) Определение системы массового обслуживания Уравнения Колмогорова Предельные вероятности состояний Определение СМО с отказами Определение СМО с ожиданием (очередью) Аналитическая геометрия Векторная алгебра Метрические понятия и аксиомы геометрии Равенство и подобие геометрических фигур Бинарные отношения Вектор, его направление и длина Линейные операции над векторами Линейная зависимость и независимость векторов Отношение коллинеарных векторов Проекции векторов на прямую и на плоскость Угол между векторами Ортогональные проекции векторов Координата вектора на прямой и базис Координаты вектора на плоскости и базис Координаты вектора в пространстве и базис Операции над векторами в координатной форме Ортогональный и ортонормированный базисы Cкалярное произведение векторов и его свойства Выражение скалярного произведения через координаты векторов Векторное произведение векторов и его свойства Смешанное произведение векторов и его свойства Ориентированные площади и объемы Двойное векторное произведение и его свойства Применение векторов в задачах на аффинные свойства фигур Применение произведений векторов при решении геометрических задач Применение векторной алгебры в механике Системы координат Прямоугольные координаты Преобразования прямоугольных координат Полярная система координат Цилиндрическая система координат Сферические координаты Аффинные координаты Аффинные преобразования координат Аффинные преобразования плоскости Примеры аффинных преобразований плоскости Аффинные преобразования пространства Многомерное координатное пространство Линейные и аффинные подпространства Скалярное произведение n-мерных векторов Преобразования систем координат Геометрия на плоскости Алгебраические линии на плоскости Общие уравнения геометрических мест точек Алгебраические уравнения линий на плоскости Уравнения прямой, проходящей через точку перпендикулярно вектору Уравнения прямой, проходящей через точку коллинеарно вектору Уравнения прямой, проходящей через две точки Уравнения прямой с угловым коэффициентом Взаимное расположение прямых Примеры задач с прямыми на плоскости Системы неравенств с двумя неизвестными Системы линейных уравнений с двумя неизвестными Линии 2-го порядка Канонические уравнения линий второго порядка Порядок приведения уравнения линии к каноническому виду Эллипс Гипербола Парабола Квадратичные неравенства с двумя неизвестными Применение линий 1-го и 2-го порядков в задачах на экстремум функций Инварианты линий Классификация линий 2-го порядка по инвариантам Приведение уравнения линии к каноническому виду по инвариантам Геометрия в пространстве Способы задания ГМТ в пространстве Алгебраические уравнения поверхностей Уравнения плоскости, проходящей через точку перпендикулярно вектору Уравнения плоскости, компланарной двум неколлинеарным векторам Уравнения плоскости, проходящей через три точки Взаимное расположение плоскостей Типовые задачи с плоскостями Уравнения прямых в пространстве Взаимное расположение прямых в пространстве Типовые задачи с прямыми в пространстве Поверхности 2-го порядка Канонические уравнения поверхностей Порядок приведения уравнения поверхности к каноническому виду Поверхности второго порядка Эллипсоиды Гиперболоиды Конусы Параболоиды Применение поверхностей 1-го и 2-го порядков в задачах на экстремум функций Инварианты поверхностей Классификация поверхностей 2-го порядка по инвариантам Квадратичные неравенства с тремя неизвестными Приведение уравнения поверхности к канониче-скому виду по инвариантам Линейная алгебра Матрицы и операции Линейные операции над матрицами Умножение матриц Возведение матриц в степень Многочлены от матриц Транспонирование и сопряжение матриц Блочные матрицы Произведение и сумма матриц Кронекера Метод Гаусса приведения матрицы к ступенчатому виду Элементарные преобразования матриц Определители Определители матриц и их основные свойства Формула полного разложения определителя Формула Лапласа полного разложения определителя Определитель произведения матриц Методы вычисления определителей Ранг матрицы Линейная зависимость и линейная независимость строк (столбцов) матрицы Ранг матрицы и базисный минор матрицы Методы вычисления ранга матрицы Ранг системы столбцов (строк) Обратная матрица Обратные матрицы и их свойства Ортогональные и унитарные матрицы Способы нахождения обратной матрицы Матричные уравнения Односторонние обратные матрицы Скелетное разложение матрицы Полуобратная матрица Псевдообратная матрица Системы уравнений Системы линейных алгебраических уравнений Метод Гаусса решения систем линейных уравнений Структура общего решения системы уравнений Решение систем с помощью полуобратных матриц Псевдорешения системы линейных уравнений Функциональные матрицы Функциональные матрицы скалярного аргумента Производные матриц по векторному аргументу Линейные и квадратичные формы и их преобразования Приведение форм к каноническому виду Закон инерции вещественных квадратичных форм Знакоопределенность форм вещественных квадратичных Формы и исследование функций на экстремум Многочленные матрицы Многочленные матрицы (лямбда-матрицы) Операции над лямбда-матрицами Простые преобразования многочленных матриц Инвариантные множители многочленной матрицы Функции от матриц Собственные векторы и значения матрицы Подобие числовых матриц Характеристический многочлен матрицы Минимальный многочлен матрицы Теорема Гамильтона-Кэли Жорданова форма матрицы Приведение матрицы к жордановой форме Многочлены от матриц Применение многочленов от матриц Функции от матриц Линейные пространства Линейные пространства: определение и примеры Линейная зависимость и независимость n-мерных векторов Размерность и базис линейного пространства Преобразования координат в линейном пространстве Изоморфизм линейных пространств Подпространства Подпространства линейного пространства Пересечение и сумма подпространств Способы описания подпространств Нахождение дополнения и суммы подпространств Нахождение пересечения подпространств Линейные отображения Линейные многообразия Линейные отображения Матрица линейного отображения Ядро и образ линейного отображения Линейные операторы Линейные операторы (преобразования) Инвариантные подпространства Собственные векторы и значения оператора Свойства собственных векторов операторов Канонический вид линейного оператора Методика приведения линейного преобразования к каноническому виду Евклидовы пространства Евклидовы пространства Ортогональные векторы евклидова пространства Ортогональный базис евклидова пространства Ортонормированный базис евклидова пространства Ортогональные дополнения в евклидовом пространстве Задача о перпендикуляре Матрица и определитель Грама и его свойства Линейные преобразования евклидовых пространств Канонический вид ортогонального оператора евклидова пространства Сопряженные операторы евклидова пространства Самосопряженные операторы евклидова пространства Приведение квадратичной формы к главным осям Унитарные пространства и их линейные преобразования Комплексный анализ Комплексные числа Комплексные числа в алгебраической форме Комплексные числа в тригонометрической и показательной формах Множества на комплексной плоскости Последовательности и ряды комплексных чисел Комплексные функции Функции комплексного переменного. Предел, непрерывность и производная Элементарные функции комплексного переменного Дифференцирование функций комплексного переменного Аналитические функции и их свойства Конформные отображения и их свойства Интегрирование функций комплексного переменного Функциональные ряды в комплексной области Функциональные ряды и последовательности Степенные ряды и их свойства Разложение функций в степенные ряды Нули аналитических функций Ряд Лорана и разложение функций по целым степеням Особые точки, Вычеты Изолированные особые точки функций и полюсы Вычеты и их применение Вычисление интегралов с помощью вычетов Вычеты и расположение нулей многочлена Операционное исчисление Преобразование Лапласа и его свойства Решение ДУ операционным методом Анализ выходных процессов линейных стационарных систем Z-преобразование и его свойства Дифференциальные уравнения ДУ первого порядка Основные понятия и определения ДУ Метод изоклин для ДУ 1-го порядка Метод последовательных приближений ДУ с разделяющимися переменными Однородные ДУ Линейные ДУ 1-го порядка Дифференциальное уравнение Бернулли ДУ в полных дифференциалах Интегрирующий множитель ДУ, не разрешенные относительно производной Дифференциальное уравнение Риккати Составление ДУ семейств линий Задачи на траектории Особые решения ДУ ДУ высших порядков Понятия и определения ДУ высших порядков ДУ, допускающие понижение порядка Линейная независимость функций Определители Вронского и Грама Однородные и неоднородные дифференциальные уравнения Задача Коши и Уравнение Эйлера Линейные ДУ с переменными коэффициентами Метод Лагранжа решения ДУ Краевые задачи для ДУ высших порядков Разложение решения ДУ в степенной ряд Разложение решения ДУ в обобщенный степенной ряд Нахождение периодических решений ДУ Асимптотическое интегрирование ДУ Системы ДУ Системы ДУ: понятия и определения Сведение системы ДУ к одному уравнению Нахождение интегрируемых комбинаций Интегрирование однородных линейных систем ДУ Методы интегрирования неоднородных систем ДУ Преобразование Лапласа и решение ДУ и систем Теория устойчивости Устойчивость решений ДУ по Ляпунову Простейшие типы точек покоя Метод функций Ляпунова Устойчивость решений ДУ по первому приближению Критерии устойчивости Рауса–Гурвица и Михайлова ДУ с малым параметром при производной Численные методы Методы алгебры Численные методы линейной алгебры Численные методы решения СЛАУ Итерационный метод Шульца обратной матрицы Методы решения задач о собственных значениях и векторах матрицы Методы решения нелинейных уравнений Методы решения систем нелинейных уравнений Методы теории приближений Методы приближения сеточных функций Методы функциональной интерполяции Методы интегрально-дифференциальной интерполяции Методы интегрального сглаживания Методы интерполяции и сглаживания сплайнами Методы численного дифференцирования и интегрирования Методы численного дифференцирования Методы численного интегрирования Методы решения обыкновенных ДУ Численные методы решения задачи Коши Разностные схемы для решения задачи Коши Составные схемы для решения задачи Коши Экстраполяционные методы решения задачи Коши Непрерывно-дискретные методы решения задачи Коши Численные методы решения краевых задач Методы решения ДУ в частных производных Численные методы решения уравнений математической физики с двумя переменными Принципы построения разностных схем для уравнений в частных производных Разностные схемы решения уравнений в частных производных 1-го порядка Разностные схемы решения уравнений в частных производных 2-го порядка Численные методы решения уравнений в частных производных Численные методы решения уравнений математической физики с тремя переменными	Контекстно-свободные языки и грамматики Мы приступаем к изучению одного из важнейших классов формальных языков — класса контекстно-свободных языков (КС-языков). Определение КС-грамматик и КС-языков было дано ранее. Напомним, что порождающую грамматику $G=(V,N,S,P)$ называют контекстно-свободной (или КС-грамматикой), если каждое правило вывода из множества $P$ имеет вид $A\to\gamma$ , где $A\in N$ — нетерминал, а $\gamma\in(V\cup N)^{\ast}$ — цепочка в объединенном алфавите грамматики. Таким образом, неформально каждое правило вывода в КС-грамматике есть правило замены нетерминального символа цепочкой (возможно, пустой) в объединенном алфавите. Каждому выводу в КС-грамматике, начинающемуся с нетерминального символа, однозначно сопоставляется ориентированный граф, являющийся деревом и называемый деревом вывода. Вершины дерева вывода помечаются символами объединенного алфавита грамматики или пустой цепочкой. Подчеркнем, что дерево вывода сопоставляется не грамматике, а конкретному выводу в данной грамматике, хотя мы увидим, что нескольким различным выводам может быть сопоставлено одно и то же дерево вывода. Прежде чем давать математическое определение дерева вывода, покажем на примере, как по данному выводу в заданной КС-грамматике строится это дерево. Пример 8.1. Рассмотрим КС-грамматику $G_0=(\{a,b\},\{S,A,B,C\},S,P_0)$ , где множество правил вывода $P_0$ имеет вид: $\begin{array}{lrlr}S\to ABC,&\quad (1)&\qquad B\to a,&\quad (5)\\ A\to BB,&\quad (2)&\qquad C\to AA,&\quad (6)\\ A\to\lambda,&\quad (3)&\qquad C\to b.&\quad (7)\\ B\to CC,&\quad (4)&\qquad & \end{array}$ В этой грамматике рассмотрим такой вывод: $\begin{aligned}&S\vdash_{(1)} ABC\vdash_{(2)} BBBC\vdash_{(6)} BBBAA\vdash_{(3)} BBB\lambda A\vdash_{(4)} CCBBA\vdash_{(7)}^2\\ &\vdash_{(7)}^2 bbBBA\vdash_{(5)}^2 bbaaA\vdash_{(2)} bbaaBB\vdash_{(5)}^2 bbaaaa.\end{aligned}$ По шагам этого вывода проследим процесс построения дерева вывода. Первому шагу соответствует дерево, изображенное на рис. 8.1. Корень этого дерева (куста) помечен заменяемым на данном шаге нетерминалом, а метки листьев, перечисленные слева направо, образуют цепочку, полученную после применения правила (1) на первом шаге. Вообще же цепочку, полученную в результате такого перечисления меток листьев, называют кроной дерева. Допуская некоторую вольность речи, кроной дерева называют и соответствующую перестановку множества листьев. На втором шаге применяется правило (2) и производится замена вхождения (единственного в данном случае) символа $A$ цепочкой $BB$ . Поэтому вершину дерева на рис. 8.1 с меткой $A$ заменим кустом, Рис. 8.2 как показано на рис. 8.2. После двух шагов получим дерево, изображенное на рис. 8.3. Действуя аналогично, после третьего шага получим дерево, показанное на рис. 8.4. Четвертый шаг требует более подробного комментария. Здесь в кроне дерева имеется несколько вхождений символа $A$ . На четвертом шаге первое вхождение символа $A$ в цепочку $BBAA$ заменяется пустой цепочкой. Поэтому очередной шаг в построении дерева будет состоять в том, что первый лист с меткой $A$ кроне дерева должен быть заменен кустом с корнем $A$ и единственным листом с меткой $\lambda$ . Тогда получим дерево, изображенное на рис. 8.5. Крона вновь полученного дерева — это цепочка $BBB\lambda A$ , выведенная из аксиомы за четыре шага. Она, как элемент свободного моноида $(V\cup N)^{\ast}$ , равна (в силу известных свойств пустой цепочки ) цепочке $BBBA$ . Обратим здесь внимание на то, что, хотя пустая цепочка и не является символом ни одного из алфавитов грамматики, она, как было уже сказано, может быть меткой вершины дерева вывода. Тем самым в дереве вывода фиксируются все вхождения выбрасываемых, т.е. заменяемых в процессе вывода пустой цепочкой, нетерминалов. Это равносильно выделению в выводимой цепочке некоторых вхождений в нее пустой цепочки. На пятом шаге первое вхождение символа $B$ в цепочку $BBBA$ заменяется цепочкой $CC$ . Этому отвечает новое построение на очередном дереве, состоящее в замене первого листа кроны с меткой $B$ кустом, изображенным на рис. 8.6, после чего получим дерево, показанное на рис. 8.7. Действуя дальше точно так же, получим в результате дерево вывода, изображенное на рис. 8.8. Из разобранного примера следует, что шаги построения дерева вывода в точности соответствуют шагам самого вывода, причем после каждого шага получаем некоторое дерево (назовем его частичным деревом вывода, полученным после данного шага). Начинаем построение с корня, и его меткой служит тот нетерминал, с которого начинается вывод (в частности, это может быть аксиома грамматики). Если на очередном шаге вывода применяется правило $B\to X_1X_2\ldots X_m$ , где $X_i\,(1\leqslant i\leqslant m)$ — либо символ объединенного алфавита, либо пустая цепочка, то тот лист частичного дерева вывода, полученного перед этим шагом, который имеет метку $B$ и соответствует заменяемому вхождению символа $B$ , заменяется кустом с корнем $B$ и листьями $X_1,X_2,\ldots,X_m$ . Замечание 8.1. 1. Прежде всего нужно отчетливо понимать, что на каждом шаге построения дерева вывода "развертывается" в куст не любая вершина, меткой которой служит некий нетерминал, а именно та вершина, которая соответствует заменяемому вхождению указанного нетерминала. 2. Совершенно необязательно рассматривать только деревья выводов терминальных цепочек а из аксиомы. Дерево вывода может быть построено по выводу любой цепочки в объединенном алфавите из любого нетерминала грамматики. Так, мы могли бы на базе разобранного выше примера нарисовать дерево вывода цепочки $CCa$ из нетерминала $A$ , показанное на рис. 8.9. 3. Можно заметить, что разные выводы одной и той же цепочки из заданного нетерминала могут дать одно и то же дерево вывода. Так, дерево, изображенное на рис. 8.9, можно построить по двум различным выводам: $A\vdash BB\vdash CCB\vdash CCa$ и $A\vdash BB\vdash Ba\vdash CCa$ . Выводы, имеющие одно и то же дерево вывода, естественно считать эквивалентными. Они различаются между собой только порядком, в котором применяются правила вывода. Дерево вывода и служит способом наглядного изображения всех эквивалентных выводов. Кроме того, как мы увидим позже, дерево вывода является одним из основных инструментов доказательства утверждений о КС-языках и КС-грамматиках. Здесь, в рамках сугубо неформального изложения, мы не даем строгого определения эквивалентных выводов. Теперь дадим формальное определение дерева вывода. Рассмотрим множество (ориентированных) деревьев, вершины которых помечены символами некоторого алфавита $W$ . Ориентированное дерево, каждая вершина которого помечена символом некоторого алфавита, будем называть помеченным деревом. Если, кроме того, задано определенное правило перечисления меток вершин дерева, образующих некоторое подмножество вершин всего дерева, в частности листьев дерева, то такое помеченное дерево называют упорядоченным деревом. Всюду в дальнейшем, изображая деревья выводов, условимся понимать их как упорядоченные деревья, метки листьев которых перечисляются всегда слева направо. Слева направо будем также перечислять и сыновей каждой вершины. Будем считать, что в машинном представлении деревьев выводов порядок "слева направо" при изображении дерева на плоскости соответствует порядку от первого элемента списка смежности вершины к последнему. Дерево, корень которого помечен символом $A$ , а листья имеют метки $X_1,X_2,\ldots,X_m$ , договоримся записывать в виде цепочки $A\downdownarrows X_1X_2\ldots X_m$ (с двумя стрелками). Если рассматриваемое дерево является кустом, то условимся писать $A\downarrow X_1X_2\ldots X_m$ (с одной стрелкой). Листья дерева, обозначенного таким образом, отождествим с символами цепочки $X_1,X_2,\ldots,X_m$ . Это значит, что, говоря о листе $X_i$ , мы имеем в виду лист помеченного дерева, меткой которого является символ $X_i$ и который в перечислении листьев слева направо получает номер $i$ . Тем самым устанавливается взаимно однозначное соответствие между листьями помеченного дерева и вхождениями символов алфавита $W$ в цепочку $X_1,X_2,\ldots,X_m$ . Например, записывая дерево в виде $A\downdownarrows BBCBC$ , мы можем говорить о листе $B$ , соответствующем первому вхождению символа $B$ в цепочку $BBCBC$ , или же, обозначив $BBCBC$ через $\alpha$ , о листе $\alpha(1)$ . Тогда листья $\alpha(1),\, \alpha(2)$ и $\alpha(4)$ — это разные листья дерева, хотя их меткой является один и тот же символ алфавита $W$ . Расширим множество помеченных деревьев, допуская в качестве меток их вершин и пустую цепочку. В этом случае, в записи $A\downdownarrows X_1X_2\ldots X_m$ , представляющей дерево корнем $A$ и листьями $X_1,X_2,\ldots,X_m$ , среди меток листьев, т.е. элементов $X_i,~i=\overline{1,m}$ могут быть и пустые цепочки. Тогда, говоря о листе с меткой $\lambda$ , нужно указывать, какое вхождение пустой цепочки $\lambda$ в цепочку $X_1X_2\ldots X_m$ имеется в виду. Пример 8.2. а. Дерево вывода, изображенное на рис. 8.8, может быть обозначено так: $S\downdownarrows bbaa\lambda aa$ . В нем лист с меткой $\lambda$ ответствует вхождению $(bbaa,\lambda,aa)$ пустой цепочки в цепочку $bbaaaa$ . б. Для грамматики из примера 8.1 вывод $\begin{aligned}S&\vdash ABC\vdash BBBC\vdash aBBC\vdash aCCBC\vdash aAACBC\vdash a\lambda ACBC\vdash a\lambda\lambda CBC\vdash\\ &\vdash a\lambda\lambda AABC\vdash a\lambda\lambda\lambda ABC\vdash a\lambda\lambda\lambda\lambda BC\vdash a\lambda\lambda\lambda\lambda aC\vdash a\lambda\lambda\lambda\lambda ab=aab\end{aligned}$ имеет дерево, показанное на рис. 8.10. В этом дереве любой его лист с меткой $\lambda$ соответствует одному и тому же вхождению пустой цепочки в выводимую цепочку $aab$ , а именно вхождению $(a,\lambda,ab)$ , так как для любого натурального $n$ выполняется равенство $\lambda^n=\lambda$ . в. Представленное на рис. 8.11 дерево вывода цепочки $aabaa$ может быть задано записью $S\downdownarrows aa\lambda\lambda b\lambda aa$ . Оно имеет три листа с меткой $\lambda$ . Первые два соответствуют вхождению $(aa,\lambda,baa)$ , а третье — вхождению $(aab,\lambda,aa)$ пустой цепочки в выводимую цепочку. Помеченное дерево $A\downdownarrows X_1X_2\ldots X_m$ называют λ-свободным, если среди меток $X_1,X_2,\ldots,X_m$ его листьев нет пустой цепочки. Из предыдущих примеров можно заключить, что не всякая цепочка, выводимая в КС-грамматике из какого-либо нетерминала, имеет λ-свободное дерево вывода. Помеченное дерево, полученное из дерева $A\downdownarrows X_1\ldots X_{i-1}X_iX_{i+1}\ldots X_m$ заменой листа $X_i\ne\lambda$ деревом $X\downdownarrows Y_1\ldots Y_k$ , будем записывать в виде цепочки $A\downdownarrows X_1\ldots X_{i-1}[X\downdownarrows Y_1\ldots Y_k]X_{i+1}\ldots X_m\,.$ Это дерево, поскольку в нем вместо листа $X_i$ , возникают листья с метками $Y_1\ldots Y_k$ , можно представить также в виде $A\downdownarrows X_1\ldots X_{i-1}Y_1\ldots Y_kX_{i+1}\ldots X_m\,.$ Дерево вывода цепочки $\beta$ в объединенном алфавите из нетерминала $A$ в КС-грамматике $G=(V,N,S,P)$ — это помеченное дерево, метками вершин которого являются символы объединенного алфавита $V\cup N$ или пустая цепочка $\lambda$ и которое строится по следующим правилам: 1) дерево любого вывода длины 0 состоит из единственной вершины, помеченной нетерминалом $A$ (в данном случае цепочка $\beta=A$ ); 2) дерево вывода $A\vdash\lambda$ — это дерево $A\downarrow\lambda$ (в данном случае цепочка $\beta=\lambda$ ); 3) дерево вывода $A\vdash\alpha$ , где $\alpha$ — непустая цепочка, есть дерево $A\downarrow\alpha$ ; 4) если $\alpha$ — цепочка в объединенном алфавите и $A\downdownarrows X_1X_2\ldots X_m$ дерево некоторого вывода $\mathbf{D}$ этой цепочки из нетерминала $A$ , где $\alpha=X_1X_2\ldots X_m$ и для каждого $i=\overline{1,m}$ имеем $X_i\in V\cup N\cup\{\lambda\}$ , а для некоторого $i\in[1,m]$ есть $X_i=B\in N$ — нетерминальный символ грамматики $G$ , и в множестве правил вывода $P$ грамматики $B$ есть правило $B\to Y_1\ldots Y_k$ , то дерево $A\downdownarrows X_1\ldots X_{i-1}[X_i\downarrow Y_1\ldots Y_k]Y_{i+1}\ldots Y_m$ есть дерево такого вывода цепочки $\beta= X_1\ldots X_{i-1} Y_1\ldots Y_kX_{i+1}\ldots X_m$ из нетерминала $A$ , что его последний шаг имеет вид $X_1\ldots X_{i-1}BX_{i+1}\ldots X_m\vdash_{B\to Y_1\ldots Y_k} X_1\ldots X_{i-1} Y_1\ldots Y_kX_{i+1}\ldots X_m\,,$ а вывод цепочки $\alpha=X_1\ldots X_{i-1}BX_{i+1}\ldots X_m$ из $A$ совпадает с $\mathbf{D}$ . Все выводы данной цепочки из данного нетерминала, по которым приведенный выше алгоритм дает одно и то же дерево вывода, будем называть эквивалентными. Среди эквивалентных выводов выделим два — левый вывод, в котором на каждом шаге заменяется самое левое вхождение нетерминального символа; и правый вывод, когда на каждом шаге, напротив, производится замена самого правого вхождения нетерминала. Это значит, что при построении дерева вывода по левому выводу данной цепочки $\alpha$ из данного нетерминала $A$ каждый раз "развертывается" в куст самый левый лист кроны частичного дерева вывода, помеченный нетерминальным символом, а при построении дерева вывода по правому выводу то же совершается с самым правым листом кроны. Для построенного выше в примере 8.2.а дерева вывода левый вывод имеет вид $\begin{aligned}S&\vdash \boldsymbol{A}BC\vdash \boldsymbol{B}BBC\vdash \boldsymbol{C}CBBC\vdash b\boldsymbol{C}BBC\vdash bb\boldsymbol{B}BC\vdash bba\boldsymbol{B}C\vdash bbaa\boldsymbol{C}\vdash\\ &\vdash bbaa\boldsymbol{A}A\vdash bbaa\lambda\boldsymbol{A}\vdash bbaa\boldsymbol{B}B\vdash bbaaa\boldsymbol{B}\vdash bbaaaa\,.\end{aligned}$ Правый вывод той же цепочки имеет вид $\begin{aligned}S&\vdash AB\boldsymbol{C}\vdash ABA\boldsymbol{A}\vdash ABAB\boldsymbol{B}\vdash ABA\boldsymbol{B}a\vdash ABAaa\vdash A\boldsymbol{B}\lambda aa\vdash\\ &\vdash \boldsymbol{A}aaa\vdash B\boldsymbol{B}aaa\vdash \boldsymbol{B}aaaa\vdash C\boldsymbol{C}aaaa\vdash \boldsymbol{C}baaaa\vdash bbaaaa\,.\end{aligned}$ В обоих выводах полужирным шрифтом выделены заменяемые вхождения нетерминалов, а также удалено возникающее после применения правила $A\to\lambda$ вхождение пустой цепочки $\lambda$ . Можно показать, что эквивалентные выводы различаются между собой только порядком применения правил. Сами же применяемые правила и вхождения заменяемых нетерминалов у эквивалентных выводов одинаковы. Мы часто будем использовать условное графическое обозначение дерева вывода $A\downdownarrows X_1X_2\ldots X_m$ в виде "треугольника", одна из вершин которого помечена нетерминалом $A$ , а противолежащая этой вершине сторона символизирует всю цепочку $\alpha= X_1X_2\ldots X_m$ . Иногда будем точками (или штрихами) отмечать отдельные символы цепочки $\alpha$ или листья с меткой $\lambda$ (рис. 8.12). Кроме того, по традиции деревья выводов изображаются без стрелок на дугах (хотя понимаются как ориентированные деревья). Из определения дерева вывода понятно, что в нем дуга из вершины с меткой $X$ ведет в вершину с меткой $Y$ тогда и только тогда, когда на некотором шаге вывода применяется правило вывода $X\to\gamma_1 Y\gamma_2$ , где $\gamma_1$ и $\gamma_2$ — цепочки в объединенном алфавите (возможно, пустые). Следовательно, число дуг любого пути ненулевой длины дерева вывода, т.е. длина этого пути, есть не что иное, как число применений правил вывода заданной КС-грамматики в некотором фрагменте вывода. А так как в КС-грамматике каждое применение правила вывода есть замена вхождения нетерминала некоторой цепочкой в объединенном алфавите, то длина пути в дереве вывода равна числу замен нетерминалов в соответствующем фрагменте вывода. Например, для дерева, показанного на рис. 8.8, пути $S\to A\to B\to a$ отвечает фрагмент вывода $S\vdash ABC\vdash BBBC\vdash BaBC$ . Обратим внимание на то, что приведенный фрагмент есть фрагмент одного из множества эквивалентных выводов, имеющих данное дерево. Таким образом, по заданному пути в дереве вывода однозначно восстанавливается фрагмент одного из множества эквивалентных выводов. Более того, по дереву вывода, построенному по одному из множества эквивалентных выводов, можно восстановить все выводы этого множества, в частности левый и правый. Можно показать, что для этого необходимо задать определенный порядок посещения вершин дерева при поиске в глубину от корня. Левый (соответственно правый) вывод будет восстановлен, если каждый раз при поиске в глубину от очередной вершины задавать продолжение поиска от самого левого (соответственно самого правого) сына этой вершины. Замечание 8.2. Длина вывода в общем случае не меньше, чем высота дерева этого вывода. Можно доказать, что для фиксированной КС-грамматики $G$ существует такая константа $C_G$ , зависящая от $G$ , что для любого вывода $\mathbf{D}$ (начинающегося каким-либо нетерминалом) и дерева $\mathbf{T}$ этого вывода разность между длиной $l_{\mathbf{D}}$ вывода $\mathbf{D}$ и высотой $h_{\mathbf{T}}$ дерева $\mathbf{T}$ не превышает $C_G\colon l_{\mathbf{D}}- h_{\mathbf{T}}\leqslant C_G$ . Другими словами, разность между длиной вывода и высотой дерева вывода для фиксированной грамматики ограничена сверху. Это обусловлено тем, что указанная разность определяется числом нетерминалов в правых частях правил вывода, которое в пределах заданной грамматики всегда ограничено. Это число, говоря неформально, определяет, как сильно "ветвится" дерево вывода в процессе его "роста". Для линейной грамматики, как нетрудно сообразить, высота дерева вывода равна длине вывода. Однако если не фиксировать грамматику, то разность между длиной вывода и высотой дерева вывода может быть сколь угодно большой. Это можно подтвердить таким простым примером. Рассмотрим семейство КС-грамматик $G_m=(V_m,N_m,S,P_m)$ , где $m\geqslant1,~ V_m=\{a_1,\ldots,a_m\},~ N_m=\{S,B_1,\ldots,B_m\}$ , а множество правил вывода $P_m$ имеет вид $S\to B_1\ldots B_m,\qquad B_1\to a_1,\ldots, B_m\to a_m.$ Грамматика $G_m$ порождает единственную терминальную цепочку $a_1,\ldots,a_m$ . Высота дерева вывода этой цепочки равна 2 и не зависит от $m$ (рис. 8.13), тогда как длина вывода определяется числом $m+1$ . Пусть фиксировано ориентированное дерево $\mathbf{T}$ с корнем $R$ . Выделим в нем произвольно вершину $Q$ , не являющуюся ни листом, ни корнем, называемую внутренней вершиной дерева. Образуем поддерево дерева $\mathbf{T}$ , объявив его корнем вершину. Такое поддерево назовем символьным поддеревом, если оно содержит все вершины исходного дерева $\mathbf{T}$ , достижимые из вершины $Q$ . Ясно, что высота любого максимального поддерева больше нуля и меньше высоты дерева $\mathbf{T}$ . Для помеченного дерева $\mathbf{T}$ нетрудно проверить справедливость следующей теоремы. Теорема 8.1. Крона любого максимального поддерева помеченного дерева есть подцепочка кроны всего дерева. Замечание 8.3. Сформулированное утверждение достаточно прозрачно и означает, что если в помеченном дереве $\mathbf{T}$ фиксировать произвольно внутреннюю вершину $Q$ и рассмотреть крону максимального поддерева с корнем $Q$ , то все листья кроны этого поддерева, расположенные между самым левым $(L)$ и самым правым $(L')$ листьями, достижимыми из $Q$ , также достижимы из $Q$ (рис. 8.14). Применяя теорему 8.1 к деревьям выводов в КС-грамматиках, получим следующий результат. Следствие 8.1. Если в дереве вывода некоторой цепочки $\alpha$ из нетерминала $A$ фиксировать произвольно внутреннюю вершину, помеченную нетерминалом $B$ , то максимальное поддерево с корнем в фиксированной вершине (с меткой $B$ ) является деревом вывода некоторой подцепочки $\beta$ цепочки $\alpha$ из нетерминала $B$ , т.е. существуют такие цепочки $\gamma_1$ и $\gamma_2$ , что $\alpha=\gamma_1\beta\gamma_2$ и $A\vdash^{\ast}\gamma_1B\gamma_2\vdash^{\ast}\gamma_1\beta\gamma_2$ (рис. 8.15). Так, для дерева вывода цепочки $bAAa$ из нетерминала $A$ в грамматике $G_0$ из примера 8.1 (рис. 8.16), фиксируя максимальное поддерево с корневой вершиной $C$ С (вторая вершина слева на первом уровне, выделена полужирным шрифтом), получим $\gamma_1=b,~\beta=AA,~ \gamma_2=a$ , Соответствующее этому максимальному поддереву разбиение вывода на два фрагмента, может быть, например, таким: $A\vdash BB\vdash CCB\vdash bCB\vdash bCa$ (первый фрагмент) и $C\vdash AA$ (второй фрагмент). Описанная в следствии 8.1 "декомпозиция" дерева вывода и соответственно вывода, по которому построено это дерево, может быть интерпретирована так: выводя цепочку $\alpha$ из нетерминала $A$ , мы, получив на некотором шаге цепочку, содержащую выделенное вхождение нетерминала $B$ , "замораживаем" этот нетерминал и продолжаем замены нетерминалов слева и справа от $B$ , выводя начало (подцепочку $\gamma_1$ ) и конец (подцепочку $\gamma_2$ ) цепочки $\alpha$ . После этого мы "размораживаем" нетерминал $B$ и "довыводим" из него середину цепочки $\alpha$ — подцепочку $\beta$ . Однозначности КС-грамматики Понятие дерева вывода связано с понятием однозначности КС-грамматики. Определение 8.1. КС-грамматику называют однозначной, если каждая цепочка порождаемого ею языка имеет единственное дерево вывода. Поскольку по дереву вывода цепочки $\alpha$ из нетерминала $A$ однозначно строится как левый, так и правый вывод данной цепочки, то определение 8.1 можно сформулировать иначе: КС-грамматика однозначна, если каждая цепочка порождаемого ею языка имеет единственный левый и единственный правый вывод. Рассмотрим один хрестоматийный пример неоднозначной грамматики. Пример 8.3. Зададим грамматику $GE$ следующим образом: $GE= \bigl(\{a,b,\mathbf{if},\mathbf{then},\mathbf{else}\}, \{S\},S, S\to\mathbf{if}~b~ \mathbf{then}~ S~\mathbf{else}~S\mid \mathbf{if}~b~\mathbf{then}~S\mid a\bigr).$ Эта грамматика описывает "абстрактный синтаксис" операторов условного перехода в некотором "паскалеобразном" языке программирования. Термин "абстрактный синтаксис" в данном случае означает, что мы отвлекаемся от структуры как операторов языка, так и логических условий. Терминальный символ $a$ означает произвольный оператор (или последовательность операторов), а терминальный символ $b$ — произвольное логическое условие. Кроме того, терминалами грамматики являются также лексемы $\mathbf{if},\,\mathbf{then}$ и $\mathbf{else}$ , формирующие "скелет" любого оператора условного перехода. Определенная таким образом грамматика неоднозначна, что усматривается из такого примера: цепочка $\mathbf{if}~b~ \mathbf{then~if}~b~ \mathbf{then}~a~ \mathbf{else}~a$ имеет два дерева вывода (рис. 8.17 и 8.18). Заметим (неформально), что наличие нескольких деревьев вывода одной и той же цепочки имеет отношение к семантике рассматриваемого языка. В данном конкретном примере понятно, что каждому дереву вывода приведенной выше цепочки отвечает свое смысловое прочтение этой цепочки: в первом случае $\mathbf{else}$ мы относим к первому $\mathbf{then}$ , а во втором — ко второму. В итоге получаем две совершенно разные интерпретации оператора условного перехода. Данный пример неоднозначности известен поэтому под названием "кочующее $\mathbf{else}$ ". Исходную грамматику, однако, можно "исправить", построив эквивалентную ей однозначную грамматику: $\begin{aligned}GE_1= \big(& \{a,b, \mathbf{if},\mathbf{then},\mathbf{else}\}, \{S_1,S_2\}, S_1,\\ &S_1\to \mathbf{if}~b~ \mathbf{then}~S_2~\mathbf{else}~ S_1\mid \mathbf{if}~b~ \mathbf{then}~ S_1\mid a,\\ &S_2\to\mathbf{if}~b~\mathbf{then}~S_2~ \mathbf{else}~S_2\mid a\big). \end{aligned}$ В общем случае алгоритма преобразования произвольной неоднозначной КС-грамматики к эквивалентной однозначной не существует. Пример неоднозначности в естественном языке Рассмотрим в заключение интересный пример неоднозначности в естественном языке (точнее, в художественном тексте). В известном стихотворении А.С. Пушкина "К вельможе", адресованном князю Юсупову, владельцу Архангельского, есть такая строка: Посланник молодой увенчанной жены... (Речь идет о том, что князь был послан Екатериной Великой к Вольтеру, великому французскому философу и писателю, состоявшему с Екатериной в переписке.) Процитированную строчку можно прочитать двояко: 1) посланник (молодой увенчанной жены), 2) (посланник молодой) увенчанной жены, т.е. в первом случае эпитет "молодой" отнесен к "жене", а во втором — к "посланнику". Чисто синтаксически эта коллизия неразрешима, но внеязыковый контекст данной фразы, учитывающий совершенно определенные биографические обстоятельства персонажей, позволяет с высокой долей вероятности предположить, что правильным будет второе прочтение. В то же время следующую анекдотическую фразу нельзя рассматривать как пример неоднозначности, ибо она не соответствует грамматическим нормам русского литературного языка: Сдавайте мусор дворнику, который накопился. Приведенные примеры, между прочим, обнаруживают, что понятие однозначности необходимо анализировать в связи с семантикой языка и что "смысл" следует придавать не цепочке языка, а дереву ее вывода. Математический форум (помощь с решением задач, обсуждение вопросов по математике). Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.

Контекстно-свободные языки и грамматики

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

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

Алгоритмы JavaScript

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ранг матрицы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Системы ДУ

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

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

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

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

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

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

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

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

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

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

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

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

Контекстно-свободные языки и грамматики

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

Определение КС-грамматик и КС-языков было дано ранее. Напомним, что порождающую грамматику $G=(V,N,S,P)$ называют контекстно-свободной (или КС-грамматикой), если каждое правило вывода из множества $P$ имеет вид $A\to\gamma$ , где $A\in N$ — нетерминал, а $\gamma\in(V\cup N)^{\ast}$ — цепочка в объединенном алфавите грамматики. Таким образом, неформально каждое правило вывода в КС-грамматике есть правило замены нетерминального символа цепочкой (возможно, пустой) в объединенном алфавите.

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

Пример 8.1. Рассмотрим КС-грамматику $G_0=(\{a,b\},\{S,A,B,C\},S,P_0)$ , где множество правил вывода $P_0$ имеет вид:

$\begin{array}{lrlr}S\to ABC,&\quad (1)&\qquad B\to a,&\quad (5)\\ A\to BB,&\quad (2)&\qquad C\to AA,&\quad (6)\\ A\to\lambda,&\quad (3)&\qquad C\to b.&\quad (7)\\ B\to CC,&\quad (4)&\qquad & \end{array}$

В этой грамматике рассмотрим такой вывод:

$\begin{aligned}&S\vdash_{(1)} ABC\vdash_{(2)} BBBC\vdash_{(6)} BBBAA\vdash_{(3)} BBB\lambda A\vdash_{(4)} CCBBA\vdash_{(7)}^2\\ &\vdash_{(7)}^2 bbBBA\vdash_{(5)}^2 bbaaA\vdash_{(2)} bbaaBB\vdash_{(5)}^2 bbaaaa.\end{aligned}$

Первый шаг процесса построения дерева вывода

По шагам этого вывода проследим процесс построения дерева вывода. Первому шагу соответствует дерево, изображенное на рис. 8.1.

Корень этого дерева (куста) помечен заменяемым на данном шаге нетерминалом, а метки листьев, перечисленные слева направо, образуют цепочку, полученную после применения правила (1) на первом шаге. Вообще же цепочку, полученную в результате такого перечисления меток листьев, называют кроной дерева*.

*Допуская некоторую вольность речи, кроной дерева называют и соответствующую перестановку множества листьев.

Второй шаг процесса построения дерева вывода

На втором шаге применяется правило (2) и производится замена вхождения (единственного в данном случае) символа $A$ цепочкой $BB$ . Поэтому вершину дерева на рис. 8.1 с меткой $A$ заменим кустом, Рис. 8.2 как показано на рис. 8.2.

После двух шагов получим дерево, изображенное на рис. 8.3. Действуя аналогично, после третьего шага получим дерево, показанное на рис. 8.4.

Дерево после третьего шага процесса построения дерева вывода

Четвёртый шаг процесса построения дерева вывода

Четвертый шаг требует более подробного комментария. Здесь в кроне дерева имеется несколько вхождений символа $A$ . На четвертом шаге первое вхождение символа $A$ в цепочку $BBAA$ заменяется пустой цепочкой. Поэтому очередной шаг в построении дерева будет состоять в том, что первый лист с меткой $A$ кроне дерева должен быть заменен кустом с корнем $A$ и единственным листом с меткой $\lambda$ . Тогда получим дерево, изображенное на рис. 8.5.

Крона вновь полученного дерева — это цепочка $BBB\lambda A$ , выведенная из аксиомы за четыре шага. Она, как элемент свободного моноида $(V\cup N)^{\ast}$ , равна (в силу известных свойств пустой цепочки ) цепочке $BBBA$ . Обратим здесь внимание на то, что, хотя пустая цепочка и не является символом ни одного из алфавитов грамматики, она, как было уже сказано, может быть меткой вершины дерева вывода. Тем самым в дереве вывода фиксируются все вхождения выбрасываемых, т.е. заменяемых в процессе вывода пустой цепочкой, нетерминалов. Это равносильно выделению в выводимой цепочке некоторых вхождений в нее пустой цепочки.

Пятый шаг процесса построения дерева вывода

На пятом шаге первое вхождение символа $B$ в цепочку $BBBA$ заменяется цепочкой $CC$ . Этому отвечает новое построение на очередном дереве, состоящее в замене первого листа кроны с меткой $B$ кустом, изображенным на рис. 8.6, после чего получим дерево, показанное на рис. 8.7.

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

Из разобранного примера следует, что шаги построения дерева вывода в точности соответствуют шагам самого вывода, причем после каждого шага получаем некоторое дерево (назовем его частичным деревом вывода, полученным после данного шага). Начинаем построение с корня, и его меткой служит тот нетерминал, с которого начинается вывод (в частности, это может быть аксиома грамматики). Если на очередном шаге вывода применяется правило $B\to X_1X_2\ldots X_m$ , где $X_i\,(1\leqslant i\leqslant m)$ — либо символ объединенного алфавита, либо пустая цепочка, то тот лист частичного дерева вывода, полученного перед этим шагом, который имеет метку $B$ и соответствует заменяемому вхождению символа $B$ , заменяется кустом с корнем $B$ и листьями $X_1,X_2,\ldots,X_m$ .

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

Дерево вывода цепочки CCa для нетерминала A

2. Совершенно необязательно рассматривать только деревья выводов терминальных цепочек а из аксиомы. Дерево вывода может быть построено по выводу любой цепочки в объединенном алфавите из любого нетерминала грамматики. Так, мы могли бы на базе разобранного выше примера нарисовать дерево вывода цепочки $CCa$ из нетерминала $A$ , показанное на рис. 8.9.

3. Можно заметить, что разные выводы одной и той же цепочки из заданного нетерминала могут дать одно и то же дерево вывода. Так, дерево, изображенное на рис. 8.9, можно построить по двум различным выводам:

$A\vdash BB\vdash CCB\vdash CCa$ и $A\vdash BB\vdash Ba\vdash CCa$ .

Выводы, имеющие одно и то же дерево вывода, естественно считать эквивалентными. Они различаются между собой только порядком, в котором применяются правила вывода*. Дерево вывода и служит способом наглядного изображения всех эквивалентных выводов. Кроме того, как мы увидим позже, дерево вывода является одним из основных инструментов доказательства утверждений о КС-языках и КС-грамматиках.

*Здесь, в рамках сугубо неформального изложения, мы не даем строгого определения эквивалентных выводов.

Теперь дадим формальное определение дерева вывода. Рассмотрим множество (ориентированных) деревьев, вершины которых помечены символами некоторого алфавита $W$ . Ориентированное дерево, каждая вершина которого помечена символом некоторого алфавита, будем называть помеченным деревом. Если, кроме того, задано определенное правило перечисления меток вершин дерева, образующих некоторое подмножество вершин всего дерева, в частности листьев дерева, то такое помеченное дерево называют упорядоченным деревом. Всюду в дальнейшем, изображая деревья выводов, условимся понимать их как упорядоченные деревья, метки листьев которых перечисляются всегда слева направо. Слева направо будем также перечислять и сыновей каждой вершины. Будем считать, что в машинном представлении деревьев выводов порядок "слева направо" при изображении дерева на плоскости соответствует порядку от первого элемента списка смежности вершины к последнему. Дерево, корень которого помечен символом $A$ , а листья имеют метки $X_1,X_2,\ldots,X_m$ , договоримся записывать в виде цепочки

$A\downdownarrows X_1X_2\ldots X_m$ (с двумя стрелками).

Если рассматриваемое дерево является кустом, то условимся писать

$A\downarrow X_1X_2\ldots X_m$ (с одной стрелкой).

Листья дерева, обозначенного таким образом, отождествим с символами цепочки $X_1,X_2,\ldots,X_m$ . Это значит, что, говоря о листе $X_i$ , мы имеем в виду лист помеченного дерева, меткой которого является символ $X_i$ и который в перечислении листьев слева направо получает номер $i$ . Тем самым устанавливается взаимно однозначное соответствие между листьями помеченного дерева и вхождениями символов алфавита $W$ в цепочку $X_1,X_2,\ldots,X_m$ . Например, записывая дерево в виде $A\downdownarrows BBCBC$ , мы можем говорить о листе $B$ , соответствующем первому вхождению символа $B$ в цепочку $BBCBC$ , или же, обозначив $BBCBC$ через $\alpha$ , о листе $\alpha(1)$ . Тогда листья $\alpha(1),\, \alpha(2)$ и $\alpha(4)$ — это разные листья дерева, хотя их меткой является один и тот же символ алфавита $W$ .

Расширим множество помеченных деревьев, допуская в качестве меток их вершин и пустую цепочку. В этом случае, в записи $A\downdownarrows X_1X_2\ldots X_m$ , представляющей дерево корнем $A$ и листьями $X_1,X_2,\ldots,X_m$ , среди меток листьев, т.е. элементов $X_i,~i=\overline{1,m}$ могут быть и пустые цепочки. Тогда, говоря о листе с меткой $\lambda$ , нужно указывать, какое вхождение пустой цепочки $\lambda$ в цепочку $X_1X_2\ldots X_m$ имеется в виду.

Пример 8.2. а. Дерево вывода, изображенное на рис. 8.8, может быть обозначено так: $S\downdownarrows bbaa\lambda aa$ . В нем лист с меткой $\lambda$ ответствует вхождению $(bbaa,\lambda,aa)$ пустой цепочки в цепочку $bbaaaa$ .

б. Для грамматики из примера 8.1 вывод

$\begin{aligned}S&\vdash ABC\vdash BBBC\vdash aBBC\vdash aCCBC\vdash aAACBC\vdash a\lambda ACBC\vdash a\lambda\lambda CBC\vdash\\ &\vdash a\lambda\lambda AABC\vdash a\lambda\lambda\lambda ABC\vdash a\lambda\lambda\lambda\lambda BC\vdash a\lambda\lambda\lambda\lambda aC\vdash a\lambda\lambda\lambda\lambda ab=aab\end{aligned}$

имеет дерево, показанное на рис. 8.10. В этом дереве любой его лист с меткой $\lambda$ соответствует одному и тому же вхождению пустой цепочки в выводимую цепочку $aab$ , а именно вхождению $(a,\lambda,ab)$ , так как для любого натурального $n$ выполняется равенство $\lambda^n=\lambda$ .

в. Представленное на рис. 8.11 дерево вывода цепочки $aabaa$ может быть задано записью $S\downdownarrows aa\lambda\lambda b\lambda aa$ . Оно имеет три листа с меткой $\lambda$ .

Первые два соответствуют вхождению $(aa,\lambda,baa)$ , а третье — вхождению $(aab,\lambda,aa)$ пустой цепочки в выводимую цепочку.

Помеченное дерево $A\downdownarrows X_1X_2\ldots X_m$ называют λ-свободным, если среди меток $X_1,X_2,\ldots,X_m$ его листьев нет пустой цепочки. Из предыдущих примеров можно заключить, что не всякая цепочка, выводимая в КС-грамматике из какого-либо нетерминала, имеет λ-свободное дерево вывода.

Помеченное дерево, полученное из дерева

$A\downdownarrows X_1\ldots X_{i-1}X_iX_{i+1}\ldots X_m$

заменой листа $X_i\ne\lambda$ деревом $X\downdownarrows Y_1\ldots Y_k$ , будем записывать в виде цепочки

$A\downdownarrows X_1\ldots X_{i-1}[X\downdownarrows Y_1\ldots Y_k]X_{i+1}\ldots X_m\,.$

Это дерево, поскольку в нем вместо листа $X_i$ , возникают листья с метками $Y_1\ldots Y_k$ , можно представить также в виде

$A\downdownarrows X_1\ldots X_{i-1}Y_1\ldots Y_kX_{i+1}\ldots X_m\,.$

Дерево вывода цепочки $\beta$ в объединенном алфавите из нетерминала $A$ в КС-грамматике $G=(V,N,S,P)$ — это помеченное дерево, метками вершин которого являются символы объединенного алфавита $V\cup N$ или пустая цепочка $\lambda$ и которое строится по следующим правилам:

1) дерево любого вывода длины 0 состоит из единственной вершины, помеченной нетерминалом $A$ (в данном случае цепочка $\beta=A$ );

2) дерево вывода $A\vdash\lambda$ — это дерево $A\downarrow\lambda$ (в данном случае цепочка $\beta=\lambda$ );

3) дерево вывода $A\vdash\alpha$ , где $\alpha$ — непустая цепочка, есть дерево $A\downarrow\alpha$ ;

4) если $\alpha$ — цепочка в объединенном алфавите и $A\downdownarrows X_1X_2\ldots X_m$ дерево некоторого вывода $\mathbf{D}$ этой цепочки из нетерминала $A$ , где $\alpha=X_1X_2\ldots X_m$ и для каждого $i=\overline{1,m}$ имеем $X_i\in V\cup N\cup\{\lambda\}$ , а для некоторого $i\in[1,m]$ есть $X_i=B\in N$ — нетерминальный символ грамматики $G$ , и в множестве правил вывода $P$ грамматики $B$ есть правило $B\to Y_1\ldots Y_k$ , то дерево

$A\downdownarrows X_1\ldots X_{i-1}[X_i\downarrow Y_1\ldots Y_k]Y_{i+1}\ldots Y_m$

есть дерево такого вывода цепочки $\beta= X_1\ldots X_{i-1} Y_1\ldots Y_kX_{i+1}\ldots X_m$ из нетерминала $A$ , что его последний шаг имеет вид

$X_1\ldots X_{i-1}BX_{i+1}\ldots X_m\vdash_{B\to Y_1\ldots Y_k} X_1\ldots X_{i-1} Y_1\ldots Y_kX_{i+1}\ldots X_m\,,$

а вывод цепочки $\alpha=X_1\ldots X_{i-1}BX_{i+1}\ldots X_m$ из $A$ совпадает с $\mathbf{D}$ .

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

Это значит, что при построении дерева вывода по левому выводу данной цепочки $\alpha$ из данного нетерминала $A$ каждый раз "развертывается" в куст самый левый лист кроны частичного дерева вывода, помеченный нетерминальным символом, а при построении дерева вывода по правому выводу то же совершается с самым правым листом кроны.

Для построенного выше в примере 8.2.а дерева вывода левый вывод имеет вид

$\begin{aligned}S&\vdash \boldsymbol{A}BC\vdash \boldsymbol{B}BBC\vdash \boldsymbol{C}CBBC\vdash b\boldsymbol{C}BBC\vdash bb\boldsymbol{B}BC\vdash bba\boldsymbol{B}C\vdash bbaa\boldsymbol{C}\vdash\\ &\vdash bbaa\boldsymbol{A}A\vdash bbaa\lambda\boldsymbol{A}\vdash bbaa\boldsymbol{B}B\vdash bbaaa\boldsymbol{B}\vdash bbaaaa\,.\end{aligned}$

Правый вывод той же цепочки имеет вид

$\begin{aligned}S&\vdash AB\boldsymbol{C}\vdash ABA\boldsymbol{A}\vdash ABAB\boldsymbol{B}\vdash ABA\boldsymbol{B}a\vdash ABAaa\vdash A\boldsymbol{B}\lambda aa\vdash\\ &\vdash \boldsymbol{A}aaa\vdash B\boldsymbol{B}aaa\vdash \boldsymbol{B}aaaa\vdash C\boldsymbol{C}aaaa\vdash \boldsymbol{C}baaaa\vdash bbaaaa\,.\end{aligned}$

В обоих выводах полужирным шрифтом выделены заменяемые вхождения нетерминалов, а также удалено возникающее после применения правила $A\to\lambda$ вхождение пустой цепочки $\lambda$ . Можно показать, что эквивалентные выводы различаются между собой только порядком применения правил. Сами же применяемые правила и вхождения заменяемых нетерминалов у эквивалентных выводов одинаковы.

Мы часто будем использовать условное графическое обозначение дерева вывода $A\downdownarrows X_1X_2\ldots X_m$ в виде "треугольника", одна из вершин которого помечена нетерминалом $A$ , а противолежащая этой вершине сторона символизирует всю цепочку $\alpha= X_1X_2\ldots X_m$ . Иногда будем точками (или штрихами) отмечать отдельные символы цепочки $\alpha$ или листья с меткой $\lambda$ (рис. 8.12). Кроме того, по традиции деревья выводов изображаются без стрелок на дугах (хотя понимаются как ориентированные деревья).

Отдельные символы цепочки или листья с меткой

Из определения дерева вывода понятно, что в нем дуга из вершины с меткой $X$ ведет в вершину с меткой $Y$ тогда и только тогда, когда на некотором шаге вывода применяется правило вывода $X\to\gamma_1 Y\gamma_2$ , где $\gamma_1$ и $\gamma_2$ — цепочки в объединенном алфавите (возможно, пустые). Следовательно, число дуг любого пути ненулевой длины дерева вывода, т.е. длина этого пути, есть не что иное, как число применений правил вывода заданной КС-грамматики в некотором фрагменте вывода. А так как в КС-грамматике каждое применение правила вывода есть замена вхождения нетерминала некоторой цепочкой в объединенном алфавите, то длина пути в дереве вывода равна числу замен нетерминалов в соответствующем фрагменте вывода. Например, для дерева, показанного на рис. 8.8, пути $S\to A\to B\to a$ отвечает фрагмент вывода $S\vdash ABC\vdash BBBC\vdash BaBC$ . Обратим внимание на то, что приведенный фрагмент есть фрагмент одного из множества эквивалентных выводов, имеющих данное дерево.

Таким образом, по заданному пути в дереве вывода однозначно восстанавливается фрагмент одного из множества эквивалентных выводов. Более того, по дереву вывода, построенному по одному из множества эквивалентных выводов, можно восстановить все выводы этого множества, в частности левый и правый. Можно показать, что для этого необходимо задать определенный порядок посещения вершин дерева при поиске в глубину от корня. Левый (соответственно правый) вывод будет восстановлен, если каждый раз при поиске в глубину от очередной вершины задавать продолжение поиска от самого левого (соответственно самого правого) сына этой вершины.

Замечание 8.2. Длина вывода в общем случае не меньше, чем высота дерева этого вывода. Можно доказать, что для фиксированной КС-грамматики $G$ существует такая константа $C_G$ , зависящая от $G$ , что для любого вывода $\mathbf{D}$ (начинающегося каким-либо нетерминалом) и дерева $\mathbf{T}$ этого вывода разность между длиной $l_{\mathbf{D}}$ вывода $\mathbf{D}$ и высотой $h_{\mathbf{T}}$ дерева $\mathbf{T}$ не превышает $C_G\colon l_{\mathbf{D}}- h_{\mathbf{T}}\leqslant C_G$ . Другими словами, разность между длиной вывода и высотой дерева вывода для фиксированной грамматики ограничена сверху. Это обусловлено тем, что указанная разность определяется числом нетерминалов в правых частях правил вывода, которое в пределах заданной грамматики всегда ограничено. Это число, говоря неформально, определяет, как сильно "ветвится" дерево вывода в процессе его "роста". Для линейной грамматики, как нетрудно сообразить, высота дерева вывода равна длине вывода. Однако если не фиксировать грамматику, то разность между длиной вывода и высотой дерева вывода может быть сколь угодно большой. Это можно подтвердить таким простым примером.

Рассмотрим семейство КС-грамматик $G_m=(V_m,N_m,S,P_m)$ , где $m\geqslant1,~ V_m=\{a_1,\ldots,a_m\},~ N_m=\{S,B_1,\ldots,B_m\}$ , а множество правил вывода $P_m$ имеет вид

$S\to B_1\ldots B_m,\qquad B_1\to a_1,\ldots, B_m\to a_m.$

Грамматика $G_m$ порождает единственную терминальную цепочку $a_1,\ldots,a_m$ . Высота дерева вывода этой цепочки равна 2 и не зависит от $m$ (рис. 8.13), тогда как длина вывода определяется числом $m+1$ .

Пусть фиксировано ориентированное дерево $\mathbf{T}$ с корнем $R$ . Выделим в нем произвольно вершину $Q$ , не являющуюся ни листом, ни корнем, называемую внутренней вершиной дерева. Образуем поддерево дерева $\mathbf{T}$ , объявив его корнем вершину. Такое поддерево назовем символьным поддеревом, если оно содержит все вершины исходного дерева $\mathbf{T}$ , достижимые из вершины $Q$ . Ясно, что высота любого максимального поддерева больше нуля и меньше высоты дерева $\mathbf{T}$ . Для помеченного дерева $\mathbf{T}$ нетрудно проверить справедливость следующей теоремы.

Теорема 8.1. Крона любого максимального поддерева помеченного дерева есть подцепочка кроны всего дерева.

Замечание 8.3. Сформулированное утверждение достаточно прозрачно и означает, что если в помеченном дереве $\mathbf{T}$ фиксировать произвольно внутреннюю вершину $Q$ и рассмотреть крону максимального поддерева с корнем $Q$ , то все листья кроны этого поддерева, расположенные между самым левым $(L)$ и самым правым $(L')$ листьями, достижимыми из $Q$ , также достижимы из $Q$ (рис. 8.14).

Применяя теорему 8.1 к деревьям выводов в КС-грамматиках, получим следующий результат.

Дерево вывода цепочки bAAa из нетерминала A в грамматике

Следствие 8.1. Если в дереве вывода некоторой цепочки $\alpha$ из нетерминала $A$ фиксировать произвольно внутреннюю вершину, помеченную нетерминалом $B$ , то максимальное поддерево с корнем в фиксированной вершине (с меткой $B$ ) является деревом вывода некоторой подцепочки $\beta$ цепочки $\alpha$ из нетерминала $B$ , т.е. существуют такие цепочки $\gamma_1$ и $\gamma_2$ , что $\alpha=\gamma_1\beta\gamma_2$ и $A\vdash^{\ast}\gamma_1B\gamma_2\vdash^{\ast}\gamma_1\beta\gamma_2$ (рис. 8.15).

Так, для дерева вывода цепочки $bAAa$ из нетерминала $A$ в грамматике $G_0$ из примера 8.1 (рис. 8.16), фиксируя максимальное поддерево с корневой вершиной $C$ С (вторая вершина слева на первом уровне, выделена полужирным шрифтом), получим $\gamma_1=b,~\beta=AA,~ \gamma_2=a$ , Соответствующее этому максимальному поддереву разбиение вывода на два фрагмента, может быть, например, таким: $A\vdash BB\vdash CCB\vdash bCB\vdash bCa$ (первый фрагмент) и $C\vdash AA$ (второй фрагмент).

Дерево вывода цепочки bAAa из нетерминала A в грамматике 2

Описанная в следствии 8.1 "декомпозиция" дерева вывода и соответственно вывода, по которому построено это дерево, может быть интерпретирована так: выводя цепочку $\alpha$ из нетерминала $A$ , мы, получив на некотором шаге цепочку, содержащую выделенное вхождение нетерминала $B$ , "замораживаем" этот нетерминал и продолжаем замены нетерминалов слева и справа от $B$ , выводя начало (подцепочку $\gamma_1$ ) и конец (подцепочку $\gamma_2$ ) цепочки $\alpha$ . После этого мы "размораживаем" нетерминал $B$ и "довыводим" из него середину цепочки $\alpha$ — подцепочку $\beta$ .

Однозначности КС-грамматики

Понятие дерева вывода связано с понятием однозначности КС-грамматики.

Определение 8.1. КС-грамматику называют однозначной, если каждая цепочка порождаемого ею языка имеет единственное дерево вывода.

Поскольку по дереву вывода цепочки $\alpha$ из нетерминала $A$ однозначно строится как левый, так и правый вывод данной цепочки, то определение 8.1 можно сформулировать иначе: КС-грамматика однозначна, если каждая цепочка порождаемого ею языка имеет единственный левый и единственный правый вывод.

Рассмотрим один хрестоматийный пример неоднозначной грамматики.

Пример 8.3. Зададим грамматику $GE$ следующим образом:

$GE= \bigl(\{a,b,\mathbf{if},\mathbf{then},\mathbf{else}\}, \{S\},S, S\to\mathbf{if}~b~ \mathbf{then}~ S~\mathbf{else}~S\mid \mathbf{if}~b~\mathbf{then}~S\mid a\bigr).$

Эта грамматика описывает "абстрактный синтаксис" операторов условного перехода в некотором "паскалеобразном" языке программирования. Термин "абстрактный синтаксис" в данном случае означает, что мы отвлекаемся от структуры как операторов языка, так и логических условий.

Терминальный символ $a$ означает произвольный оператор (или последовательность операторов), а терминальный символ $b$ — произвольное логическое условие. Кроме того, терминалами грамматики являются также лексемы $\mathbf{if},\,\mathbf{then}$ и $\mathbf{else}$ , формирующие "скелет" любого оператора условного перехода.

Определенная таким образом грамматика неоднозначна, что усматривается из такого примера: цепочка $\mathbf{if}~b~ \mathbf{then~if}~b~ \mathbf{then}~a~ \mathbf{else}~a$ имеет два дерева вывода (рис. 8.17 и 8.18).

Два дерева вывода неоднозначной грамматики

Заметим (неформально), что наличие нескольких деревьев вывода одной и той же цепочки имеет отношение к семантике рассматриваемого языка. В данном конкретном примере понятно, что каждому дереву вывода приведенной выше цепочки отвечает свое смысловое прочтение этой цепочки: в первом случае $\mathbf{else}$ мы относим к первому $\mathbf{then}$ , а во втором — ко второму. В итоге получаем две совершенно разные интерпретации оператора условного перехода. Данный пример неоднозначности известен поэтому под названием "кочующее $\mathbf{else}$ ".

Исходную грамматику, однако, можно "исправить", построив эквивалентную ей однозначную грамматику:

$\begin{aligned}GE_1= \big(& \{a,b, \mathbf{if},\mathbf{then},\mathbf{else}\}, \{S_1,S_2\}, S_1,\\ &S_1\to \mathbf{if}~b~ \mathbf{then}~S_2~\mathbf{else}~ S_1\mid \mathbf{if}~b~ \mathbf{then}~ S_1\mid a,\\ &S_2\to\mathbf{if}~b~\mathbf{then}~S_2~ \mathbf{else}~S_2\mid a\big). \end{aligned}$

В общем случае алгоритма преобразования произвольной неоднозначной КС-грамматики к эквивалентной однозначной не существует.

Пример неоднозначности в естественном языке

Рассмотрим в заключение интересный пример неоднозначности в естественном языке (точнее, в художественном тексте). В известном стихотворении А.С. Пушкина "К вельможе", адресованном князю Юсупову, владельцу Архангельского, есть такая строка:

Посланник молодой увенчанной жены...

(Речь идет о том, что князь был послан Екатериной Великой к Вольтеру, великому французскому философу и писателю, состоявшему с Екатериной в переписке.)

Процитированную строчку можно прочитать двояко:

1) посланник (молодой увенчанной жены),
2) (посланник молодой) увенчанной жены,

т.е. в первом случае эпитет "молодой" отнесен к "жене", а во втором — к "посланнику". Чисто синтаксически эта коллизия неразрешима, но внеязыковый контекст данной фразы, учитывающий совершенно определенные биографические обстоятельства персонажей, позволяет с высокой долей вероятности предположить, что правильным будет второе прочтение.

В то же время следующую анекдотическую фразу нельзя рассматривать как пример неоднозначности, ибо она не соответствует грамматическим нормам русского литературного языка:

Сдавайте мусор дворнику, который накопился.

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

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

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

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

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