Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Характеризация контекстно-свободных языков
Теорема 10.2.1. Если язык L является контекстно-свободным, то существует МП-автомат, распознающий этот язык. Доказательство. Пусть язык L порождается контекстно-свободной грамматикой , в которой каждое правило имеет вид , где , и (в силу теоремы 8.8.3 такая грамматика существует). Положим , , , и Можно доказать, что тогда и только тогда, когда существует левосторонний вывод (здесь и ). Пример 10.2.2. Пусть . Контекстно-свободная грамматика и МП-автомат , где задают один и тот же язык. Лемма 10.2.3. Каждый МП-автомат эквивалентен некоторому МП-автомату , где |I| = 1, |F| = 1 и каждый переход удовлетворяет требованиям и . Пример 10.2.4. Рассмотрим МП-автомат , где , , , Он эквивалентен МП-автомату , где и Пример 10.2.5. Рассмотрим МП-автомат , где , , , Он эквивалентен МП-автомату , где , и Пример 10.2.6. Рассмотрим МП-автомат , где , , , Он эквивалентен МП-автомату , где , , , , Теорема 10.2.7. Если язык L распознается некоторым МП-автоматом, то L является контекстно-свободным. Доказательство. Пусть язык L распознается МП-автоматом . Без ограничения общности можно считать, что , и каждый переход удовлетворяет требованию . Построим искомую контекстно-свободную грамматику , положив , и Можно доказать, что тогда и только тогда, когда (здесь ). Пример 10.2.8. МП-автомат , где , , и контекстно-свободная грамматика задают один и тот же язык. Здесь S, T и U соответствуют символам A1,2, A1,1 и A2,2 из доказательства теоремы 10.2.7. Упражнение 10.2.9. Найти МП-автомат, распознающий язык, порождаемый грамматикой Упражнение 10.2.10. Найти контекстно-свободную грамматику, порождающую язык Упражнение 10.2.10. Найти контекстно-свободную грамматику, порождающую язык Упражнение 10.2.10. Найти контекстно-свободную грамматику, порождающую язык 10.3*. Автоматы с магазинной памятью с однобуквенными переходами Теорема 10.3.1. Каждый МП-автомат эквивалентен некоторому МП-автомату , где |Q| = 2 и каждый переход удовлетворяет требованиям |x| = 1, и . Доказательство. Пусть исходным МП-автоматом распознается контекстно-свободный язык . Согласно теореме 8.4.6 язык порождается некоторой контекстно-свободной грамматикой , в которой каждое правило имеет вид , где , , и . Аналогично тому, как было сделано при доказательстве теоремы 10.2.1, положим , Q = {1,2}, I = {1},
Теорема 10.3.2. Каждый МП-автомат эквивалентен некоторому МП-автомату , в котором каждый переход удовлетворяет требованиям |x| = 1, и . Доказательство. Пусть исходным МП-автоматом распознается контекстно-вободный язык . Согласно теореме 8.4.6 язык порождается некоторой контекстно-вободной грамматикой , в которой каждое правило имеет один из следующих трех видов: , , , где , , , . Легко добиться того, чтобы в правилах грамматики G вспомогательные символы в правой части (то есть символы B и C) были отличны от начального символа S. Положим , где . Далее, положим , Упражнение 10.3.3. Найти для языка, порождаемого грамматикой МП-автомат, в котором каждый переход удовлетворяет требованиям |x| = 1, и . Упражнение 10.3.4. Найти для языка, порождаемого грамматикой МП-автомат, в котором каждый переход удовлетворяет требованиям , и . В этой лекции излагаются те свойства контекстно-свободных языков, которые удобно доказывать с привлечением автоматов с магазинной памятью. В первых двух разделах приводятся некоторые свойства замкнутости класса контекстно-свободных языков (замкнутость относительно деления, взятия гомоморфного образа и полного гомоморфного прообраза). В конце лекции формулируются два критерия контекстной свободности, интересных в основном с теоретической точки зрения. 11.1*. Деление контекстно-свободных языков Теорема 11.1.1. Пусть L1 - контекстно-свободный язык над алфавитом и L2 - автоматный язык над алфавитом . Тогда язык является контекстно-свободным. Доказательство. Пусть - МП-автомат, распознающий язык L1. Без ограничения общности можно считать, что для каждого перехода выполняется неравенство . Пусть - конечный автомат, распознающий язык L2. Без ограничения общности можно считать, что и для каждого перехода выполняется равенство |x| = 1. Тогда язык распознается МП-автоматом , где , I = I1, и Пример 11.1.2. Пусть , язык L1 распознается МП-автоматом и язык L2 распознается конечным автоматом Следуя доказательству теоремы 11.1.1, получаем, что язык распознается МП-автоматом, изображенным ниже. Пример 11.1.3. Пусть , и . Тогда
Пример 11.1.4. Пусть , и . Тогда Замечание 11.1.5. Пусть и . Язык является контекстно-свободным тогда и только тогда, когда язык L является контекстно-свободным. Упражнение 11.1.6. Существует ли такой контекстно-свободный язык , что язык Subw не является контекстно-свободным? Упражнение 11.1.7. Существует ли такой контекстно-свободный язык L над алфавитом {a,b}, что язык не является контекстно-свободным? Упражнение 11.1.8. Существует ли такой контекстно-свободный язык L над алфавитом {a,b}, что язык
|
||||||
Последнее изменение этой страницы: 2021-04-04; просмотров: 62; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 13.59.124.247 (0.021 с.) |