Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Представления контекстно-свободных языков посредством гомоморфизмов
Теорема 11.3.1. Рассмотрим алфавит и язык , порождаемый контекстно-свободной грамматикой G0: Произвольный язык является контекстно-свободным тогда и только тогда, когда существует такой гомоморфизм , что L = h-1(L0) или . Доказательство. Достаточность следует из теоремы 11.2.4. Приведем теперь идею доказательства необходимости (полное доказательство можно найти в [Сал, с. 103-109]). Пусть дан произвольный контекстно-свободный язык L. Согласно теореме 8.4.6 язык порождается некоторой контекстно-свободной грамматикой , в которой каждое правило имеет один из следующих трех видов: , , , где . Определим вспомогательную функцию , ставящую в соответствие каждому символу из конечный язык над алфавитом следующим образом: Искомый гомоморфизм h определяется следующим образом: если положим Пример 11.3.2. Пусть . Рассмотрим язык L, порождаемый грамматикой Тогда L = h-1(L0), где гомоморфизм h задан равенствами h(d) = cb1b2b1a1a2a2a1a1a2a1c,h(f) = cb1b2b1cb1b2b2b1a1a2a2a2a1cb1b2b2b1a1a2a2a2a1a1a2a2a1c,h(g) = cb1b2b2b2b1c.Рассмотрим, например, слово . Проверим, что слово h(dffg) выводится в грамматике G0 из теоремы 11.3.1. Очевидно, что . С помощью последних пяти правил грамматики G0 можно вывести, что Осталось найти такие шесть выводимых из C слов , что Подходят слова w1 = c,w2 = c,w3 = cb1b2b2b1a1a2a2a2a1cb1b2b2b1a1a2a2a2a1a1a2a2a1c,w4 = cb1b2b1c,w5 = cb1b2b2b1a1a2a2a2a1a1a2a2a1c,w6 = c.Теорема 11.3.3 (Теорема Хомского-Шютценберже). Язык является контекстно-свободным тогда и только тогда, когда существуют такие натуральное число n, автоматный язык L1 над алфавитом и гомоморфизм , что , где - язык Дика над 2n буквами. Доказательство можно найти в [Лал, с. 331-333]. Упражнение 11.3.4. Рассмотрим язык L1, порождаемый грамматикой и язык L2, порождаемый грамматикой Найти такой гомоморфизм , что К сожалению, теорема о детерминизации не переносится с конечных автоматов на автоматы с магазинной памятью. Возникает важный для практических приложений класс языков, распознаваемых детерминированными автоматами с магазинной памятью (то есть такими автоматами с магазинной памятью, которые ни в какой конфигурации не могут выбирать между несколькими очередными тактами). Точные определения этого класса автоматов и соответствующего класса языков даны в разделе 12.1. Чтобы получить полезный и естественный с точки зрения практики класс, нужно добавить в конец каждого слова специальный символ, называемый маркером конца слова. Языки из выделенного таким образом класса называются детерминированными контекстно-свободными языками. Во втором разделе лекции формулируется ряд свойств этого класса языков. Важность детерминированных контекстно-свободных языков для теоретической информатики обусловлена тем, что для каждого такого языка можно указать быстрый алгоритм, распознающий принадлежность слова этому языку.
|
||||
Последнее изменение этой страницы: 2021-04-04; просмотров: 64; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 13.59.82.167 (0.006 с.) |