Викиконспекты - Вклад участника [ru]

Участник:SkudarnovYaroslav/Теормин к зачёту по сетям

2015-03-20T20:01:16Z

91.215.121.216: /* Тест 2 */

= Тест 1 =
== Дайте определение компьютерной сети ==
Компьютерная сеть — совокупность компьютеров, объединённых с помощью телекоммуникаций (т. — связь при помощи электронных устройств) для совместного использования данных/ресурсов. Распределённая система — совокупность объединённых компьютеров (аналогично тому, что выше), посредством специального ПО предоставляющих пользователю интерфейс единой системы.

== Какие области технического прогресса породили компьютерные сети? ==
Коммуникации и компьютерные технологии.

== Приведите классификации компьютерных сетей ==
а) По размерам (территориальному признаку функционирования): Desk Area Network (рабочая станция; обмен данными организован на основе ATM ({{TODO|t=???}}), Personal Area Network (сеть устройств пользователя), Local Area Network (соединяет устройства в помещениях — домах, школах и т.д.), Metropolitan Area Network (соединяет устройства в одном городе), Wide Area Network (охватывает большие территории, связывает более маленькие сети, ниже скорость), Internet ({{TODO|t=крупнейшая WAN?}})

б) По скорости передачи данных: низкоскоростные — до 10 Мбит/с, среднескоростные — до 100 Мбит/c, высокоскоростные — свыше 100 Мбит/с.

в) По типу среды передачи данных: проводные, беспроводные.

г) По типу абонентов: стационарные/мобильные.

д) По правовой принадлежности: частные, государственные, общественные ({{TODO|t=по идее, последнее должно относиться либо к первому, либо ко второму}}).

е) По типу взаимодействия компьютеров: одноранговые, иерархические.

ж) По типу предоставляемых сервисов: односервисные, мультисервисные.

== Приведите варианты топологий компьютерных сетей ==
Шина, кольцо, звезда, ячеистая.
Примеры:
* Шина {{---}} 10BASE5, 10BASE2
* Кольцо {{---}} FDDI Ring
* Звезда {{---}} что-то про Ethernet Hub
* Ячеистая {{---}} Netsukuku

== Сформулируйте обобщённую задачу коммутации ==
а) Определение потоков, для которых требуется прокладка маршрута. б) Маршрутизация (определение маршрута). в) Продвижение потоков (распознавание потоков и локальная коммутация на транзитных узлах. устройство, коммутирующее интерфейсы — коммутатор). г) Мультиплексирование (разделение агрегированного потока на составляющие) и демультиплексирование (наоборот, образование из отдельных агрегированный).

== В чем отличия канальной и пакетной коммутации? ==
Пакеты поступают в сеть без резервирования линии связи. Маршрут следования хранится на промежуточных узлах и формируется вручную/автоматически (в случае с каналами он становится известен сразу после создания составного канала). Доставка пакетов в правильном порядке без искажений не гарантируется. У пакетных коммутаторов есть буферная память для временного хранения пакетов (промежуточное хранение).

== Что такое эталонная модель OSI? ==
Модель стека сетевых протоколов, определяющая, что должен делать каждый уровень, разрабатывалась в семидесятых-восьмидесятых годах.

== Что такое стэк протоколов? ==
Иерархически организованный набор сетевых протоколов, достаточный для организации взаимодействия узлов в сети, примеры — TCP/IP, IPX/SPX.

== Перечислите уровни модели OSI и стека TCP/IP ==
OSI — Семь уровней (в скобках название единицы обмена):
* прикладной (APDU)
* у. представления (PPDU)
* сеансовый (SPDU)
* транспортный (TPDU)
* сетевой (пакет)
* канальный (кадр)
* физический (бит).
TCP/IP:
* прикладной (HTTP, FTP, DNS)
* транспортный (TCP, UDP)
* сетевой (IP)
* канальный (Ethernet/IEEE 802.11 Wireless Internet/etc).

== Сформулируйте теорему Шеннона ==
Если аналоговый сигнал имеет конечный (ограниченный по ширине) спектр, то он может быть восстановлен однозначно и без потерь по своим отсчётам, взятым с частотой, строго большей удвоенной верхней частоты.

== Что такое модуляция и манипуляция? ==
Модуляция — представление дискретных сигналов в среде передачи данных в виде синусоидальных волн. Манипуляция — то же самое, но при дискретных уровнях модулирующего сигнала.

== Чем модуляция отличается от физического кодирования сигнала? ==
Физическое кодирование не изменяет структуры сигнала, в отличие от модуляции.

== Что такое самосинхронизирующийся код? ==
С. код — код, который можно декодировать без отдельного тактового сигнала/другого источника синхронизации. Примеры: применение синусоид в качестве результирующего сигнала; использование избыточного кодирования; манчестерский код (логическая единица — положительный переход в середине символа, ноль — отрицательный).

== Что такое витая пара? ==
По стандарту — четыре пары медных проводов, обвитых вокруг друг друга под одной оболочкой.

== Что такое кадр? ==
Единица передачи данных на уровне передачи данных (канальном уровне)? В Ethernet состоит из хедера (мак исходного адреса, назначения и два байте EtherType), полезная нагрузка, CRC.

== Какие есть варианты кадрирования? ==
* подсчёт количества символов;
* использование сигнальных байтов с символьным заполнением;
* использование стартовых и стоповых бит с битовым заполнением;
* использование запрещённых сигналов физического уровня.

== Какие бывают варианты протоколов уровня передачи данных по их отношению к ошибкам в кадрах? ==
Повторно запросить кадр/восстановить исходную информацию.

== Что такое расстояние кода в смысле Хэмминга? ==
Минимальное количество битов, которыми различаются два кодовых слова.

== Зачем нужно избыточное кодирование? ==
Для восстановления информации/обнаружения ошибок.

== Как можно верифицировать протоколы канального уровня? ==
Модель конечных автоматов (анализ состояний протокольной машины — отправителя/получателя), сети Петри (похоже).

== Что такое "коллизия", в каких системах и на каком уровне возможно её возникновение? ==
Наложение двух и более кадров от станций, пытающихся передать кадр в один и тот же момент времени в среде передачи коллективного доступа. В системах с широковещательным каналом, на подуровне, управляющим доступом в общей среде, являющимся нижней частью уровня передачи данных.

== Чем "коллизия" отличается от "внешней помехи"? ==
Коллизия — передаче кадра мешает передача другого; внешняя помеха — передаче кадра мешают проблемы со средой.

== Что такое CSMA/CD? ==
CSMA — Carrier Sense Multiple Access — множественный доступ с контролем несущей. Слушаем канал, если занят, ждём случайное время. Если свободен — передаём, если коллизия — ждём случайное время. Настойчивость p — передаём с вероятностью p. Детектируем коллизию — шлём jam signal, сообщая о ней другим станциям, потом ждём случайное время… Полудуплекс из-за того, что слушаем канал.

== Зачем нужен алгоритм двоичного экспоненциального отката и как его применение сказывается на разрешении коллизий? ==
После c коллизий выбираем рандомное число от 0 до 2^c-1, ждём это число. Для того, чтобы увеличить время ожидания при большом количестве коллизий и, как следствие, уменьшить их вероятность при повторной передаче.

== Какие вы знаете методы неконкуретного доступа к общей среде? ==
Протокол битовой карты (период конкуренции — N, если i-ая станция желает передавать, она шлёт на i-ом интервале бит), двоичный обратный отсчёт — станции передают по очереди биты своего номера, начиная со самого старшего. Побеждает та, у которой наибольший номер.

== Какое физическое кодирование используется в 10Base-T Ethernet? ==
Манчестерское кодирование.

== Какое кодирование используется в 100Base-T Ethernet? ==
4b5b (четыре бита кодируются пятью, в целях в т.ч. синхронизации), MLT-3 (Multi Level Transition — три уровня, -U, 0, +U).

== Чем отличается стандарт 100Base-T4 от 100Base-TX? ==
T4 использует витую пару категории 3, У T4 нет полного дуплекса.

== Чем отличается концентратор от коммутатора? ==
Концентратор пересылает данные всем устройствам, коммутатор — только тем, кому предназначаются эти данные.

== Что такое и зачем нужны сетевые мосты? ==
Устройства, работающие на уровне передачи данных, анализирующие адреса, содержащиеся в кадрах этого уровня и соответствующим образом маршрутизирующие. Нужны для:
* соединения различных удалённых в пространстве сетей.
* для того, чтобы связывать различные типы сетей.

== Что такое и зачем нужен алгоритм остовного дерева (STP)? ==
В сети выбирается один корневой мост (англ. Root Bridge). Далее каждый, отличный от корневого, мост просчитывает кратчайший путь к корневому. Соответствующий порт называется корневым портом (англ. Root Port). У любого некорневого коммутатора может быть только один корневой порт. После этого для каждого сегмента сети, к которому присоединён более чем один порт моста, просчитывается кратчайший путь к корневому порту. Мост, через который проходит этот путь, становится назначенным для этой сети (англ. Designated Bridge), а соответствующий порт — назначенным портом (англ. Designated port). Далее во всех сегментах, с которыми соединены более одного порта моста, все мосты блокируют все порты, не являющиеся корневыми и назначенными. В итоге получается древовидная структура (математический граф) с вершиной в виде корневого коммутатор.

Основной задачей STP является устранение петель в топологии произвольной сети Ethernet, в которой есть один или более сетевых мостов, связанных избыточными соединениями. STP решает эту задачу, автоматически блокируя соединения, которые в данный момент для полной связности коммутаторов являются избыточными.

== Зачем нужен уровень MAC и какие задачи он решает? ==
IEEE разделяет канальный уровень на два подуровня: media access control (MAC) и logical link control (LLC) (управления логической связью). Таким образом, MAC выступает в качестве интерфейса между подуровнем LLC и физическим (первым) уровнем. MAC обеспечивает адресацию и механизмы управления доступом к каналам, что позволяет нескольким терминалам или точкам доступа общаться между собой в многоточечной сети. В широковещательных сетях (таких, как сети на основе Ethernet) MAC-адрес позволяет уникально идентифицировать каждый узел сети и доставлять данные только этому узлу.

== Зачем нужен уровень LLC и какие сервисы он предоставляет? ==
LLC осуществляет управление передачей данных, обеспечивает проверку и правильность передачи информации по соединению. {{TODO|t=тут, наверное, побольше надо написать}}

== Что такое MAC-адрес в понимании Ethernet сети и как назначаются MAC адреса устройствам? ==
Первые 3 октета (в порядке их передачи по сети; старшие 3 октета, если рассматривать их в традиционной бит-реверсной шестнадцатеричной записи MAC-адресов) содержат 24-битный уникальный идентификатор организации (OUI), или (Код MFG — Manufacturing, производителя), который производитель получает в IEEE. При этом используются только младшие 22 разряда (бита), 2 старшие имеют специальное назначение: первый бит указывает, для одиночного (0) или группового (1) адресата предназначен кадр, следующий бит указывает, является ли MAC-адрес глобально (0) или локально (1) администрируемым.

Следующие три октета выбираются изготовителем для каждого экземпляра устройства. За исключением сетей системной сетевой архитектуры SNA.

Таким образом, глобально администрируемый MAC-адрес устройства глобально уникален и обычно «зашит» в аппаратуру.

Администратор сети имеет возможность, вместо использования «зашитого», назначить устройству MAC-адрес по своему усмотрению. Такой локально администрируемый MAC-адрес выбирается произвольно.

== Какие вы знаете методы разделения широковещательного канала? ==
DCF — Distributed Coordination Function. CSMA с избежанием коллизий (jam signal), никакого QoS, возможны инверсии приоритета (всё плохо).

PCF — Point Coordination Function. Работает только, если сеть организована точкой доступа; точка доступа посылает каждые 0.1 секунды специальный сигнал. Между сигналами возможны два периода; в одном она ведёт себя как с DCF, в другом — шлёт станциям пакеты, сообщающие о праве посылать пакеты (AP тут — координатор).

В 802.11e ввели несколько новых функций координации, с QoS. Одна из них (Hybrid Coordination Fuinction) — по сути PCF, но с QoS.

== Что такое шумоподобный сигнал? ==
Cигнал, содержащий много гармонических (синусоидальных) составляющих в выбранной полосе частот. Шумом называют неупорядоченные случайные сложные колебания со сплошным относительно широким частотным спектром. Отсюда происходит название рассматриваемого сигнала. Использование шумообразных сигналов позволяет значительно уменьшить мощность их источников. Она составляет менее 1 Вт. Кроме этого, применение этих сигналов обеспечивает повышение помехоустройчивости передачи данных.

== Опишите проблемы "скрытой" и "засвеченной" станций в беспроводных сетях. ==
Описано вот тут: http://book.itep.ru/4/41/i802_418.htm

== Что такое последовательно Баркера и какое её основное свойство? ==
Числовая последовательность <tex> a_1 , a_2 , \ldots a_N </tex>, где каждый элемент равен +1 или -1, причём <tex>\forall v : 1 \le v < N</tex> выполняется <tex>\left\vert \sum\limits_{j=1}^{N-v} a_j a_{j+v} \right\vert \le 1</tex>. Последовательности Баркера имеют минимальный уровень боковых лепестков автокорреляционной функции.

== Что такое QPSK? ==
Фазовая модуляция, при которой возможных значений фазового сдвига 4.

== Что такое СCK коды и когда они применяются вместо кода Баркера? ==
CCK — Complementary Code Keying. Комплементарными принято называть такие пары последовательностей, для которых сумма автокорреляционных функций последовательностей для любого циклического сдвига, отличного от нуля, всегда равна нулю. Применяются {{TODO|t=WTF}}

== Что такое OFDM? ==
OFDM — Orthogonal Frequency Division Multiplexing — мультиплексирование разделением на ортогональные несущие. При демультиплексировании в принимающих устройствах используется обратное быстрое преобразование Фурье.

== Что такое IEEE 802.11? ==
Набор стандартов связи для коммуникации в беспроводной локальной сетевой зоне частотных диапазонов 0,9; 2,4; 3,6 и 5 ГГц, описывающих передачу данных на физическом уровне и MAC-уровне.

== Какие есть методы расширения спектра сигнала? ==
{{TODO|t=допилить, что ли}}

== Что такое PCF и DCF режимы в 802.11? Могут ли одновременно работать станции по PCF и DCF? ==
По идее, это аналогично вопросу 35. Могут ли одновременно — да, кто мешает? В какой-то из периодов PCF, насколько я помню, вполне может использоваться DCF.

== Что описывают стандарты IEEE 802.16 и 802.16e? ==
WMAN (Wireless MAN) — беспроводные сети масштаба города. Стандарты описывают их работу на физическом уровне, LLC и MAC.

== Что такое и зачем нужен протокол скользящего окна? ==
Он работает следующим образом: посылатель посылает какое-то фиксированное количество байт (размер окна), если информация пришла вовремя и без искажений, то получатель посылает отправителю подтверждение — квитанцию. Нужен — для гарантии передачи данных.

== Что такое ACK в протоколах передачи данных? Что такое NAK и когда выгодно его использовать? ==
ACK — сигнал, означающий подтверждение принятия данных, NAK говорит о том, что данные не пришли. NAK выгодно использовать в случае со стабильной связью (при которой почти не понадобится его посылать).

== Что такое многомодовое и что такое одномодовое оптоволокно? ==
Одномодовое оптоволокно — волокно, которое может передавать только один луч света одновременно. Многоводовое — соответственно, несколько.

== Как достигается одномодовый режим работы оптоволокна? ==
Волокно делают настолько тонким, что диаметр доходит до нескольких длин волн света, в результате чего волокно действует подобно волноводу. {{TODO|t=уточнить, если я правильно понял, в вопросе говорится про то, что многомодовое волокно может работать в одномодовом режиме}}

== Что такое "окна прозрачности в оптоволокне"? ==
Диапазон длин волн оптического излучения, в котором имеет место меньшее, по сравнению с другими диапазонами, затухание излучения в волокне.

== Что такое технологии WDM? ==
WDM (Wavelength-division multiplexing) — мультиплексирование с разделением по длине волны — технология, позволяющая одновременно передавать несколько информационных каналов по одному оптическому волокну на разных несущих частотах. WDM позволяет существенно увеличить пропускную способность канала, причем она позволяет использовать уже проложенные волоконно-оптические линии.

== В чём принцип технологий PON? ==
PON (Passive Optical Network) — технология, основанная на древовидной волоконно-кабельной архитектуре с пассивными оптическими разветвителями на узлах, представляет экономичный способ обеспечить широкополосную передачу информации. При этом архитектура PON обладает необходимой эффективностью наращивания узлов сети и пропускной способности, в зависимости от настоящих и будущих потребностей абонентов. Основная идея: использование всего одного приёмопередающего модуля в OLT (optical line terminal) для передачи информации множеству абонентских устройств ONT (optical network terminal) и приёма информации от них. Все узлы-абоненты ведут передачу на одной и той же длине волны, поэтому для разделения сигналов используется концепция множественного доступа с временным разделением.

== Что такое эрбиевый усилитель сигнала? Зачем он нужен? ==
Волоконно-оптический усилитель на оптическом волокне, легированном ионами эрбия. Применяется в волоконно-оптических линиях передачи для восстановления уровня оптического сигнала. Преимуществом эрбиевых усилителей является отсутствие преобразования в электрический сигнал, возможность одновременного усиления сигналов с разными длинами волн (что обуславливает возможность усиления спектрально-мультиплексированного сигнала), практически точное соответствие рабочего диапазона эрбиевых усилителей области минимальных оптических потерь световодов на основе кварцевого стекла, сравнительно низкий уровень шума и простота включения в волоконно-оптическую систему.

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

= Тест 2 =

== Что такое элементарный и составной каналы в сетях с канальной коммутацией? ==
Элементарный канал — базовая техническая характеристика сети с коммутацией каналов, представляющая собой некоторое фиксированное в пределах данного типа сетей значение пропускной способности. Любая линия в сети с коммутацией каналов имеет пропускную способность, кратную элементарному каналу, принятому для данного типа сети.

== Перечислите примеры протоколов стека TCP/IP по уровням ==
* прикладной (binkp, FTP, Finger, DNS, Gnutella, Gopher, HTTP, HTTPS, IMAP, IRC, XMPP, LDAP, NTP, NNTP, POP3, RDP, SMB, SSH, SMTP, Telnet, SNMP, SIP, DMX-512)
* транспортный (SPX, XOT, BGP, ISODE, DVMRP, TCP, UDP, SCTP, RDP/RUDP, RTCP)
* сетевой (ICMP, IPv4, IPv6, IPX, ARP)
* канальный (Ethernet/IEEE 802.11, Wireless Internet, Token ring, FDDI, HDLC, GVRP, PPP, PPTP, L2TP, ATM, xDSL).

== Какая бывает модуляция? ==
Фазовая (в зависимости от входного сигнала выходной сдвигается на какую-то фазу), амплитудная (в зависимости от входного сигнала изменяется амплитуда выходного), частотная (в зависимости от входного сигнала изменяется частота выходного).

== Приведите примеры вариантов физического кодирования ==
===2 уровня===
* NRZ (Non Return Zero) — простейший код, 1 — есть ток, 0 — нет;
* NRZI (Non Return Zero Inverted) — смена сигнала происходит при передаче единицы, передача нуля не приводит к изменению сигнала;
* RZ (Return to Zero) — 0 — положительное напряжение, 1 — отрицательное, в середине сигнала происходит переход в отсутствие напряжение;
* Манчестерский код — (логическая единица — положительный переход в середине символа, ноль — отрицательный).
===3 уровня===
* Биполярный код AMI - биты 0 представляются нулевым напряжением (0 В), биты 1 представляются поочерёдно значениями -U или +U (В);
* MLT-3 Multi Level Transmission — 3 (многоуровневая передача) — метод кодирования, использующий три уровня сигнала. Метод основывается на циклическом переключении уровней -U, 0, +U. Единице соответствует переход с одного уровня сигнала на следующий. Так же как и в методе NRZI при передаче «нуля» сигнал не меняется.
===4 уровня===
Потенциальный код 2B1Q передает пару бит за один битовый интервал. Каждой возможной паре в соответствие ставится свой уровень из четырех возможных уровней потенциала: "00" = <tex>-2.5</tex>, "01" = <tex>−0.833</tex>, "11" = <tex>+0.833</tex>, "10" = <tex>+2.5</tex>.
== Что такое кадр? ==
Единица передачи на канальном уровне

== Какие есть варианты кадрирования? ==
* подсчёт количества символов;
* использование сигнальных байтов с символьным заполнением;
* использование стартовых и стоповых бит с битовым заполнением;
* использование запрещённых сигналов физического уровня.

== Что такое алгоритм двоичного экспоненциального отката? ==
После <tex>c</tex> коллизий выбираем рандомное число от <tex>0</tex> до <tex>2^c - 1</tex>, ждём это число. Для того, чтобы увеличить время ожидания при большом количестве коллизий и, как следствие, уменьшить их вероятность при повторной передаче.

== Нарисуйте схему CSMA/CD ==
схему? лолшто?
CSMA — Carrier Sense Multiple Access — множественный доступ с контролем несущей. Слушаем канал, если занят, ждём случайное время. Если свободен — передаём, если коллизия — ждём случайное время. Настойчивость <tex>p</tex> — передаём с вероятностью <tex>p</tex>. Детектируем коллизию — шлём jam signal, сообщая о ней другим станциям, потом ждём случайное время… Полудуплекс из-за того, что слушаем канал.

== Какое кодирование используется в 100 мегабитном Ethernet? ==
В 100BASE-T4 используется 8B6T (8 двоичных символов кодируются 6 тернарными), в 100BASE-TX — 4B5B (4 двоичных символа кодируются 5 двоичными, на более нижнем уровне используется NRZI, поэтому один «лишний» символ используется для синхронизации)

== Что такое протокол скользящего окна? ==
Он работает следующим образом: посылатель посылает какое-то фиксированное количество байт (размер окна), если информация пришла вовремя и без искажений, то получатель посылает отправителю подтверждение — квитанцию. Нужен — для гарантии передачи данных.

== Чем отличается концентратор от коммутатора? ==
Концентратор пересылает данные всем устройствам, коммутатор — только тем, кому предназначаются эти данные.

== Что такое и зачем нужны сетевые мосты? ==
Устройства, работающие на уровне передачи данных, анализирующие адреса, содержащиеся в кадрах этого уровня и соответствующим образом маршрутизирующие. Нужны для:
* соединения различных удалённых в пространстве сетей.
* для того, чтобы связывать различные типы сетей.

== Что такое и зачем нужен алгоритм остовного дерева (STP)? ==
В сети выбирается один корневой мост (англ. Root Bridge). Далее каждый, отличный от корневого, мост просчитывает кратчайший путь к корневому. Соответствующий порт называется корневым портом (англ. Root Port). У любого некорневого коммутатора может быть только один корневой порт. После этого для каждого сегмента сети, к которому присоединён более чем один порт моста, просчитывается кратчайший путь к корневому порту. Мост, через который проходит этот путь, становится назначенным для этой сети (англ. Designated Bridge), а соответствующий порт — назначенным портом (англ. Designated port). Далее во всех сегментах, с которыми соединены более одного порта моста, все мосты блокируют все порты, не являющиеся корневыми и назначенными. В итоге получается древовидная структура (математический граф) с вершиной в виде корневого коммутатор.

Основной задачей STP является устранение петель в топологии произвольной сети Ethernet, в которой есть один или более сетевых мостов, связанных избыточными соединениями. STP решает эту задачу, автоматически блокируя соединения, которые в данный момент для полной связности коммутаторов являются избыточными.

== Какую задачу решает уровень MAC? ==
IEEE разделяет канальный уровень на два подуровня: media access control (MAC) и logical link control (LLC) (управления логической связью). Таким образом, MAC выступает в качестве интерфейса между подуровнем LLC и физическим (первым) уровнем. MAC обеспечивает адресацию и механизмы управления доступом к каналам, что позволяет нескольким терминалам или точкам доступа общаться между собой в многоточечной сети. В широковещательных сетях (таких, как сети на основе Ethernet) MAC-адрес позволяет уникально идентифицировать каждый узел сети и доставлять данные только этому узлу.

== Какие есть варианты разделения широковещательного канала? ==
DCF — Distributed Coordination Function. CSMA с избежанием коллизий (jam signal), никакого QoS, возможны инверсии приоритета (всё плохо).

PCF — Point Coordination Function. Работает только, если сеть организована точкой доступа; точка доступа посылает каждые 0.1 секунды специальный сигнал. Между сигналами возможны два периода; в одном она ведёт себя как с DCF, в другом — шлёт станциям пакеты, сообщающие о праве посылать пакеты (AP тут — координатор).

В 802.11e ввели несколько новых функций координации, с QoS. Одна из них (Hybrid Coordination Fuinction) — по сути PCF, но с QoS.

== Какие сервисы предоставляет подуровень LLC? ==
LLC осуществляет управление передачей данных, обеспечивает проверку и правильность передачи информации по соединению.

== Что такое шумоподобный сигнал? ==
Cигнал, содержащий много гармонических (синусоидальных) составляющих в выбранной полосе частот. Шумом называют неупорядоченные случайные сложные колебания со сплошным относительно широким частотным спектром. Отсюда происходит название рассматриваемого сигнала. Использование шумообразных сигналов позволяет значительно уменьшить мощность их источников. Она составляет менее 1 Вт. Кроме этого, применение этих сигналов обеспечивает повышение помехоустойчивости передачи данных.

== Что такое проблема засвеченной станции и проблема скрытой станции? ==
===проблема скрытой станции===
В случае, когда расстояние между передатчиком и приемником сравнимо с радиусом надежной связи, отличие от традиционных сетей становится значительным. Ведь для радиосетей важна интерференция на входе приемника, а не на выходе передатчика (как в CSMA). Если передачу осуществляет узел А, узел С находится вне его радиуса действия и может решить, что можно начать передачу. Излучение передатчика С может вызвать помехи на входе узла В.
===проблема засвеченной станции===
В случае, когда передачу ведет узел В, узел С может решить, что начало передачи сообщения узлу D не возможно, так как в зоне С детектируется излучение станции В. Таким образом, в радиосетях, прежде чем начать передачу данных надо знать, имеется ли радио активность в зоне приемника-адресата.

== Что такое OFDM? ==
OFDM — Orthogonal Frequency Division Multiplexing — мультиплексирование разделением на ортогональные несущие. При демультиплексировании в принимающих устройствах используется обратное быстрое преобразование Фурье.

== Чем многомодовое оптоволокно отличается от одномодового? ==
Одномодовое оптоволокно — волокно, которое может передавать только один луч света одновременно. Многоводовое — соответственно, несколько.

== Что такое CWDM? ==
CWDM (Coarse WDM) — «грубое» WDM с разносом каналов более 2500 ГГц, позволяет мультиплексировать не более 18 каналов.

== В чём отличительная особенность технологии PON? ==
PON (Passive Optical Network) — технология, основанная на древовидной волоконно-кабельной архитектуре с пассивными оптическими разветвителями на узлах, представляет экономичный способ обеспечить широкополосную передачу информации. При этом архитектура PON обладает необходимой эффективностью наращивания узлов сети и пропускной способности, в зависимости от настоящих и будущих потребностей абонентов. Основная идея: использование всего одного приёмопередающего модуля в OLT (optical line terminal) для передачи информации множеству абонентских устройств ONT (optical network terminal) и приёма информации от них. Все узлы-абоненты ведут передачу на одной и той же длине волны, поэтому для разделения сигналов используется концепция множественного доступа с временным разделением.

== Перечислите сервисы сетевого уровня ==

===модели соединения: с установкой соединения и без установки соединения===
Сетевой уровень модели OSI может быть как с установкой соединения, так и без него. Для сравнения — Межсетевой уровень (англ. internet) стека протоколов Модели DoD (Модель TCP/IP) поддерживает только протокол IP, который является протоколом без установки соединения; протоколы с установкой соединения находятся на следующих уровнях этой модели.
===адрес, присвоенный сетевому узлу===
Каждый хост в сети должен иметь уникальный адрес, который определяет, где он находится. Этот адрес обычно назначается из иерархической системы. В Интернете адреса известны как адреса протокола IP.
===продвижение данных===
Так как многие сети разделены на подсети и соединяются с другими сетями широковещательными каналами, сети используют специальные хосты, которые называются шлюзами или роутерами (маршрутизаторами) для доставления пакетов между сетями. Это также используется в интересах мобильных приложений, когда пользователь двигается от одного приложения к другому, в этом случае пакеты (сообщения) должны следовать за ним. В протоколе IPv4 такая идея описана, но практически не применяется. IPv6 содержит более рациональное решение.

== Что такое маршрутизация? ==
Маршрутизация — процесс определения маршрута следования информации в сетях связи.

== Чем маршрутизация при дейтаграммном подходе отличается от маршрутизации в сетях с виртуальными каналами? ==
При дейтаграммном подходе для каждого пакета строится свой маршрут. При маршрутизации с виртуальным каналом все пакеты идут по одному маршруту.

Вроде всё. Мы же дальше не проходили?

Участник:SkudarnovYaroslav/Теормин к зачёту по сетям

2015-03-20T18:34:01Z

91.215.121.216: /* Тест 2 */

= Тест 1 =
== Дайте определение компьютерной сети ==
Компьютерная сеть — совокупность компьютеров, объединённых с помощью телекоммуникаций (т. — связь при помощи электронных устройств) для совместного использования данных/ресурсов. Распределённая система — совокупность объединённых компьютеров (аналогично тому, что выше), посредством специального ПО предоставляющих пользователю интерфейс единой системы.

== Какие области технического прогресса породили компьютерные сети? ==
Коммуникации и компьютерные технологии.

== Приведите классификации компьютерных сетей ==
а) По размерам (территориальному признаку функционирования): Desk Area Network (рабочая станция; обмен данными организован на основе ATM ({{TODO|t=???}}), Personal Area Network (сеть устройств пользователя), Local Area Network (соединяет устройства в помещениях — домах, школах и т.д.), Metropolitan Area Network (соединяет устройства в одном городе), Wide Area Network (охватывает большие территории, связывает более маленькие сети, ниже скорость), Internet ({{TODO|t=крупнейшая WAN?}})

б) По скорости передачи данных: низкоскоростные — до 10 Мбит/с, среднескоростные — до 100 Мбит/c, высокоскоростные — свыше 100 Мбит/с.

в) По типу среды передачи данных: проводные, беспроводные.

г) По типу абонентов: стационарные/мобильные.

д) По правовой принадлежности: частные, государственные, общественные ({{TODO|t=по идее, последнее должно относиться либо к первому, либо ко второму}}).

е) По типу взаимодействия компьютеров: одноранговые, иерархические.

ж) По типу предоставляемых сервисов: односервисные, мультисервисные.

== Приведите варианты топологий компьютерных сетей ==
Шина, кольцо, звезда, ячеистая.
Примеры:
* Шина {{---}} 10BASE5, 10BASE2
* Кольцо {{---}} FDDI Ring
* Звезда {{---}} что-то про Ethernet Hub
* Ячеистая {{---}} Netsukuku

== Сформулируйте обобщённую задачу коммутации ==
а) Определение потоков, для которых требуется прокладка маршрута. б) Маршрутизация (определение маршрута). в) Продвижение потоков (распознавание потоков и локальная коммутация на транзитных узлах. устройство, коммутирующее интерфейсы — коммутатор). г) Мультиплексирование (разделение агрегированного потока на составляющие) и демультиплексирование (наоборот, образование из отдельных агрегированный).

== В чем отличия канальной и пакетной коммутации? ==
Пакеты поступают в сеть без резервирования линии связи. Маршрут следования хранится на промежуточных узлах и формируется вручную/автоматически (в случае с каналами он становится известен сразу после создания составного канала). Доставка пакетов в правильном порядке без искажений не гарантируется. У пакетных коммутаторов есть буферная память для временного хранения пакетов (промежуточное хранение).

== Что такое эталонная модель OSI? ==
Модель стека сетевых протоколов, определяющая, что должен делать каждый уровень, разрабатывалась в семидесятых-восьмидесятых годах.

== Что такое стэк протоколов? ==
Иерархически организованный набор сетевых протоколов, достаточный для организации взаимодействия узлов в сети, примеры — TCP/IP, IPX/SPX.

== Перечислите уровни модели OSI и стека TCP/IP ==
OSI — Семь уровней (в скобках название единицы обмена):
* прикладной (APDU)
* у. представления (PPDU)
* сеансовый (SPDU)
* транспортный (TPDU)
* сетевой (пакет)
* канальный (кадр)
* физический (бит).
TCP/IP:
* прикладной (HTTP, FTP, DNS)
* транспортный (TCP, UDP)
* сетевой (IP)
* канальный (Ethernet/IEEE 802.11 Wireless Internet/etc).

== Сформулируйте теорему Шеннона ==
Если аналоговый сигнал имеет конечный (ограниченный по ширине) спектр, то он может быть восстановлен однозначно и без потерь по своим отсчётам, взятым с частотой, строго большей удвоенной верхней частоты.

== Что такое модуляция и манипуляция? ==
Модуляция — представление дискретных сигналов в среде передачи данных в виде синусоидальных волн. Манипуляция — то же самое, но при дискретных уровнях модулирующего сигнала.

== Чем модуляция отличается от физического кодирования сигнала? ==
Физическое кодирование не изменяет структуры сигнала, в отличие от модуляции.

== Что такое самосинхронизирующийся код? ==
С. код — код, который можно декодировать без отдельного тактового сигнала/другого источника синхронизации. Примеры: применение синусоид в качестве результирующего сигнала; использование избыточного кодирования; манчестерский код (логическая единица — положительный переход в середине символа, ноль — отрицательный).

== Что такое витая пара? ==
По стандарту — четыре пары медных проводов, обвитых вокруг друг друга под одной оболочкой.

== Что такое кадр? ==
Единица передачи данных на уровне передачи данных (канальном уровне)? В Ethernet состоит из хедера (мак исходного адреса, назначения и два байте EtherType), полезная нагрузка, CRC.

== Какие есть варианты кадрирования? ==
* подсчёт количества символов;
* использование сигнальных байтов с символьным заполнением;
* использование стартовых и стоповых бит с битовым заполнением;
* использование запрещённых сигналов физического уровня.

== Какие бывают варианты протоколов уровня передачи данных по их отношению к ошибкам в кадрах? ==
Повторно запросить кадр/восстановить исходную информацию.

== Что такое расстояние кода в смысле Хэмминга? ==
Минимальное количество битов, которыми различаются два кодовых слова.

== Зачем нужно избыточное кодирование? ==
Для восстановления информации/обнаружения ошибок.

== Как можно верифицировать протоколы канального уровня? ==
Модель конечных автоматов (анализ состояний протокольной машины — отправителя/получателя), сети Петри (похоже).

== Что такое "коллизия", в каких системах и на каком уровне возможно её возникновение? ==
Наложение двух и более кадров от станций, пытающихся передать кадр в один и тот же момент времени в среде передачи коллективного доступа. В системах с широковещательным каналом, на подуровне, управляющим доступом в общей среде, являющимся нижней частью уровня передачи данных.

== Чем "коллизия" отличается от "внешней помехи"? ==
Коллизия — передаче кадра мешает передача другого; внешняя помеха — передаче кадра мешают проблемы со средой.

== Что такое CSMA/CD? ==
CSMA — Carrier Sense Multiple Access — множественный доступ с контролем несущей. Слушаем канал, если занят, ждём случайное время. Если свободен — передаём, если коллизия — ждём случайное время. Настойчивость p — передаём с вероятностью p. Детектируем коллизию — шлём jam signal, сообщая о ней другим станциям, потом ждём случайное время… Полудуплекс из-за того, что слушаем канал.

== Зачем нужен алгоритм двоичного экспоненциального отката и как его применение сказывается на разрешении коллизий? ==
После c коллизий выбираем рандомное число от 0 до 2^c-1, ждём это число. Для того, чтобы увеличить время ожидания при большом количестве коллизий и, как следствие, уменьшить их вероятность при повторной передаче.

== Какие вы знаете методы неконкуретного доступа к общей среде? ==
Протокол битовой карты (период конкуренции — N, если i-ая станция желает передавать, она шлёт на i-ом интервале бит), двоичный обратный отсчёт — станции передают по очереди биты своего номера, начиная со самого старшего. Побеждает та, у которой наибольший номер.

== Какое физическое кодирование используется в 10Base-T Ethernet? ==
Манчестерское кодирование.

== Какое кодирование используется в 100Base-T Ethernet? ==
4b5b (четыре бита кодируются пятью, в целях в т.ч. синхронизации), MLT-3 (Multi Level Transition — три уровня, -U, 0, +U).

== Чем отличается стандарт 100Base-T4 от 100Base-TX? ==
T4 использует витую пару категории 3, У T4 нет полного дуплекса.

== Чем отличается концентратор от коммутатора? ==
Концентратор пересылает данные всем устройствам, коммутатор — только тем, кому предназначаются эти данные.

== Что такое и зачем нужны сетевые мосты? ==
Устройства, работающие на уровне передачи данных, анализирующие адреса, содержащиеся в кадрах этого уровня и соответствующим образом маршрутизирующие. Нужны для:
* соединения различных удалённых в пространстве сетей.
* для того, чтобы связывать различные типы сетей.

== Что такое и зачем нужен алгоритм остовного дерева (STP)? ==
В сети выбирается один корневой мост (англ. Root Bridge). Далее каждый, отличный от корневого, мост просчитывает кратчайший путь к корневому. Соответствующий порт называется корневым портом (англ. Root Port). У любого некорневого коммутатора может быть только один корневой порт. После этого для каждого сегмента сети, к которому присоединён более чем один порт моста, просчитывается кратчайший путь к корневому порту. Мост, через который проходит этот путь, становится назначенным для этой сети (англ. Designated Bridge), а соответствующий порт — назначенным портом (англ. Designated port). Далее во всех сегментах, с которыми соединены более одного порта моста, все мосты блокируют все порты, не являющиеся корневыми и назначенными. В итоге получается древовидная структура (математический граф) с вершиной в виде корневого коммутатор.

Основной задачей STP является устранение петель в топологии произвольной сети Ethernet, в которой есть один или более сетевых мостов, связанных избыточными соединениями. STP решает эту задачу, автоматически блокируя соединения, которые в данный момент для полной связности коммутаторов являются избыточными.

== Зачем нужен уровень MAC и какие задачи он решает? ==
IEEE разделяет канальный уровень на два подуровня: media access control (MAC) и logical link control (LLC) (управления логической связью). Таким образом, MAC выступает в качестве интерфейса между подуровнем LLC и физическим (первым) уровнем. MAC обеспечивает адресацию и механизмы управления доступом к каналам, что позволяет нескольким терминалам или точкам доступа общаться между собой в многоточечной сети. В широковещательных сетях (таких, как сети на основе Ethernet) MAC-адрес позволяет уникально идентифицировать каждый узел сети и доставлять данные только этому узлу.

== Зачем нужен уровень LLC и какие сервисы он предоставляет? ==
LLC осуществляет управление передачей данных, обеспечивает проверку и правильность передачи информации по соединению. {{TODO|t=тут, наверное, побольше надо написать}}

== Что такое MAC-адрес в понимании Ethernet сети и как назначаются MAC адреса устройствам? ==
Первые 3 октета (в порядке их передачи по сети; старшие 3 октета, если рассматривать их в традиционной бит-реверсной шестнадцатеричной записи MAC-адресов) содержат 24-битный уникальный идентификатор организации (OUI), или (Код MFG — Manufacturing, производителя), который производитель получает в IEEE. При этом используются только младшие 22 разряда (бита), 2 старшие имеют специальное назначение: первый бит указывает, для одиночного (0) или группового (1) адресата предназначен кадр, следующий бит указывает, является ли MAC-адрес глобально (0) или локально (1) администрируемым.

Следующие три октета выбираются изготовителем для каждого экземпляра устройства. За исключением сетей системной сетевой архитектуры SNA.

Таким образом, глобально администрируемый MAC-адрес устройства глобально уникален и обычно «зашит» в аппаратуру.

Администратор сети имеет возможность, вместо использования «зашитого», назначить устройству MAC-адрес по своему усмотрению. Такой локально администрируемый MAC-адрес выбирается произвольно.

== Какие вы знаете методы разделения широковещательного канала? ==
DCF — Distributed Coordination Function. CSMA с избежанием коллизий (jam signal), никакого QoS, возможны инверсии приоритета (всё плохо).

PCF — Point Coordination Function. Работает только, если сеть организована точкой доступа; точка доступа посылает каждые 0.1 секунды специальный сигнал. Между сигналами возможны два периода; в одном она ведёт себя как с DCF, в другом — шлёт станциям пакеты, сообщающие о праве посылать пакеты (AP тут — координатор).

В 802.11e ввели несколько новых функций координации, с QoS. Одна из них (Hybrid Coordination Fuinction) — по сути PCF, но с QoS.

== Что такое шумоподобный сигнал? ==
Cигнал, содержащий много гармонических (синусоидальных) составляющих в выбранной полосе частот. Шумом называют неупорядоченные случайные сложные колебания со сплошным относительно широким частотным спектром. Отсюда происходит название рассматриваемого сигнала. Использование шумообразных сигналов позволяет значительно уменьшить мощность их источников. Она составляет менее 1 Вт. Кроме этого, применение этих сигналов обеспечивает повышение помехоустройчивости передачи данных.

== Опишите проблемы "скрытой" и "засвеченной" станций в беспроводных сетях. ==
Описано вот тут: http://book.itep.ru/4/41/i802_418.htm

== Что такое последовательно Баркера и какое её основное свойство? ==
Числовая последовательность <tex> a_1 , a_2 , \ldots a_N </tex>, где каждый элемент равен +1 или -1, причём <tex>\forall v : 1 \le v < N</tex> выполняется <tex>\left\vert \sum\limits_{j=1}^{N-v} a_j a_{j+v} \right\vert \le 1</tex>. Последовательности Баркера имеют минимальный уровень боковых лепестков автокорреляционной функции.

== Что такое QPSK? ==
Фазовая модуляция, при которой возможных значений фазового сдвига 4.

== Что такое СCK коды и когда они применяются вместо кода Баркера? ==
CCK — Complementary Code Keying. Комплементарными принято называть такие пары последовательностей, для которых сумма автокорреляционных функций последовательностей для любого циклического сдвига, отличного от нуля, всегда равна нулю. Применяются {{TODO|t=WTF}}

== Что такое OFDM? ==
OFDM — Orthogonal Frequency Division Multiplexing — мультиплексирование разделением на ортогональные несущие. При демультиплексировании в принимающих устройствах используется обратное быстрое преобразование Фурье.

== Что такое IEEE 802.11? ==
Набор стандартов связи для коммуникации в беспроводной локальной сетевой зоне частотных диапазонов 0,9; 2,4; 3,6 и 5 ГГц, описывающих передачу данных на физическом уровне и MAC-уровне.

== Какие есть методы расширения спектра сигнала? ==
{{TODO|t=допилить, что ли}}

== Что такое PCF и DCF режимы в 802.11? Могут ли одновременно работать станции по PCF и DCF? ==
По идее, это аналогично вопросу 35. Могут ли одновременно — да, кто мешает? В какой-то из периодов PCF, насколько я помню, вполне может использоваться DCF.

== Что описывают стандарты IEEE 802.16 и 802.16e? ==
WMAN (Wireless MAN) — беспроводные сети масштаба города. Стандарты описывают их работу на физическом уровне, LLC и MAC.

== Что такое и зачем нужен протокол скользящего окна? ==
Он работает следующим образом: посылатель посылает какое-то фиксированное количество байт (размер окна), если информация пришла вовремя и без искажений, то получатель посылает отправителю подтверждение — квитанцию. Нужен — для гарантии передачи данных.

== Что такое ACK в протоколах передачи данных? Что такое NAK и когда выгодно его использовать? ==
ACK — сигнал, означающий подтверждение принятия данных, NAK говорит о том, что данные не пришли. NAK выгодно использовать в случае со стабильной связью (при которой почти не понадобится его посылать).

== Что такое многомодовое и что такое одномодовое оптоволокно? ==
Одномодовое оптоволокно — волокно, которое может передавать только один луч света одновременно. Многоводовое — соответственно, несколько.

== Как достигается одномодовый режим работы оптоволокна? ==
Волокно делают настолько тонким, что диаметр доходит до нескольких длин волн света, в результате чего волокно действует подобно волноводу. {{TODO|t=уточнить, если я правильно понял, в вопросе говорится про то, что многомодовое волокно может работать в одномодовом режиме}}

== Что такое "окна прозрачности в оптоволокне"? ==
Диапазон длин волн оптического излучения, в котором имеет место меньшее, по сравнению с другими диапазонами, затухание излучения в волокне.

== Что такое технологии WDM? ==
WDM (Wavelength-division multiplexing) — мультиплексирование с разделением по длине волны — технология, позволяющая одновременно передавать несколько информационных каналов по одному оптическому волокну на разных несущих частотах. WDM позволяет существенно увеличить пропускную способность канала, причем она позволяет использовать уже проложенные волоконно-оптические линии.

== В чём принцип технологий PON? ==
PON (Passive Optical Network) — технология, основанная на древовидной волоконно-кабельной архитектуре с пассивными оптическими разветвителями на узлах, представляет экономичный способ обеспечить широкополосную передачу информации. При этом архитектура PON обладает необходимой эффективностью наращивания узлов сети и пропускной способности, в зависимости от настоящих и будущих потребностей абонентов. Основная идея: использование всего одного приёмопередающего модуля в OLT (optical line terminal) для передачи информации множеству абонентских устройств ONT (optical network terminal) и приёма информации от них. Все узлы-абоненты ведут передачу на одной и той же длине волны, поэтому для разделения сигналов используется концепция множественного доступа с временным разделением.

== Что такое эрбиевый усилитель сигнала? Зачем он нужен? ==
Волоконно-оптический усилитель на оптическом волокне, легированном ионами эрбия. Применяется в волоконно-оптических линиях передачи для восстановления уровня оптического сигнала. Преимуществом эрбиевых усилителей является отсутствие преобразования в электрический сигнал, возможность одновременного усиления сигналов с разными длинами волн (что обуславливает возможность усиления спектрально-мультиплексированного сигнала), практически точное соответствие рабочего диапазона эрбиевых усилителей области минимальных оптических потерь световодов на основе кварцевого стекла, сравнительно низкий уровень шума и простота включения в волоконно-оптическую систему.

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

= Тест 2 =

== Что такое элементарный и составной каналы в сетях с канальной коммутацией? ==
Элементарный канал — базовая техническая характеристика сети с коммутацией каналов, представляющая собой некоторое фиксированное в пределах данного типа сетей значение пропускной способности. Любая линия в сети с коммутацией каналов имеет пропускную способность, кратную элементарному каналу, принятому для данного типа сети.

== Перечислите примеры протоколов стека TCP/IP по уровням ==
* прикладной (binkp, FTP, Finger, DNS, Gnutella, Gopher, HTTP, HTTPS, IMAP, IRC, XMPP, LDAP, NTP, NNTP, POP3, RDP, SMB, SSH, SMTP, Telnet, SNMP, SIP, DMX-512)
* транспортный (SPX, XOT, BGP, ISODE, DVMRP, TCP, UDP, SCTP, RDP/RUDP, RTCP)
* сетевой (ICMP, IPv4, IPv6, IPX, ARP)
* канальный (Ethernet/IEEE 802.11, Wireless Internet, Token ring, FDDI, HDLC, GVRP, PPP, PPTP, L2TP, ATM, xDSL).

== Какая бывает модуляция? ==
Фазовая (в зависимости от входного сигнала выходной сдвигается на какую-то фазу), амплитудная (в зависимости от входного сигнала изменяется амплитуда выходного), частотная (в зависимости от входного сигнала изменяется частота выходного).

== Приведите примеры вариантов физического кодирования ==
===2 уровня===
* NRZ (Non Return Zero) — простейший код, 1 — есть ток, 0 — нет;
* NRZI (Non Return Zero Inverted) — смена сигнала происходит при передаче единицы, передача нуля не приводит к изменению сигнала;
* RZ (Return to Zero) — 0 — положительное напряжение, 1 — отрицательное, в середине сигнала происходит переход в отсутствие напряжение;
* Манчестерский код — (логическая единица — положительный переход в середине символа, ноль — отрицательный).
===3 уровня===
* Биполярный код AMI - биты 0 представляются нулевым напряжением (0 В), биты 1 представляются поочерёдно значениями -U или +U (В);
* MLT-3 Multi Level Transmission — 3 (многоуровневая передача) — метод кодирования, использующий три уровня сигнала. Метод основывается на циклическом переключении уровней -U, 0, +U. Единице соответствует переход с одного уровня сигнала на следующий. Так же как и в методе NRZI при передаче «нуля» сигнал не меняется.
===4 уровня===
Потенциальный код 2B1Q передает пару бит за один битовый интервал. Каждой возможной паре в соответствие ставится свой уровень из четырех возможных уровней потенциала: "00" = <tex>-2.5</tex>, "01" = <tex>−0.833</tex>, "11" = <tex>+0.833</tex>, "10" = <tex>+2.5</tex>.
== Что такое кадр? ==
Единица передачи на канальном уровне

== Какие есть варианты кадрирования? ==
* подсчёт количества символов;
* использование сигнальных байтов с символьным заполнением;
* использование стартовых и стоповых бит с битовым заполнением;
* использование запрещённых сигналов физического уровня.

== Что такое алгоритм двоичного экспоненциального отката? ==
После <tex>c</tex> коллизий выбираем рандомное число от <tex>0</tex> до <tex>2^c - 1</tex>, ждём это число. Для того, чтобы увеличить время ожидания при большом количестве коллизий и, как следствие, уменьшить их вероятность при повторной передаче.

== Нарисуйте схему CSMA/CD ==
схему? лолшто?
CSMA — Carrier Sense Multiple Access — множественный доступ с контролем несущей. Слушаем канал, если занят, ждём случайное время. Если свободен — передаём, если коллизия — ждём случайное время. Настойчивость <tex>p</tex> — передаём с вероятностью <tex>p</tex>. Детектируем коллизию — шлём jam signal, сообщая о ней другим станциям, потом ждём случайное время… Полудуплекс из-за того, что слушаем канал.

== Какое кодирование используется в 100 мегабитном Ethernet? ==
В 100BASE-T4 используется 8B6T (8 двоичных символов кодируются 6 тернарными), в 100BASE-TX — 4B5B (4 двоичных символа кодируются 5 двоичными, на более нижнем уровне используется NRZI, поэтому один «лишний» символ используется для синхронизации)

== Что такое протокол скользящего окна? ==
см. тест 1, вопрос 46

== Чем отличается концентратор от коммутатора? ==
см. тест 1, вопрос 29

== Что такое и зачем нужны сетевые мосты? ==
см. тест 1, вопрос 30

== Что такое и зачем нужен алгоритм остовного дерева (STP)? ==
см. тест 1, вопрос 31

== Какую задачу решает уровень MAC? ==
см. тест 1, вопрос 32

== Какие есть варианты разделения широковещательного канала? ==
см. тест 1, вопрос 35

== Какие сервисы предоставляет подуровень LLC? ==
см. тест 1, вопрос 33

== Что такое шумоподобный сигнал? ==
см. тест 1, вопрос 36

== Что такое проблема засвеченной станции и проблема скрытой станции? ==
см. тест 1, вопрос 37

== Что такое OFDM? ==
см. тест 1, вопрос 41

== Чем многомодовое оптоволокно отличается от одномодового? ==
см. тест 1, вопрос 48

== Что такое CWDM? ==
CWDM (Coarse WDM) — «грубое» WDM с разносом каналов более 2500 ГГц, позволяет мультиплексировать не более 18 каналов.

== В чём отличительная особенность технологии PON? ==
см. тест 1, вопрос 52

== Перечислите сервисы сетевого уровня ==
{{TODO|t=найти информацию и допилить}}

== Что такое маршрутизация? ==
Маршрутизация — процесс определения маршрута следования информации в сетях связи.

== Чем маршрутизация при дейтаграммном подходе отличается от маршрутизации в сетях с виртуальными каналами? ==
При дейтаграммном подходе для каждого пакета строится свой маршрут. При маршрутизации с виртуальным каналом все пакеты идут по одному маршруту.

Вроде всё. Мы же дальше не проходили?

Префикс-функция

2014-10-20T20:14:26Z

91.215.121.216: /* Реализация */

{{Определение
|definition = '''Префикс-функция''' ''(англ. prefix-function)'' от строки {{---}} массив длин наибольших [[Период_и_бордер,_их_связь#Определения|бордеров]] для каждой позиции этой строки}}
Здесь и далее считаем, что символы в строках нумеруются с <tex>1</tex>.

Определим префикс-функцию от строки <tex>s</tex> в позиции <tex>i</tex> следующим образом: <tex>\pi(s, i) = \max\limits_{k = 1..i - 1} \{k : </tex> <tex>s[1..k] = s[i - k + 1..i] \}</tex>. Если мы не нашли такого <tex>k</tex>, то <tex>\pi(s, i)=0</tex>.

==Наивный алгоритм==
Наивный алгоритм вычисляет префикс-функцию непосредственно по определению, сравнивая префиксы и суффиксы строк. Обозначим длину строки за <tex>n</tex>. Будем считать, что префикс-функция хранится в массиве <tex> p </tex>.

===Псевдокод===
'''int'''[] prefixFunction('''string''' s):
'''int'''[] p = '''int'''[s.length]
fill(p, 0)
'''for''' i = 1 '''to''' n
'''for''' k = 1 '''to''' i
'''if''' s[1..k] == s[i - k + 1..i]
p[i] = k
'''return''' p

===Пример===
Рассмотрим строку <tex>abcabcd</tex>, для которой значение префикс-функции равно <tex>[0,0,0,1,2,3,0]</tex>.
{| class="wikitable"
! Шаг || Строка || Значение функции
|-
| <tex>1</tex> || a || 0
|-
| <tex>2</tex> || ab || 0
|-
| <tex>3</tex> || abc || 0
|-
| <tex>4</tex> || abca || 1
|-
| <tex>5</tex> || abcab || 2
|-
| <tex>6</tex> || abcabc || 3
|-
| <tex>7</tex> || abcabcd || 0
|}

===Время работы===
Всего <tex>O(n^2)</tex> итераций цикла, на каждой из который происходит сравнение строк за <tex>O(n)</tex>, что дает в итоге <tex>O(n^3)</tex>.

==Эффективный алгоритм==
Вносятся несколько важных замечаний:
* Заметим, что <tex>p[i + 1] \leqslant p[i] + 1</tex>. Чтобы показать это, рассмотрим суффикс,оканчивающийся на позиции <tex>i + 1</tex> и имеющий длину <tex>p[i + 1]</tex>, удалив из него последний символ, мы получим суффикс, оканчивающийся на позиции <tex>i</tex> и имеющий длину <tex>p[i + 1] - 1</tex>, следовательно неравенство <tex>p[i + 1] > p[i] + 1</tex> неверно.
* Избавимся от явных сравнений строк. Пусть мы вычислили <tex>p[i]</tex>, тогда, если <tex>s[i + 1] = s[p[i]]</tex>, то <tex>p[i + 1] = p[i] + 1</tex>. Если окажется, что <tex>s[i + 1] \ne s[p[i]]</tex>, то нужно попытаться попробовать подстроку меньшей длины. Хотелось бы сразу перейти к такому [[Период_и_бордер,_их_связь#Определения|бордеру]] наибольшей длины, для этого подберем такое <tex>k</tex>, что <tex>k = p[i] - 1</tex>. Делаем это следующим образом. За исходное <tex>k</tex> необходимо взять <tex>p[i - 1]</tex>, что следует из первого пункта. В случае, когда символы <tex>s[k+1]</tex> и <tex>s[i]</tex> не совпадают, <tex>p[k]</tex> {{---}} следующее потенциальное наибольшее значение <tex>k</tex>, что видно из рисунка. Последнее утверждение верно, пока <tex>k>0</tex>, что позволит всегда найти его следующее значение. Если <tex>k=0</tex>, то <tex>p[i]=1</tex> при <tex>s[i] = s[1]</tex> , иначе <tex>p[i]=0</tex>.

[[Файл:mprfx.jpg|800px]]

===Псевдокод===
'''int'''[] prefixFunction('''string''' s):
p[1] = 0
'''for''' i = 2 '''to''' n
k = p[i - 1]
'''while''' k > 0 '''and''' s[i] != s[k + 1]
k = p[k]
'''if''' s[i] == s[k + 1]
k++
p[i] = k
'''return''' p

===Время работы===
Время работы алгоритма составит <tex>O(n)</tex>. Для доказательства этого нужно заметить, что итоговое количество итераций цикла <tex>\mathrm{while}</tex> определяет асимптотику алгоритма. Теперь стоит отметить, что <tex>k</tex> увеличивается на каждом шаге не более чем на единицу, значит максимально возможное значение <tex>k = n - 1</tex>. Поскольку внутри цикла <tex>\mathrm{while}</tex> значение <tex>k</tex> лишь уменьшается, получается, что <tex>k</tex> не может суммарно уменьшиться больше, чем <tex>n-1</tex> раз. Значит цикл <tex>\mathrm{while}</tex> в итоге выполнится не более <tex>n</tex> раз, что дает итоговую оценку времени алгоритма <tex>O(n)</tex>.

== Построение префикс-функции по Z-функции==
=== Постановка задачи ===
Дан массив с корректной [[Z-функция | Z-функцией]] для строки <tex>s</tex>, получить за <tex>O(n)</tex> массив с префикс-функцией для строки <tex>s</tex>.

=== Описание алгоритма ===
Пусть Z-функция хранится в массиве <tex>z[1..n]</tex>. Префикс-функцию будем записывать в массив <tex>p[1..n]</tex>.
Заметим, что если <tex>z[i] > 0, </tex> то для всех элементов с индексом <tex>i + j</tex>, где <tex>0 \leqslant j < z[i] </tex>, значение <tex>p[i + j] </tex> будет не меньше, чем длина подстроки с <tex> i </tex> по <tex> i + j</tex>, что равно <tex>j + 1</tex> (как изображено на рисунке).

Также заметим, что если мы уже установили в какую-то позицию значение <tex> j </tex> с позиции <tex> i </tex>, а потом пытаемся установить значение <tex> j' </tex> c позиции <tex> i' </tex>, причём <tex> i < i' </tex> и <tex> i + j = i' + j' </tex>, то изменение с позиции <tex> i' </tex> только уменьшит значение <tex> p[i + j]</tex>. Действительно, значение после первого присвоения <tex>p[i + j] = j > j' = p[i' + j']</tex>. В итоге получаем алгоритм: идем слева направо по массиву <tex>z</tex> и, находясь на позиции <tex>i</tex>, пытаемся записать в <tex>p</tex> от позиции <tex>i + z[i] - 1 </tex> до <tex>i</tex> значение <tex> j + 1,</tex> где <tex>j</tex> пробегает все значения <tex> 0 \dots z[i] - 1</tex>, пока не наткнемся на уже инициализированный элемент. Слева от него все значения тоже нет смысла обновлять, поэтому прерываем эту итерацию.

Убедимся, что алгоритм работает за линейное время (см. псевдокод). Каждый элемент устанавливается ровно один раз. Дальше на нем может случиться только <tex>\mathrm{break}</tex>. Поэтому в итоге внутренний цикл суммарно отработает за количество установленных значений и количество <tex>\mathrm{break}</tex>. Количество установленных значений {{---}} <tex> n</tex>. А число <tex>\mathrm{break}</tex> тоже будет не больше <tex>n</tex>, так как каждый <tex>\mathrm{break}</tex> переводит внешний цикл на следующую итерацию, откуда получаем итоговую асимптотику <tex>O(n)</tex>.

[[Файл:ZP4.jpg|800px]]

=== Псевдокод ===
'''int'''[] buildPrefixFunctionFromZFunction('''int'''[] z):
'''int'''[] p = '''int'''[z.length]
fill(p, 0)
'''for''' i = 2 '''to''' z.length - 1
'''for''' j = z[i] - 1 '''downto''' 0
'''if''' p[i + j] > 0
'''break'''
'''else'''
p[i + j] = j + 1
'''return''' p

==Построение строки по префикс-функции==
===Постановка задачи===
Восстановить строку по префикс-функции за <tex>O(n)</tex>, считая алфавит неограниченным.

===Описание алгоритма===
Здесь для удобства будем считать, что строки и массивы нумеруются с нуля.

Пусть в массиве <tex>p</tex> хранятся значения префикс-функции, в <tex>s</tex> будет записан ответ. Пойдем по массиву <tex>p</tex> слева направо.

Пусть мы хотим узнать значение <tex>s[i]</tex>. Для этого посмотрим на значение <tex>p[i]</tex>: если <tex>p[i] =0</tex>, тогда в <tex>s[i]</tex> запишем новый символ, иначе <tex>s[i] = s[p[i]]</tex>. Обратим внимание, что <tex>s[p[i]]</tex> нам уже известно, так как <tex>p[i] < i</tex>.

=== Реализация ===
'''string''' buildFromPrefix('''int'''[] p):
s = ""
'''for''' i = 0 '''to''' p.length - 1
'''if''' p[i] == 0
s += new character
'''else'''
s += s[p[i] - 1]
'''return''' s

===Доказательство корректности алгоритма===
Докажем, что если нам дали корректную префикс-функцию, то наш алгоритм построит строку с такой же префикс-функцией. Также заметим, что строк с такой префикс-функцией может быть много, и алгоритм строит только одну из них.

Пусть <tex>p</tex> {{---}} данная префикс-функция, строку <tex>s</tex> построил наш алгоритм, <tex> q </tex> {{---}} массив значений префикс-функции для <tex>s</tex>.

Докажем корректность индукцией по длине массива префикс-функции полученной строки. Для начала заметим, что на предыдущие значения массива <tex> q </tex> прибавление нового символа не влияет, так как при подсчёте префикс-функции на <tex> i </tex>-ой позиции рассматриваются символы на позициях не больше <tex> i </tex>. Поэтому достаточно показать, что очередное значение префикс-функции будет вычислено правильно.
* База очевидна для строки длины <tex>1</tex>.
* Переход: пусть до <tex>n</tex>-ой позиции мы построили строку, что <tex>p[0..n - 1] = q[0..n - 1]</tex>. Возможны два случая:
** <tex>p[n] = 0</tex>. Тогда мы добавляем новый символ, поэтому <tex>q[n]</tex> тоже будет равно <tex>0</tex>.
** <tex>p[n] > 0</tex>. Бордер строки <tex> s[0..n - 1] </tex> имеет длину <tex> p[n-1] = q[n-1] </tex>. Поэтому если дописать к строке <tex> s </tex> символ <tex> s[q[n]] </tex>, то бордер нашей новой строки <tex> s[0..n] </tex> станет равен <tex> p[n] </tex>, как можно увидеть на [[Префикс-функция#Эффективный алгоритм | рисунке]].

== См. также ==
*[[Z-функция|Z-функция]]
*[[Алгоритм Кнута-Морриса-Пратта|Алгоритм Кнута-Морриса-Пратта]]
== Источники информации ==
*[[wikipedia:ru:Префикс-функция | Википедия {{---}} Префикс-функция]]
*[http://e-maxx.ru/algo/prefix_function MAXimal :: algo :: Префикс-функция]
* Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. {{---}} 2-е изд. {{---}} М.: Издательский дом «Вильямс», 2007. {{---}} С. 1296 ISBN 978-5-8459-0857-5

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Поиск подстроки в строке]]

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

2014-04-13T17:44:36Z

91.215.121.216:

== Лекция - Классы чисел и основная теорема арифметики ==
* [[Классы чисел]]
* [[Натуральные и целые числа]]
* [[Простые числа]]
* [[Наибольший общий делитель]]
* [[Основная теорема арифметики]]
* [[Теоремы о простых числах]]
=== Практика - Разложение на множители и длинная арифметика ===
* [[Системы счисления]]
* [[Арифметика чисел в b-ичной системе счисления (Длинная арифметика)]]
* [[Разложение на множители (факторизация)]]

== Лекция - Основные элементы теории чисел ==
* [[Сравнения, система вычетов, решение линейных систем по модулю]]
* [[Китайская теорема об остатках]]
* [[Теорема Ферма]]
* [[Теорема Вильсона]]
* [[Мультипликативность функции, свертка Дирихле]]
* [[Функция Эйлера]]
* [[Количество делителей, сумма делителей]]
* [[Функция Мебиуса]]

=== Практика - Основные алгоритмы теории чисел ===
* [[Решето Эратосфена]]
* [[Быстрое возведение в степень]]
* [[Умножение по Монтгомери]]

== Лекция - Основы теории групп ==
* [[Полугруппа]], [[моноид]], [[группа]]
* [[Абелева группа]], [[Конечная группа]]
* [[Гомоморфизм групп]], [[изоморфизм групп]]
* [[Подгруппа]], [[нормальная подгруппа]]
* [[Порядок элемента группы]], [[циклическая группа]], [[конечно порожденная группа]]
* [[Теорема о подгруппах циклической группы]]
* [[Смежные классы]], [[теорема Лагранжа]], [[факторгруппы]]
=== Практика - Основы теории групп ===
* [[Вычисление порядка элемента в группе]]
* [[Вычисление порядка перестановки в группе перестановок]]
* [[Дискретное логарифмирование в группе]]
* [[Действие группы на множестве]]
* [[Лемма Бернсайда, задача о числе ожерелий]]
* [[Представление групп]]

== Лекция - Основы теории колец ==
*[[Определение кольца, подкольца, изоморфизмы колец]]
*[[Делители нуля, области целостности]]
*[[Единицы (обратимые элементы), группа обратимых элементов]]
*[[Неразложимые элементы, ассоциированные элементы и разложение на множители в целостных кольцах]]
*[[Евклидовы кольца]]
=== Практика - Арифметика полиномов от одной переменной над полем ===

== Лекция - Основы теории полей ==
* [[Определение поля и подполя, изоморфизмы полей]]
* [[Примеры полей]]
* [[Мультипликативная группа поля]]
* [[Расширения полей]]

== Лекция - Первообразные корни и квадратичные вычеты ==
* [[Теорема о цикличности мультипликативной группы поля Z/pZ|Теорема о цикличности мультипликативной группы поля <tex>\mathbb{Z}/p\mathbb{Z}</tex>]]
* [[Первообразные корни]]
** [[Существование первообразных корней по определенным модулям|Теорема о существовании первообразных корней по модулям вида <tex>2,4,p^n,2\cdot p^n</tex>]]
* [[Квадратичные вычеты|Квадратичные вычеты, количество квадратичных вычетов по простому модулю]]
** [[Символ Лежандра, критерий Эйлера]]
** [[Теорема о (((p-1)/2)!)^2=-1(mod p)|Теорема о <tex>((\frac{p-1}{2})!)^2\equiv -1 (mod ~p)</tex> при <tex>p=4\cdot k+1</tex>]]
** [[Лемма Гаусса для вычисления квадратичного характера числа по простому модулю]]
=== Практика - Первообразные корни и квадратичные вычеты ===

== Лекция - Квадратичные вычеты ==
*[[Квадратичный закон взаимности]]
*[[Символ Якоби и его свойства]]
*[[Обобщенный квадратичный закон взаимности]]
*[[Алгоритм вычисления символа Якоби]]
=== Практика - Вероятностные тесты чисел на простоту ===
*[[Тест Ферма проверки чисел на простоту, числа Кармайкла]]
*[[Тест Соловея-Штрассена]]
*[[Тест Миллера-Рабина]]

== Лекция - Аналитическая теория чисел ==
* [[Факты из математического анализа]]
* [[Теорема Чебышёва]]
* [[Постулат Бертрана]]
* [[Уточнение констант в теореме Чебышёва]]
* [[Сумма обратных к простым]]
* [[Асимптотический закон распределения простых чисел]]
=== Практика - Вычисление <math>\pi(x)</math> ===

== Лекция - Цепные (непрерывные) дроби и уравнение Пелля ==
* [[Цепная дробь]]
** [[Связь цепных дробей и алгоритма Евклида]]
** [[Сходимость цепных дробей]]
** [[Цепные дроби как приближение к числу]]
** [[Квадратичная иррациональность]]
** [[Периодичность цепных дробей]]
** [[Цепные дроби для sqrtd и квадратичных иррациональностей|Цепные дроби для <tex>\sqrt{d}</tex> и квадратичных иррациональностей]]
* [[Уравнение Пелля]]
* [[Представление простых в виде суммы двух квадратов]]

== Лекция - Конечные поля ==
=== Практика - Методы разложения полиномов на множители над конечными полями ===

Удаление eps-правил из грамматики

2013-12-19T15:47:20Z

91.215.121.216: /* Время работы алгоритма */

== Используемые определения ==
{{Определение
|definition = Правила вида <tex>A \to \varepsilon</tex> называются '''<tex>\varepsilon</tex>-правилами''' (''<tex>\varepsilon</tex> rule'').
}}
{{Определение
|definition = Нетерминал <tex>A</tex> называется '''<tex>\varepsilon</tex>-порождающим''' (''<tex>\varepsilon</tex>-generating''), если <tex>A \Rightarrow^* \varepsilon</tex>.
}}

== Алгоритм удаления ε-правил из грамматики ==
'''Вход:''' КС грамматика <tex> G=\langle N,\Sigma, P, S \rangle</tex>. 
'''Выход:''' КС грамматика <tex> G'=\langle N,\Sigma, P', S' \rangle</tex> без <tex>\varepsilon</tex>-правил (может присутствовать правило <tex>S \rightarrow \varepsilon</tex>, но в этом случае <tex>S</tex> не встречается в правых частях правил); <tex>L(G') = L(G)</tex>.

# Добавить все правила из <tex>P</tex> в <tex>P'</tex>.
# [[#.D0.90.D0.BB.D0.B3.D0.BE.D1.80.D0.B8.D1.82.D0.BC_.D0.BF.D0.BE.D0.B8.D1.81.D0.BA.D0.B0_.CE.B5-.D0.BF.D0.BE.D1.80.D0.BE.D0.B6.D0.B4.D0.B0.D1.8E.D1.89.D0.B8.D1.85_.D0.BD.D0.B5.D1.82.D0.B5.D1.80.D0.BC.D0.B8.D0.BD.D0.B0.D0.BB.D0.BE.D0.B2 | Найти все <tex>\varepsilon</tex>-порождаюшие нетерминалы]].
# Для каждого правила вида <tex>A \rightarrow \alpha_0 B_1 \alpha_1 B_2 \alpha_2 ... B_k \alpha_k</tex> (где <tex>\alpha_i</tex> — последовательности из терминалов и нетерминалов, <tex>B_j</tex> — <tex>\varepsilon</tex>-порождающие нетерминалы) добавить в <tex>P'</tex> все возможные варианты правил, в которых либо присутствует, либо удалён каждый из нетерминалов <tex>B_j\; (1 \le j \le k)</tex>.
# Удалить все <tex>\varepsilon</tex>-правила из <tex>P'</tex>.
# Если в исходной грамматике <tex>G</tex> выводилось <tex>\varepsilon</tex>, то необходимо добавить новый нетерминал <tex>S'</tex>, сделать его стартовым, добавить правило <tex>S' \rightarrow S|\varepsilon</tex>.

=== Доказательство корректности ===
{{Теорема
|statement = Если грамматика <tex>G'</tex> была построена с помощью описанного выше алгоритма по грамматике <tex>G</tex>, то <tex>L(G') = L(G)</tex>.
|proof =
Сначала докажем, что, если не выполнять шаг 5 алгоритма, то получится грамматика <tex>G' : L(G') = L(G) \setminus \lbrace \varepsilon \rbrace </tex>. 
Для этого достаточно доказать, что
<tex>A \underset{G'}{\Rightarrow}^*w</tex> тогда и только тогда, когда <tex>A \underset{G}{\Rightarrow}^*w</tex> и <tex>w \ne \varepsilon</tex> (*).

<tex>\Rightarrow</tex><br\>
Пусть <tex>A \underset{G'}{\Rightarrow}^*w</tex>  и  <tex>w \ne \varepsilon</tex>. 
Докажем индукцией по длине порождения в грамматике <tex>G'</tex>, что <tex>A \underset{G}{\Rightarrow}^*w</tex>. 
'''База'''. <tex>A \underset{G'}{\Rightarrow} w</tex>. 
В этом случае в <tex>G'</tex> есть правило <tex>A \rightarrow w</tex>. По построению <tex>G'</tex> в <tex>G</tex> есть правило <tex>A \rightarrow \alpha</tex>, причем <tex>\alpha</tex> — цепочка <tex>w</tex>, элементы которой, возможно, перемежаются <tex>\varepsilon</tex>-порождающими нетерминалами. Тогда в <tex>G</tex> есть порождения <tex>A \underset{G}{\Rightarrow} \alpha \underset{G}{\Rightarrow}^*w</tex>. 
'''Предположение индукции'''. Пусть из <tex>A \underset{G'}{\Rightarrow}^*w \ne \varepsilon</tex> менее, чем за <tex>n</tex> шагов, следует, что <tex>A \underset{G}{\Rightarrow}^*w</tex>. 
'''Переход'''.
Пусть в порождении <tex>n</tex> шагов, <tex>n > 1</tex>. Тогда оно имеет вид <tex>A\underset{G'}{\Rightarrow}X_1 X_2...X_k \underset{G'}{\Rightarrow}^*w</tex>, где <tex>X_i \in N \cup \Sigma </tex>. Первое использованное правило должно быть построено по правилу грамматики <tex>G</tex> <tex>A \rightarrow Y_1 Y_2...Y_m</tex>, где последовательность <tex>Y_1 Y_2...Y_m</tex> совпадает с последовательностью <tex>X_1 X_2...X_k</tex>, символы которой, возможно, перемежаются <tex>\varepsilon</tex>-порождающими нетерминалами. 
Цепочку <tex>w</tex> можно разбить на <tex>w_1 w_2...w_k</tex>, где <tex>X_i \underset{G'}{\Rightarrow}^*w_i</tex>. Если <tex>X_i</tex> — терминал, то <tex>w_i = X_i</tex>, a если нетерминал, то порождение <tex>X_i \underset{G'}{\Rightarrow}^*w_i</tex> содержит менее <tex>n</tex> шагов. По предположению <tex>X_i \underset{G}{\Rightarrow}^*w_i</tex>, значит <tex>A \underset {G}{\Rightarrow} Y_1 Y_2...Y_m \underset{G}{\Rightarrow}^* X_1 X_2...X_k \underset{G}{\Rightarrow}^* w_1 w_2...w_k = w</tex>.

<tex>\Leftarrow</tex> 
Пусть <tex>A \underset{G}{\Rightarrow}^*w</tex>  и  <tex>w \ne \varepsilon</tex>. 
Докажем индукцией по длине порождения в грамматике <tex>G</tex>, что <tex>A \underset{G'}{\Rightarrow}^*w</tex>. 
'''База'''. <tex>A \underset{G}{\Rightarrow} w</tex>. 
Правило <tex>A \rightarrow w</tex> присутствует в <tex>G</tex>. Поскольку <tex>w \ne \varepsilon</tex>, это же правило будет и в <tex>G'</tex>, поэтому <tex>A \underset{G'}{\Rightarrow}^*w</tex>. 
'''Предположение индукции'''. Пусть из <tex>A \underset{G}{\Rightarrow}^*w \ne \varepsilon</tex> менее, чем за <tex>n</tex> шагов, следует, что <tex>A \underset{G'}{\Rightarrow}^*w </tex>. 
'''Переход'''. Пусть в порождении <tex>n</tex> шагов, <tex>n > 1</tex>. Тогда оно имеет вид <tex>A\underset{G}{\Rightarrow}Y_1 Y_2...Y_m \underset{G}{\Rightarrow}^*w</tex>, где <tex>Y_i \in N \cup \Sigma </tex>. Цепочку <tex>w</tex> можно разбить на <tex>w_1 w_2...w_m</tex>, где <tex>Y_i \underset{G}{\Rightarrow}^*w_i</tex>. 
Пусть <tex>Y_{i_1}, Y_{i_2}, ..., Y_{i_p}</tex> — подпоследовательность, состоящая из всех элементов, таких, что <tex>w_{i_k} \ne \varepsilon</tex>, то есть <tex>Y_{i_1} Y_{i_2} ... Y_{i_p} \underset{G}{\Rightarrow}^*w</tex>. <tex>p \ge 1</tex>, поскольку <tex>w \ne \varepsilon</tex>. Значит, <tex>A \rightarrow Y_{i_1} Y_{i_2} ... Y_{i_p}</tex> является правилом в <tex>G'</tex> по построению <tex>G'</tex>. 
Так как каждое из порождений <tex>Y_i \underset{G}{\Rightarrow}^*w_i</tex> содержит менее <tex>n</tex> шагов, к ним можно применить предположение индукции и заключить, что, если <tex>w_i \ne \varepsilon</tex>, то <tex>Y_i \underset{G'}{\Rightarrow}^*w_i</tex>. 
Таким образом, <tex>A \underset{G'}{\Rightarrow} Y_{i_1} Y_{i_2} ... Y_{i_p} \underset{G'}{\Rightarrow}^* w</tex>.

Подставив <tex>S</tex> вместо <tex>A</tex> в утверждение (*), видим, что <tex>w \in L(G)</tex> для <tex>w \ne \varepsilon</tex> тогда и только тогда, когда <tex>w \in L(G')</tex>. Так как после выполнения шага 5 алгоритма в <tex>G'</tex> могло добавиться только пустое слово <tex>\varepsilon</tex>, то язык, задаваемый КС грамматикой <tex>G'</tex>, совпадает с языком, задаваемым КС грамматикой <tex>G</tex>.
}}

=== Время работы алгоритма ===
Рассмотрим грамматику:
<tex> \Gamma =
\begin{array}{l l}
S\rightarrow T_1 T_2 T_3 ... T_n\\
T_1\rightarrow t_1|\varepsilon\\
T_2\rightarrow t_2|\varepsilon\\
...\\
T_n\rightarrow t_n|\varepsilon
\end{array}
</tex>. 
<tex>\left| \Gamma \right| = O(n)</tex>. Из нетерминала <tex>S</tex> можно вывести <tex>2^n</tex> сочетаний нетерминалов <tex>T_i</tex>. Таким образом в худшем случае алгоритм работает за <tex>O(2^{\left| \Gamma \right|})</tex>. 
Однако если в грамматике устранены [[Удаление_длинных_правил_из_грамматики|длинные правила]], то алгоритм будет работать за <tex>O(\left| \Gamma \right|)</tex> и добавит в грамматику <tex>O(\left| \Gamma \right|)</tex> новых правил длинны <tex>O(1)</tex>.

=== Пример ===
Рассмотрим грамматику:
<tex>
\begin{array}{l l}
S\rightarrow ABCd\\
A\rightarrow a|\varepsilon\\
B\rightarrow AC\\
C\rightarrow c|\varepsilon
\end{array}
</tex>, в которой <tex>A</tex>, <tex>B</tex> и <tex>C</tex> являются <tex>\varepsilon</tex>-порождающими нетерминалами.
# Переберём для каждого правила все возможные сочетания ε-порождающих нетерминалов и добавим новые правила:
#* <tex>S\rightarrow Ad|ABd|Bd|BCd|Cd|d</tex> для <tex>S \rightarrow ABCd</tex>
#* <tex>B \rightarrow A|C</tex> для <tex>B \rightarrow AC</tex>
# Удалим праила <tex>A\rightarrow \varepsilon</tex> и <tex>C\rightarrow \varepsilon</tex>

В результате мы получим новую грамматику без <tex>\varepsilon</tex>-правил:
<tex>\begin{array}{l l}
S\rightarrow Ad|ABd|ABCd|Bd|BCd|Cd|d\\
A\rightarrow a\\
B\rightarrow A|AC|C\\
C\rightarrow c
\end{array}</tex>

== Алгоритм поиска ε-порождающих нетерминалов ==
'''Вход:''' КС грамматика <tex> G=\langle N,\Sigma, P, S \rangle</tex>. 
'''Выход:''' множество <tex>\varepsilon</tex>-порождающих нетерминалов.

# Найти все <tex>\varepsilon</tex>-правила. Составить множество, состоящее из нетерминалов, входящих в левые части таких правил.
# Перебираем правила грамматики <tex>G</tex>. Если найдено правило <tex>A \rightarrow C_1C_2...C_k</tex>, для которого верно, что каждый <tex>C_i</tex> принадлежит множеству, то добавить <tex>A</tex> в множество.
# Если на шаге 2 множество изменилось, то повторить шаг 2.

=== Доказательство корректности ===
{{Теорема
|statement = Описанный выше алгоритм находит все <tex>\varepsilon</tex>-порождающие нетерминалы грамматики <tex>G</tex>.
|proof =

Для доказательства корректности алгоритма достаточно показать, что, если множество <tex>\varepsilon</tex>-порождающих нетерминалов на очередной итерации алгоритма не изменялось, то алгоритм нашел все <tex>\varepsilon</tex>-порождающие нетерминалы.

Пусть после завершения алгоритма существуют нетерминалы такие, что они являются <tex>\varepsilon</tex>-порождающими, но не были найдены алгоритмом. Выберем из этих нетерминалов нетерминал <tex>B</tex>, из которого выводится <tex>\varepsilon</tex> за наименьшее число шагов. Тогда в грамматике есть правило <tex>B \rightarrow C_1C_2...C_k</tex>, где каждый нетерминал <tex>C_i</tex> — <tex>\varepsilon</tex>-порождающий. Каждый <tex>C_i</tex> входит в множество <tex>\varepsilon</tex>-порождающих нетерминалов, так как иначе вместо <tex>B</tex> необходимо было взять <tex>C_i</tex>. Следовательно, на одной из итераций алгоритма <tex>B</tex> уже добавился в множество <tex>\varepsilon</tex>-порождающих нетерминалов. Противоречие. Следовательно, алгоритм находит все <tex>\varepsilon</tex>-порождающие нетерминалы.
}}

=== Время работы алгоритма ===
Данный алгоритм работает за <tex>O(\left| \Gamma \right| ^ 2)</tex>, однако используя [[Очередь|очередь]] можно ускорить его до <tex>O(\left| \Gamma \right|)</tex>.

=== Пример ===
Рассмотрим грамматику:
<tex>
\begin{array}{l l}
S\rightarrow ABC|DS\\
A\rightarrow \varepsilon\\
B\rightarrow AC\\
C\rightarrow \varepsilon\\
D\rightarrow d
\end{array}
</tex>
# Возьмём множество состоящее из <tex>\varepsilon</tex>-порождающих нетерминалов <tex>\lbrace A, C \rbrace</tex>.
# Добавим <tex>B</tex> в множество, так как правая часть правила <tex>B\rightarrow AC</tex> состоит только из нетерминалов из множества.
# Повторим второй пункт для правила <tex>S\rightarrow ABC</tex> и получим множество <tex>\lbrace A, B, C, S \rbrace</tex>.
# Больше нет нерассмотренных правил, содержащих справа только нетерминалы из множества.

Таким образом <tex>\varepsilon</tex>-порождающими нетерминалами являются <tex>A</tex>, <tex>B</tex>, <tex>C</tex> и <tex>S</tex>.

== См. также ==
* [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|Контекстно-свободные грамматики]]
* [[Нормальная_форма_Хомского|Нормальная форма Хомского]]
* [http://en.wikipedia.org/wiki/Chomsky_normal_form Chomsky normal form]

== Литература ==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — С. 273: ISBN 5-8459-0261-4 (рус.)
[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

Удаление eps-правил из грамматики

2013-11-17T11:35:36Z

91.215.121.216:

== Используемые определения ==
{{Определение
|definition = Правила вида <tex>A \to \varepsilon</tex> называются '''<tex>\varepsilon</tex>-правилами''' (''<tex>\varepsilon</tex> rule'').
}}
{{Определение
|definition = Нетерминал <tex>A</tex> называется '''<tex>\varepsilon</tex>-порождающим''' (''<tex>\varepsilon</tex>-generating''), если <tex>A \Rightarrow^* \varepsilon</tex>.
}}

== Алгоритм удаления ε-правил из грамматики ==
'''Вход:''' КС грамматика <tex> G=\langle N,\Sigma, P, S \rangle</tex>. 
'''Выход:''' КС грамматика <tex> G'=\langle N,\Sigma, P', S' \rangle</tex> без <tex>\varepsilon</tex>-правил (может присутствовать правило <tex>S \rightarrow \varepsilon</tex>, но в этом случае <tex>S</tex> не встречается в правых частях правил); <tex>L(G') = L(G)</tex>.

# Добавить все правила из <tex>P</tex> в <tex>P'</tex>.
# [[#.D0.90.D0.BB.D0.B3.D0.BE.D1.80.D0.B8.D1.82.D0.BC_.D0.BF.D0.BE.D0.B8.D1.81.D0.BA.D0.B0_.CE.B5-.D0.BF.D0.BE.D1.80.D0.BE.D0.B6.D0.B4.D0.B0.D1.8E.D1.89.D0.B8.D1.85_.D0.BD.D0.B5.D1.82.D0.B5.D1.80.D0.BC.D0.B8.D0.BD.D0.B0.D0.BB.D0.BE.D0.B2 | Найти все <tex>\varepsilon</tex>-порождаюшие нетерминалы]].
# Для каждого правила вида <tex>A \rightarrow \alpha_0 B_1 \alpha_1 B_2 \alpha_2 ... B_k \alpha_k</tex> (где <tex>\alpha_i</tex> — последовательности из терминалов и нетерминалов, <tex>B_j</tex> — <tex>\varepsilon</tex>-порождающие нетерминалы) добавить в <tex>P'</tex> все возможные варианты правил, в которых либо присутствует, либо удалён каждый из нетерминалов <tex>B_j\; (1 \le j \le k)</tex>.
# Удалить все <tex>\varepsilon</tex>-правила из <tex>P'</tex>.
# Если в исходной грамматике <tex>G</tex> выводилось <tex>\varepsilon</tex>, то необходимо добавить новый нетерминал <tex>S'</tex>, сделать его стартовым, добавить правило <tex>S' \rightarrow S|\varepsilon</tex>.

=== Доказательство корректности ===
{{Теорема
|statement = Если грамматика <tex>G'</tex> была построена с помощью описанного выше алгоритма по грамматике <tex>G</tex>, то <tex>L(G') = L(G)</tex>.
|proof =
Сначала докажем, что, если не выполнять шаг 5 алгоритма, то получится грамматика <tex>G' : L(G') = L(G) \setminus \lbrace \varepsilon \rbrace </tex>. 
Для этого достаточно доказать, что
<tex>A \underset{G'}{\Rightarrow}^*w</tex> тогда и только тогда, когда <tex>A \underset{G}{\Rightarrow}^*w</tex> и <tex>w \ne \varepsilon</tex> (*).

<tex>\Rightarrow</tex><br\>
Пусть <tex>A \underset{G'}{\Rightarrow}^*w</tex>  и  <tex>w \ne \varepsilon</tex>. 
Докажем индукцией по длине порождения в грамматике <tex>G'</tex>, что <tex>A \underset{G}{\Rightarrow}^*w</tex>. 
'''База'''. <tex>A \underset{G'}{\Rightarrow} w</tex>. 
В этом случае в <tex>G'</tex> есть правило <tex>A \rightarrow w</tex>. По построению <tex>G'</tex> в <tex>G</tex> есть правило <tex>A \rightarrow \alpha</tex>, причем <tex>\alpha</tex> — цепочка <tex>w</tex>, элементы которой, возможно, перемежаются <tex>\varepsilon</tex>-порождающими нетерминалами. Тогда в <tex>G</tex> есть порождения <tex>A \underset{G}{\Rightarrow} \alpha \underset{G}{\Rightarrow}^*w</tex>. 
'''Предположение индукции'''. Пусть из <tex>A \underset{G'}{\Rightarrow}^*w \ne \varepsilon</tex> менее, чем за <tex>n</tex> шагов, следует, что <tex>A \underset{G}{\Rightarrow}^*w</tex>. 
'''Переход'''.
Пусть в порождении <tex>n</tex> шагов, <tex>n > 1</tex>. Тогда оно имеет вид <tex>A\underset{G'}{\Rightarrow}X_1 X_2...X_k \underset{G'}{\Rightarrow}^*w</tex>, где <tex>X_i \in N \cup \Sigma </tex>. Первое использованное правило должно быть построено по правилу грамматики <tex>G</tex> <tex>A \rightarrow Y_1 Y_2...Y_m</tex>, где последовательность <tex>Y_1 Y_2...Y_m</tex> совпадает с последовательностью <tex>X_1 X_2...X_k</tex>, символы которой, возможно, перемежаются <tex>\varepsilon</tex>-порождающими нетерминалами. 
Цепочку <tex>w</tex> можно разбить на <tex>w_1 w_2...w_k</tex>, где <tex>X_i \underset{G'}{\Rightarrow}^*w_i</tex>. Если <tex>X_i</tex> — терминал, то <tex>w_i = X_i</tex>, a если нетерминал, то порождение <tex>X_i \underset{G'}{\Rightarrow}^*w_i</tex> содержит менее <tex>n</tex> шагов. По предположению <tex>X_i \underset{G}{\Rightarrow}^*w_i</tex>, значит <tex>A \underset {G}{\Rightarrow} Y_1 Y_2...Y_m \underset{G}{\Rightarrow}^* X_1 X_2...X_k \underset{G}{\Rightarrow}^* w_1 w_2...w_k = w</tex>.

<tex>\Leftarrow</tex> 
Пусть <tex>A \underset{G}{\Rightarrow}^*w</tex>  и  <tex>w \ne \varepsilon</tex>. 
Докажем индукцией по длине порождения в грамматике <tex>G</tex>, что <tex>A \underset{G'}{\Rightarrow}^*w</tex>. 
'''База'''. <tex>A \underset{G}{\Rightarrow} w</tex>. 
Правило <tex>A \rightarrow w</tex> присутствует в <tex>G</tex>. Поскольку <tex>w \ne \varepsilon</tex>, это же правило будет и в <tex>G'</tex>, поэтому <tex>A \underset{G'}{\Rightarrow}^*w</tex>. 
'''Предположение индукции'''. Пусть из <tex>A \underset{G}{\Rightarrow}^*w \ne \varepsilon</tex> менее, чем за <tex>n</tex> шагов, следует, что <tex>A \underset{G'}{\Rightarrow}^*w </tex>. 
'''Переход'''. Пусть в порождении <tex>n</tex> шагов, <tex>n > 1</tex>. Тогда оно имеет вид <tex>A\underset{G}{\Rightarrow}Y_1 Y_2...Y_m \underset{G}{\Rightarrow}^*w</tex>, где <tex>Y_i \in N \cup \Sigma </tex>. Цепочку <tex>w</tex> можно разбить на <tex>w_1 w_2...w_m</tex>, где <tex>Y_i \underset{G}{\Rightarrow}^*w_i</tex>. 
Пусть <tex>Y_{i_1}, Y_{i_2}, ..., Y_{i_p}</tex> — подпоследовательность, состоящая из всех элементов, таких, что <tex>w_{i_k} \ne \varepsilon</tex>, то есть <tex>Y_{i_1} Y_{i_2} ... Y_{i_p} \underset{G}{\Rightarrow}^*w</tex>. <tex>p \ge 1</tex>, поскольку <tex>w \ne \varepsilon</tex>. Значит, <tex>A \rightarrow Y_{i_1} Y_{i_2} ... Y_{i_p}</tex> является правилом в <tex>G'</tex> по построению <tex>G'</tex>. 
Так как каждое из порождений <tex>Y_i \underset{G}{\Rightarrow}^*w_i</tex> содержит менее <tex>n</tex> шагов, к ним можно применить предположение индукции и заключить, что, если <tex>w_i \ne \varepsilon</tex>, то <tex>Y_i \underset{G'}{\Rightarrow}^*w_i</tex>. 
Таким образом, <tex>A \underset{G'}{\Rightarrow} Y_{i_1} Y_{i_2} ... Y_{i_p} \underset{G'}{\Rightarrow}^* w</tex>.

Подставив <tex>S</tex> вместо <tex>A</tex> в утверждение (*), видим, что <tex>w \in L(G)</tex> для <tex>w \ne \varepsilon</tex> тогда и только тогда, когда <tex>w \in L(G')</tex>. Так как после выполнения шага 5 алгоритма в <tex>G'</tex> могло добавиться только пустое слово <tex>\varepsilon</tex>, то язык, задаваемый КС грамматикой <tex>G'</tex>, совпадает с языком, задаваемым КС грамматикой <tex>G</tex>.
}}

=== Время работы алгоритма ===
Рассмотрим грамматику:
<tex> \Gamma =
\begin{array}{l l}
S\rightarrow T_1 T_2 T_3 ... T_n\\
T_1\rightarrow t_1|\varepsilon\\
T_2\rightarrow t_2|\varepsilon\\
...\\
T_n\rightarrow t_n|\varepsilon
\end{array}
</tex>. 
<tex>\left| \Gamma \right| = O(n)</tex>. Из нетерминала <tex>S</tex> можно вывести <tex>2^n</tex> сочетаний нетерминалов <tex>T_i</tex>. Таким образом в худшем случае алгоритм работает за <tex>O(\left| \Gamma \right| ^ 2)</tex>. 
Однако если в грамматике устранены [[Удаление_длинных_правил_из_грамматики|длинные правила]], то алгоритм будет работать за <tex>O(\left| \Gamma \right|)</tex> и добавит в грамматику <tex>O(\left| \Gamma \right|)</tex> новых правил длинны <tex>O(1)</tex>.

=== Пример ===
Рассмотрим грамматику:
<tex>
\begin{array}{l l}
S\rightarrow ABCd\\
A\rightarrow a|\varepsilon\\
B\rightarrow AC\\
C\rightarrow c|\varepsilon
\end{array}
</tex>, в которой <tex>A</tex>, <tex>B</tex> и <tex>C</tex> являются <tex>\varepsilon</tex>-порождающими нетерминалами.
# Переберём для каждого правила все возможные сочетания ε-порождающих нетерминалов и добавим новые правила:
#* <tex>S\rightarrow Ad|ABd|Bd|BCd|Cd|d</tex> для <tex>S \rightarrow ABCd</tex>
#* <tex>B \rightarrow A|C</tex> для <tex>B \rightarrow AC</tex>
# Удалим праила <tex>A\rightarrow \varepsilon</tex> и <tex>C\rightarrow \varepsilon</tex>

В результате мы получим новую грамматику без <tex>\varepsilon</tex>-правил:
<tex>\begin{array}{l l}
S\rightarrow Ad|ABd|ABCd|Bd|BCd|Cd|d\\
A\rightarrow a\\
B\rightarrow A|AC|C\\
C\rightarrow c
\end{array}</tex>

== Алгоритм поиска ε-порождающих нетерминалов ==
'''Вход:''' КС грамматика <tex> G=\langle N,\Sigma, P, S \rangle</tex>. 
'''Выход:''' множество <tex>\varepsilon</tex>-порождающих нетерминалов.

# Найти все <tex>\varepsilon</tex>-правила. Составить множество, состоящее из нетерминалов, входящих в левые части таких правил.
# Перебираем правила грамматики <tex>G</tex>. Если найдено правило <tex>A \rightarrow C_1C_2...C_k</tex>, для которого верно, что каждый <tex>C_i</tex> принадлежит множеству, то добавить <tex>A</tex> в множество.
# Если на шаге 2 множество изменилось, то повторить шаг 2.

=== Доказательство корректности ===
{{Теорема
|statement = Описанный выше алгоритм находит все <tex>\varepsilon</tex>-порождающие нетерминалы грамматики <tex>G</tex>.
|proof =

Для доказательства корректности алгоритма достаточно показать, что, если множество <tex>\varepsilon</tex>-порождающих нетерминалов на очередной итерации алгоритма не изменялось, то алгоритм нашел все <tex>\varepsilon</tex>-порождающие нетерминалы.

Пусть после завершения алгоритма существуют нетерминалы такие, что они являются <tex>\varepsilon</tex>-порождающими, но не были найдены алгоритмом. Выберем из этих нетерминалов нетерминал <tex>B</tex>, из которого выводится <tex>\varepsilon</tex> за наименьшее число шагов. Тогда в грамматике есть правило <tex>B \rightarrow C_1C_2...C_k</tex>, где каждый нетерминал <tex>C_i</tex> — <tex>\varepsilon</tex>-порождающий. Каждый <tex>C_i</tex> входит в множество <tex>\varepsilon</tex>-порождающих нетерминалов, так как иначе вместо <tex>B</tex> необходимо было взять <tex>C_i</tex>. Следовательно, на одной из итераций алгоритма <tex>B</tex> уже добавился в множество <tex>\varepsilon</tex>-порождающих нетерминалов. Противоречие. Следовательно, алгоритм находит все <tex>\varepsilon</tex>-порождающие нетерминалы.
}}

=== Время работы алгоритма ===
Данный алгоритм работает за <tex>O(\left| \Gamma \right| ^ 2)</tex>, однако используя [[Очередь|очередь]] можно ускорить его до <tex>O(\left| \Gamma \right|)</tex>.

=== Пример ===
Рассмотрим грамматику:
<tex>
\begin{array}{l l}
S\rightarrow ABC|DS\\
A\rightarrow \varepsilon\\
B\rightarrow AC\\
C\rightarrow \varepsilon\\
D\rightarrow d
\end{array}
</tex>
# Возьмём множество состоящее из <tex>\varepsilon</tex>-порождающих нетерминалов <tex>\lbrace A, C \rbrace</tex>.
# Добавим <tex>B</tex> в множество, так как правая часть правила <tex>B\rightarrow AC</tex> состоит только из нетерминалов из множества.
# Повторим второй пункт для правила <tex>S\rightarrow ABC</tex> и получим множество <tex>\lbrace A, B, C, S \rbrace</tex>.
# Больше нет нерассмотренных правил, содержащих справа только нетерминалы из множества.

Таким образом <tex>\varepsilon</tex>-порождающими нетерминалами являются <tex>A</tex>, <tex>B</tex>, <tex>C</tex> и <tex>S</tex>.

== См. также ==
* [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|Контекстно-свободные грамматики]]
* [[Нормальная_форма_Хомского|Нормальная форма Хомского]]
* [http://en.wikipedia.org/wiki/Chomsky_normal_form Chomsky normal form]

== Литература ==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — С. 273: ISBN 5-8459-0261-4 (рус.)
[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

Нормальная форма Хомского

2013-11-17T10:41:46Z

91.215.121.216:

{{Определение
|definition=Грамматикой в '''нормальной форме Хомского''' (''Chomsky normal form'') называется [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]], в которой могут содержатся правила только следующего вида:
<tex>A \rightarrow B C </tex>,

<tex>A \rightarrow a </tex>,

<tex>S \rightarrow \varepsilon </tex>,

где <tex> a </tex> {{---}} терминал, <tex> A, B, C </tex> {{---}} нетерминалы, <tex> S </tex> {{---}} стартовая вершина, <tex> \varepsilon </tex> {{---}} пустая строка, стартовая вершина не содержится в правых частях правил.
}}

==Приведение грамматики к нормальной форме Хомского==

{{Теорема
|statement=Любую контекстно-свободную грамматику можно привести к нормальной форме Хомского.
|proof=
Рассмотрим контекстно-свободную грамматику <tex> \Gamma </tex>. Для приведения ее к нормальной форме Хомского необходимо выполнить пять шагов. На каждом шаге мы строим новую <tex> \Gamma_i </tex>, которая допускает тот же язык, что и <tex> \Gamma </tex>.

# Уберём длинные правила.
#: Воспользуемся [[Удаление длинных правил из грамматики|алгоритмом удаления длинных правил]] из грамматики. Получим грамматику <tex> \Gamma_1 </tex>, эквивалентную исходной, содержащую правила длины 0, 1 и 2.
# Удаление <tex> \varepsilon </tex>-правил.
#:Воспользуемся [[Удаление eps-правил из грамматики|алгоритмом удаления <tex> \varepsilon </tex>-правил ]] из грамматики. Получим грамматику <tex> \Gamma_2 </tex>, эквивалентную исходной, но в которой нет <tex>\varepsilon </tex>-правил.
# Удаление цепных правил.
#:Воспользуемся [[Удаление_цепных_правил_из_грамматики| алгоритмом удаления цепных правил]] из грамматики. Алгоритм работает таким образом, что новые <tex> \varepsilon </tex>-правила не образуются. Получим грамматику <tex> \Gamma_3 </tex>, эквивалентную <tex> \Gamma </tex>.
# Удалим бесполезные символы.
#:Воспользуемся [[Удаление бесполезных символов из грамматики| алгоритмом удаления бесполезных символов]] из грамматики. Так как <tex> \Gamma_3 </tex> эквивалентна <tex> \Gamma </tex>, то бесполезные символы не могли перестать быть бесполезными. Более того, мы только удаляем правила, новые <tex>\varepsilon</tex>-правила и цепные правила не могли появиться.
# Уберём ситуации, когда в правиле встречаются несколько терминалов.
#:Для всех правил вида <tex> A \rightarrow u_1 u_2</tex> (где <tex> u_i </tex> {{---}} терминал или нетерминал) заменим все терминалы <tex> u_i </tex> на новые нетерминалы <tex> U_i </tex> и добавим правила <tex> U_i \rightarrow u_i </tex>. Теперь правила содержат либо одиночный терминал, либо строку из двух нетерминалов.
Таким образом, мы получили грамматику в нормальной форме Хомского, которая допускает тот же язык, что и <tex> \Gamma </tex>.

Заметим, что размеры грамматики при таком порядке действий возрастают полиномиально.

При удалении длинных правил из каждого правила длины <tex> k \ge 3 </tex> могло появиться <tex> k-1 </tex> новых правил, причем их длина не превышает двух. На этом шаге размер грамматики возрастает не более, чем вдвое.

При удалении <tex> \varepsilon </tex>-правил из грамматики, содержащей правила длины 0, 1 и 2, размеры грамматики могли вырасти не больше, чем в 3 раза.

Всего цепных правил в грамматике не больше, чем <tex> n^2 </tex>, где <tex> n </tex> {{---}} число нетерминалов. При удалении цепных правил мы берем каждую из цепных пар и производим добавление нецепных правил, выводимых из второго нетерминала в паре. Если максимальная суммарная длина всех правил, выводимых из какого-либо нетерминала, равна <tex> k </tex>, то размер грамматики возрастет не больше, чем на <tex> k \cdot n^2 </tex>.

Наконец, на последнем шаге может произойти добавление не более, чем <tex>|\Sigma|</tex> (<tex>\Sigma</tex> {{---}} алфавит грамматики) новых правил, причем все они будут длины 1.
}}

== Пример ==
Рассмотрим грамматику для языка правильных скобочных последовательностей: <tex>S\rightarrow \varepsilon|(S)|SS</tex>.
# Удалим длинные правила и получим грамматику <tex>
\begin{array}{l l}
S\rightarrow \varepsilon|A)|SS\\
A\rightarrow (S
\end{array}
</tex>.
# Удалим ε правила - <tex>
\begin{array}{l l}
S\rightarrow \varepsilon|S'\\
S'\rightarrow A)|S'S'\\
A\rightarrow (S'|(
\end{array}
</tex>.
# Удалим цепные правила - <tex>
\begin{array}{l l}
S\rightarrow \varepsilon|A)|S'S'\\
S'\rightarrow A)|S'S'\\
A\rightarrow (S'|(
\end{array}
</tex>.
# Заменим терминалы на нетерминалы - <tex>
\begin{array}{l l}
S\rightarrow \varepsilon|AB|S'S'\\
S'\rightarrow AB|S'S'\\
A\rightarrow CS'|(\\
C\rightarrow (\\
B\rightarrow )
\end{array}
</tex>.

== См. также ==
* [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|Контекстно-свободные грамматики]]
* [http://en.wikipedia.org/wiki/Chomsky_normal_form Chomsky normal form]

==Литература==
* http://www.enseignement.polytechnique.fr/informatique/profs/Luc.Maranget/IF/09/chomsky.pdf

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

Удаление длинных правил из грамматики

2013-11-17T10:36:10Z

91.215.121.216:

{{Определение
|definition =
Пусть <tex>\Gamma</tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]].
Правило <tex>A \rightarrow \beta </tex> называется '''длинным''', если <tex>|\beta| > 2</tex>.
}}

== Постановка задачи ==
Пусть <tex>\Gamma</tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]], содержащая длинные правила. Требуется построить эквивалентную грамматику <tex>\Gamma'</tex>, не содержащую длинных правил. 
Задача удаления длинных правил из грамматики возникает при попытке её приведения к [[нормальная форма Хомского|нормальной форме Хомского]].

== Алгоритм ==
С каждым длинным правилом <tex>A \rightarrow a_1 a_2 \ldots a_k</tex>, <tex>k > 2</tex>, <tex>a_i \in \Sigma \cup N</tex> проделаем следующее: 
#Добавим в грамматику <tex>k-2</tex> новых нетерминала <tex>B_1, B_2, \ldots B_{k-2}</tex>. 
#Добавим в грамматику <tex>k-1</tex> новое правило: 
#:<tex>A \rightarrow a_1B_1</tex>, 
#:<tex>B_1 \rightarrow a_2B_2</tex>, 
#:<tex>B_2 \rightarrow a_3B_3</tex>, 
#:<tex>\ldots </tex>, 
#:<tex>B_{k-2} \rightarrow a_{k-1}a_{k}</tex>. 
#Удалим из грамматики правило <tex>A \rightarrow a_1 a_2 \ldots a_k</tex>.
=== Корректность алгоритма ===
{{Теорема
|statement=Пусть <tex>\Gamma</tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]]. <tex>\Gamma'</tex> {{---}} грамматика, полученная в результате применения алгоритма к <tex>\Gamma</tex>. Тогда <tex>L(\Gamma) = L(\Gamma').</tex>
|proof=
<tex>\Rightarrow </tex> 
Покажем, что <tex>L(\Gamma) \subseteq L(\Gamma')</tex>. 
Пусть <tex>w \in L(\Gamma)</tex>. Рассмотрим вывод <tex>w</tex>. Если в выводе используется длинное правило <tex>A \rightarrow a_1 a_2 \ldots a_k</tex>, то заменим его на последовательное применение правил <tex>A \rightarrow a_1B_1</tex>, <tex>B_1 \rightarrow a_2B_2</tex>,
<tex>B_2 \rightarrow a_3B_3</tex>, <tex>\ldots </tex>, <tex>B_{k-2} \rightarrow a_{k-1}a_{k}</tex>. Получим вывод <tex>w</tex> в <tex>\Gamma'</tex>. 
<tex>\Leftarrow </tex> 
Покажем, что <tex>L(\Gamma') \subseteq L(\Gamma)</tex>. 
Допустим, что это не так, то есть <tex>\exists w \in L(\Gamma'), w \notin L(\Gamma)</tex>. 
Рассмотрим вывод <tex>w</tex> в <tex>\Gamma' \cup \Gamma</tex>, минимальный по количеству примененных правил, отсутствующих в <tex>\Gamma</tex>. 
Найдем в этом выводе первое применение некоторого правила <tex>A \rightarrow a_1A_1, a_1 \in \Sigma \cup N</tex>, которого нет в <tex>\Gamma</tex>. В ходе алгоритма оно было получено из некоторого длинного правила <tex>A \rightarrow a_1 a_2 \ldots a_k</tex>. Применим <tex>A \rightarrow a_1 a_2 \ldots a_k</tex> вместо <tex>A \rightarrow a_1A_1</tex> и удалим в выводе все применения правил, полученных из <tex>A \rightarrow a_1 a_2 \ldots a_k</tex>.
Получим вывод <tex>w</tex> в <tex>\Gamma \cup \Gamma'</tex>, в котором меньше применений правил, отсутствующих в <tex>\Gamma</tex>, чем в исходном. Противоречие.
}}

== Время работы алгоритма ==
Данный алгоритм работает за <tex>O(\left| \Gamma \right|)</tex> и добавляет в грамматику <tex>O(\left| \Gamma \right|)</tex> новых правил длинны <tex>O(1)</tex>.

== Пример работы ==
Покажем, как описанный алгоритм будет работать на следующей грамматике: 
<tex>S \rightarrow AB</tex>, 
<tex>A \rightarrow aBcB</tex>, 
<tex>B \rightarrow def</tex>. 

Для правила <tex>A \rightarrow aBcB</tex> вводим 2 новых нетерминала <tex>A_1, A_2</tex> и 3 новых правила: 
<tex>A \rightarrow aA_1</tex>, 
<tex>A_1 \rightarrow BA_2</tex>, 
<tex>A_2 \rightarrow cB</tex>. 

Для правила <tex>B \rightarrow def</tex> вводим 1 новый нетерминал <tex>B_1</tex> и 2 новых правила: 
<tex>B \rightarrow dB_1</tex>, 
<tex>B_1 \rightarrow ef</tex>. 

В итоге полученная грамматика <tex>\Gamma'</tex> будет иметь вид: 
<tex>S \rightarrow AB</tex>, 
<tex>A \rightarrow aA_1</tex>, 
<tex>A_1 \rightarrow BA_2</tex>, 
<tex>A_2 \rightarrow cB</tex>, 
<tex>B \rightarrow dB_1</tex>, 
<tex>B_1 \rightarrow ef</tex>. 

== См. также ==
* [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|Контекстно-свободные грамматики]]
* [[Нормальная_форма_Хомского|Нормальная форма Хомского]]
* [http://en.wikipedia.org/wiki/Chomsky_normal_form Chomsky normal form]

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

Удаление цепных правил из грамматики

2013-11-17T10:18:31Z

91.215.121.216:

{{Определение
|definition=
'''Цепное правило''' (''unit rule'') — правило вида <tex>A\rightarrow B</tex>, где <tex>A</tex> и <tex>B</tex> — нетерминалы.
}}

== Постановка задачи ==
Пусть <tex>\Gamma</tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]], содержащая цепные правила. Требуется построить эквивалентную грамматику <tex>\Gamma'</tex>, не содержащую цепных правил. 
Задача удаления цепных правил из грамматики возникает при попытке её приведения к [[нормальная форма Хомского|нормальной форме Хомского]].

==Алгоритм==
{{Определение
|definition=
'''Цепная пара''' (''unit pair'') — упорядоченная пара <tex>(A,B)</tex>, в которой <tex>A\Rightarrow ^* B</tex>, используя только цепные правила.
}}

Алгоритм удаления цепных правил из грамматики:
#Найти все цепные пары в грамматике <tex>\Gamma</tex>.
#Для каждой цепной пары <tex>(A,B)</tex> добавить в грамматику <tex>\Gamma'</tex> все правила вида <tex>A\rightarrow\alpha</tex>, где <tex>B\rightarrow\alpha</tex> {{---}} нецепное правило из <tex>\Gamma</tex>.
#Удалить все цепные правила

Найти все цепные пары можно по индукции:

'''Базис.''' <tex>(A,A)</tex> {{---}} цепная пара для любого нетерминала, так как <tex>A\Rightarrow ^* A</tex> за ноль шагов.

'''Индукция.''' Если пара <tex>(A,B)</tex> {{---}} цепная, и есть правило <tex>B\rightarrow C</tex>, то <tex>(A,C)</tex> {{---}} цепная пара.

Нетрудно понять, что такой алгоритм найдет все цепные правила грамматики <tex>\Gamma</tex>, и только их.

===Корректность алгоритма===
{{Теорема
|statement=Пусть <tex>\Gamma</tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]]. <tex>\Gamma'</tex> {{---}} грамматика, полученная в результате применения алгоритма к <tex>\Gamma</tex>. Тогда <tex>L(\Gamma) = L(\Gamma').</tex>
|proof=
<tex>\Rightarrow </tex> 
Покажем, что <tex>L(\Gamma) \subseteq L(\Gamma')</tex>. 
Пусть <tex>w\in L(\Gamma)</tex>. Тогда <tex>w</tex> имеет левое порождение <tex>S\overset{*}{\underset{lm}{\Rightarrow}} w</tex>. Где бы в левом порождении ни использовалось цепное правило, нетерминал в правой части становится крайним слева в выводимой цепочке и сразу же заменяется. Таким образом, левое порождение в <tex>\Gamma</tex> можно разбить на последовательность шагов, в которых ноль или несколько цепных правил сопровождаются нецепным. Заметим, что любое нецепное правило, перед которым нет цепных, образует такой шаг. Но по построению <tex>\Gamma'</tex> каждый из этих шагов может быть выполнен одним её правилом. Таким образом, <tex>S\overset{*}{\underset{\Gamma'}{\Rightarrow}} w</tex>, то есть <tex>w\in L(\Gamma')</tex>.

<tex>\Leftarrow </tex> 
Покажем, что <tex>L(\Gamma') \subseteq L(\Gamma)</tex>. 
Пусть <tex>w\in L(\Gamma')</tex>, то есть <tex>S\overset{*}{\underset{\Gamma'}{\Rightarrow}} w</tex>. Так как каждое правило <tex>\Gamma'</tex> эквивалентно последовательности из нуля или нескольких цепных правил <tex>\Gamma</tex>, за которой следует нецепное правило из <tex>\Gamma</tex>, то из <tex>\alpha{\underset{\Gamma'}{\Rightarrow}} \beta</tex> следует <tex>\alpha\overset{*}{\underset{\Gamma}{\Rightarrow}} \beta</tex>. Таким образом, каждый шаг порождения в <tex>\Gamma'</tex> может быть заменен одним или несколькими шагами в <tex>\Gamma</tex>. Собрав эти последовательности шагов, получим, что <tex>S\overset{*}{\underset{\Gamma}{\Rightarrow}} w</tex>, то есть <tex>w\in L(\Gamma)</tex>.

}}

=== Время работы алгоритма ===
Данный алгоритм работает за <tex>O(\left| \Gamma \right| ^ 2)</tex>.

=== Пример ===
Рассмотрим грамматику:
<tex>
\begin{array}{l l}
A\rightarrow B|a\\
B\rightarrow C|b\\
C\rightarrow DD|c
\end{array}</tex>, в которой есть два цепных правила <tex>A\rightarrow B</tex> и <tex>B\rightarrow C</tex>.

# Для каждого нетерминала создадим цепную пару. Теперь множество цепных пар будет состоять из <tex>(A, A)</tex>, <tex>(B, B)</tex>, <tex>(C, C)</tex> и <tex>(D, D)</tex>.
# Рассмотрим цепное правило <tex>A\rightarrow B</tex>. Так как существует цепная пара <tex>(A, A)</tex>, второй элемент которой совпадает с левым нетерминалом из правила, добавим в множество пару <tex>(A, B)</tex>, у которой первый элемент такой же как у найденной, а второй равен правому нетерминалу из текущего правила.
# Повторим второй пункт для правила <tex>B\rightarrow C</tex> и пары <tex>(B, B)</tex>. Теперь множество цепных пар будет состоять из <tex>(A, A)</tex>, <tex>(B, B)</tex>, <tex>(C, C)</tex>, <tex>(D, D)</tex>, <tex>(A, B)</tex> и <tex>(B, C)</tex>.
# Повторим второй пункт для правила <tex>B\rightarrow C</tex> и пары <tex>(A, B)</tex>, и получим множество <tex>\lbrace (A, A), (B, B), (C, C), (D, D), (A, B), (B, C), (A, C)\rbrace</tex>.
# Для каждой пары добавим в <tex>\Gamma'</tex> новые правила:
#* <tex>A\rightarrow b</tex> для <tex>(A, B)</tex>
#* <tex>A\rightarrow c</tex> и <tex>A\rightarrow DD</tex> для <tex>(A, C)</tex>
#* <tex>B\rightarrow c</tex> и <tex>B\rightarrow DD</tex> для <tex>(B, C)</tex>
#* Оставшиеся цепные пары новых правил не добавят.

== См. также ==
* [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|Контекстно-свободные грамматики]]
* [[Нормальная_форма_Хомского|Нормальная форма Хомского]]
* [http://en.wikipedia.org/wiki/Chomsky_normal_form Chomsky normal form]

==Литература==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

Удаление бесполезных символов из грамматики

2013-11-17T09:47:17Z

91.215.121.216: /* Время работы алгоритма */

== Порождающие и непорождающие нетерминалы ==
{{Определение
|definition=
Нетерминал <tex>A</tex> называется '''порождающим''' (''generating''), если из него может быть выведена конечная терминальная цепочка. Иначе он называется '''непорождающим'''.
}}

Очевидно, что если и только если все нетерминалы правой части правила являются порождающими, то порождающим является и нетерминал, стоящий в его левой части. Это позволяет обнаружить непорождающие нетерминалы с помощью следующей процедуры.
# Найти правила, не содержащие нетерминалов в правых частях. Составить множество нетерминалов, встречающихся в левых частях таких правил.
# Если найдено такое правило, что все нетерминалы, стоящие в его правой части, уже входят в множество, то добавить в множество нетерминалы, стоящие в его левой части.
# Если на шаге 2 множество изменилось, повторить шаг 2.
# Получено множество всех порождающих нетерминалов грамматики, а все нетерминалы, не попавшие в него, являются непорождающими.

{{Лемма
|statement=
После удаления из грамматики правил, содержащих непорождающие нетерминалы, язык не изменится.
|proof=
Непорождающие нетерминалы по определению не могли участвовать в выводе какого-либо слова.
}}

=== Время работы алгоритма ===
Данный алгоритм работает за <tex>O(\left| \Gamma \right| ^ 2)</tex>, однако используя [[Очередь|очередь]] можно ускорить его до <tex>O(\left| \Gamma \right|)</tex>.

=== Пример ===
Рассмотрим грамматику:
<tex>
\begin{array}{l l}
S\rightarrow Ac\\
A\rightarrow SD\\
D\rightarrow aD\\
A\rightarrow a
\end{array}
</tex>
# Изначально множество порождающих нетерминалов состоит из одного элемента <tex>A</tex>.
# Добавим в множество нетеминал <tex>S</tex>, так как существует правило <tex>S\rightarrow Ac</tex>, в правой части которого стоят нетерминал <tex>A</tex>, который есть в множестве, и терминал <tex>c</tex>.
# После следуещего обхода правил из грамматики множество не изменится.
# Теперь удалим правила <tex>A\rightarrow SD</tex> и <tex>D\rightarrow aD</tex>, так как они содержит нетерминалы, которых нет в полученном множестве.

== Достижимые и недостижимые нетерминалы ==
{{Определение
|definition=
Нетерминал <tex>A</tex> называется '''достижимым''' (''reachable'') в КС-грамматике <tex>\Gamma</tex>, если существует порождение <tex>S \Rightarrow^* \alpha A \beta</tex>. Иначе он называется '''недостижимым''' (''unreachable'').
}}

Очевидно, что если нетерминал в левой части правила является достижимым, то и все нетерминалы правой части являются достижимыми. Найти недостижимые нетерминалы можно с помощью следующей процедуры.
# Возьмём множество, состоящее из единственного элемента: <tex>\lbrace S \rbrace</tex>.
# Если найдено правило, в левой части которого стоит нетерминал, содержащийся в множестве, добавить в множество все нетерминалы из правой части.
# Если на шаге 2 множество изменилось, повторить шаг 2.
# Получено множество всех достижимых нетерминалов, а нетерминалы, не попавшие в него, являются недостижимыми.

{{Лемма
|statement=
После удаления из грамматики правил, содержащих недостижимые нетерминалы, язык не изменится.
|proof=
Недостижимые нетерминалы по определению не достижимы из стартового, следовательно они не могли участвовать в выводе какого-либо слова.
}}

=== Время работы алгоритма ===
Данный алгоритм работает за <tex>O(\left| \Gamma \right| ^ 2)</tex>, однако используя [[Обход_в_глубину,_цвета_вершин|обход в глубину]] можно ускорить его до <tex>O(\left| \Gamma \right|)</tex>.

=== Пример ===
Рассмотрим грамматику:
<tex>
\begin{array}{l l}
S\rightarrow AB|CD\\
A\rightarrow EF\\
G\rightarrow AD\\
C\rightarrow c

\end{array}
</tex>
# Возьмём множество, состоящее из единственного элемента: <tex>\lbrace S \rbrace</tex>.
# Из <tex>S</tex> достижимы нетерминалы <tex>A</tex>, <tex>B</tex>, <tex>C</tex> и <tex>D</tex>. Добавим их в множество и получим <tex>\lbrace S, A, B, C, D \rbrace</tex>.
# Множество изменилось. Переберём заново правила из грамматики. Из <tex>A</tex> можно вывести <tex>E</tex> и <tex>F</tex>, добавим их в множество.
# Снова переберём правила. Из <tex>C</tex> можно вывести только терминал, а <tex>G</tex> нету в множестве.
# После последнего обхода правил грамматики множество не изменилось, значит мы нашли все достижимые нетерминалы: <tex>\lbrace S, A, B, C, D, E, F \rbrace</tex>.
# Теперь удалим правило <tex>G\rightarrow AD</tex>, так как оно содержит в левой части нетерминал, которого нет в полученном множестве.

== Полезные и бесполезные нетерминалы ==
{{Определение
|definition=
Нетерминал <tex>A</tex> называется '''полезным''' (''useful'') в КС-грамматике <tex>\Gamma</tex>, если он может участвовать в выводе, то есть существует порождение вида <tex>S \Rightarrow ^* \alpha A \beta \Rightarrow ^* w</tex>. Иначе он называется '''бесполезным''' (''useless'').
}}

{{Теорема
|id=th1
|statement=
Грамматика <tex>\Gamma</tex> не содержит бесполезных нетерминалов тогда и только тогда, когда грамматика <tex>\Gamma</tex> не содержит ни недостижимых нетерминалов, ни непорождающих.
|proof=
''Необходимость.'' Очевидно, так как недостижимые и непорождающие нетерминалы являются бесполезными.

''Достаточность.'' Рассмотрим любой нетерминал <tex>A</tex>. Так как он достижим, существуют <tex>\alpha</tex> и <tex>\beta</tex> такие, что <tex>S \Rightarrow ^* \alpha A \beta</tex>. Из того, что любой нетерминал является порождающим, следует, что из любой строки можно вывести строку из терминалов. Значит, существует <tex>\omega \in \Sigma ^ *</tex>: <tex>S \Rightarrow ^* \alpha A \beta \Rightarrow ^* \omega</tex>, и <tex>A</tex> {{---}} не бесполезный.
}}

== Алгоритм удаления бесполезных нетерминалов ==
# Удалить из грамматики правила, содержащие непорождающие нетерминалы.
# Удалить из грамматики правила, содержащие недостижимые нетерминалы.

=== Корректность алгоритма ===
Достаточность данных действий следует из доказанной выше теоремы.

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

Допустим, что в грамматике появился непорождающий нетерминал <tex>A</tex>. Так как до удаления недостижимых нетерминалов существовал вывод из <tex>A</tex> некоторой конечной цепочки терминалов <tex>\omega</tex>, то было удалено хотя бы какое-то одно правило из этого вывода.

Пусть <tex>B\rightarrow\alpha</tex> {{---}} правило, первым из удалённых применяемое в выводе <tex>A \Rightarrow ^* \omega</tex>. Оно могло быть удалено только в том случае, если в <tex>\alpha</tex> присутствуют недостижимые нетерминалы. Но так как было выбрано первое удалённое правило из вывода, то <tex>B</tex> — достижим, следовательно достижимы и все нетерминалы из <tex>\alpha</tex>. Значит, это правило не могло быть удалено.

=== Пример ===

Пусть нам дана грамматика:
<tex>
\begin{array}{l l}
S\rightarrow AS|BS|s \\
E\rightarrow EF|FF \\
A\rightarrow a \\
F\rightarrow f

\end{array}
</tex>. 
Удалим правила, содержащие непорождающие нетерминалы и получим грамматику
<tex>
\begin{array}{l l}
S\rightarrow AS|s \\
E\rightarrow EF|FF \\
A\rightarrow a \\
F\rightarrow f

\end{array}
</tex>. 
Теперь удалим недостижимые нетерминалы и получим грамматику
<tex>
\begin{array}{l l}
S\rightarrow AS|s \\
A\rightarrow a
\end{array}
</tex>.

=== Замечание ===
Шаги алгоритма нельзя менять местами.

Рассмотрим следующую грамматику:
<tex>
\begin{array}{l l}
S\rightarrow AB|a \\
A\rightarrow b
\end{array}.
</tex>
Все нетерминалы в этой грамматике достижимы. Однако, если удалить <tex>B</tex> как непорождающий, то нетерминал <tex>A</tex> станет недостижимым.
== См. также ==
* [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|Контекстно-свободные грамматики]]
* [[Нормальная_форма_Хомского|Нормальная форма Хомского]]
* [http://en.wikipedia.org/wiki/Chomsky_normal_form Chomsky normal form]

== Литература ==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

Удаление бесполезных символов из грамматики

2013-11-16T22:28:59Z

91.215.121.216:

== Порождающие и непорождающие нетерминалы ==
{{Определение
|definition=
Нетерминал <tex>A</tex> называется '''порождающим''' (''generating''), если из него может быть выведена конечная терминальная цепочка. Иначе он называется '''непорождающим'''.
}}

Очевидно, что если и только если все нетерминалы правой части правила являются порождающими, то порождающим является и нетерминал, стоящий в его левой части. Это позволяет обнаружить непорождающие нетерминалы с помощью следующей процедуры.
# Найти правила, не содержащие нетерминалов в правых частях. Составить множество нетерминалов, встречающихся в левых частях таких правил.
# Если найдено такое правило, что все нетерминалы, стоящие в его правой части, уже входят в множество, то добавить в множество нетерминалы, стоящие в его левой части.
# Если на шаге 2 множество изменилось, повторить шаг 2.
# Получено множество всех порождающих нетерминалов грамматики, а все нетерминалы, не попавшие в него, являются непорождающими.

{{Лемма
|statement=
После удаления из грамматики правил, содержащих непорождающие нетерминалы, язык не изменится.
|proof=
Непорождающие нетерминалы по определению не могли участвовать в выводе какого-либо слова.
}}

=== Время работы алгоритма ===
Данный алгоритм работает за <tex>O(\left| \Gamma \right| ^ 2)</tex>, однако, если в грамматике устранены [[Удаление_длинных_правил_из_грамматики|длинные правила]], то используя [[Очередь|очередь]] можно ускорить его до <tex>O(\left| \Gamma \right|)</tex>.

=== Пример ===
Рассмотрим грамматику:
<tex>
\begin{array}{l l}
S\rightarrow Ac\\
A\rightarrow SD\\
D\rightarrow aD\\
A\rightarrow a
\end{array}
</tex>
# Изначально множество порождающих нетерминалов состоит из одного элемента <tex>A</tex>.
# Добавим в множество нетеминал <tex>S</tex>, так как существует правило <tex>S\rightarrow Ac</tex>, в правой части которого стоят нетерминал <tex>A</tex>, который есть в множестве, и терминал <tex>c</tex>.
# После следуещего обхода правил из грамматики множество не изменится.
# Теперь удалим правила <tex>A\rightarrow SD</tex> и <tex>D\rightarrow aD</tex>, так как они содержит нетерминалы, которых нет в полученном множестве.

== Достижимые и недостижимые нетерминалы ==
{{Определение
|definition=
Нетерминал <tex>A</tex> называется '''достижимым''' (''reachable'') в КС-грамматике <tex>\Gamma</tex>, если существует порождение <tex>S \Rightarrow^* \alpha A \beta</tex>. Иначе он называется '''недостижимым''' (''unreachable'').
}}

Очевидно, что если нетерминал в левой части правила является достижимым, то и все нетерминалы правой части являются достижимыми. Найти недостижимые нетерминалы можно с помощью следующей процедуры.
# Возьмём множество, состоящее из единственного элемента: <tex>\lbrace S \rbrace</tex>.
# Если найдено правило, в левой части которого стоит нетерминал, содержащийся в множестве, добавить в множество все нетерминалы из правой части.
# Если на шаге 2 множество изменилось, повторить шаг 2.
# Получено множество всех достижимых нетерминалов, а нетерминалы, не попавшие в него, являются недостижимыми.

{{Лемма
|statement=
После удаления из грамматики правил, содержащих недостижимые нетерминалы, язык не изменится.
|proof=
Недостижимые нетерминалы по определению не достижимы из стартового, следовательно они не могли участвовать в выводе какого-либо слова.
}}

=== Время работы алгоритма ===
Данный алгоритм работает за <tex>O(\left| \Gamma \right| ^ 2)</tex>, однако используя [[Обход_в_глубину,_цвета_вершин|обход в глубину]] можно ускорить его до <tex>O(\left| \Gamma \right|)</tex>.

=== Пример ===
Рассмотрим грамматику:
<tex>
\begin{array}{l l}
S\rightarrow AB|CD\\
A\rightarrow EF\\
G\rightarrow AD\\
C\rightarrow c

\end{array}
</tex>
# Возьмём множество, состоящее из единственного элемента: <tex>\lbrace S \rbrace</tex>.
# Из <tex>S</tex> достижимы нетерминалы <tex>A</tex>, <tex>B</tex>, <tex>C</tex> и <tex>D</tex>. Добавим их в множество и получим <tex>\lbrace S, A, B, C, D \rbrace</tex>.
# Множество изменилось. Переберём заново правила из грамматики. Из <tex>A</tex> можно вывести <tex>E</tex> и <tex>F</tex>, добавим их в множество.
# Снова переберём правила. Из <tex>C</tex> можно вывести только терминал, а <tex>G</tex> нету в множестве.
# После последнего обхода правил грамматики множество не изменилось, значит мы нашли все достижимые нетерминалы: <tex>\lbrace S, A, B, C, D, E, F \rbrace</tex>.
# Теперь удалим правило <tex>G\rightarrow AD</tex>, так как оно содержит в левой части нетерминал, которого нет в полученном множестве.

== Полезные и бесполезные нетерминалы ==
{{Определение
|definition=
Нетерминал <tex>A</tex> называется '''полезным''' (''useful'') в КС-грамматике <tex>\Gamma</tex>, если он может участвовать в выводе, то есть существует порождение вида <tex>S \Rightarrow ^* \alpha A \beta \Rightarrow ^* w</tex>. Иначе он называется '''бесполезным''' (''useless'').
}}

{{Теорема
|id=th1
|statement=
Грамматика <tex>\Gamma</tex> не содержит бесполезных нетерминалов тогда и только тогда, когда грамматика <tex>\Gamma</tex> не содержит ни недостижимых нетерминалов, ни непорождающих.
|proof=
''Необходимость.'' Очевидно, так как недостижимые и непорождающие нетерминалы являются бесполезными.

''Достаточность.'' Рассмотрим любой нетерминал <tex>A</tex>. Так как он достижим, существуют <tex>\alpha</tex> и <tex>\beta</tex> такие, что <tex>S \Rightarrow ^* \alpha A \beta</tex>. Из того, что любой нетерминал является порождающим, следует, что из любой строки можно вывести строку из терминалов. Значит, существует <tex>\omega \in \Sigma ^ *</tex>: <tex>S \Rightarrow ^* \alpha A \beta \Rightarrow ^* \omega</tex>, и <tex>A</tex> {{---}} не бесполезный.
}}

== Алгоритм удаления бесполезных нетерминалов ==
# Удалить из грамматики правила, содержащие непорождающие нетерминалы.
# Удалить из грамматики правила, содержащие недостижимые нетерминалы.

=== Корректность алгоритма ===
Достаточность данных действий следует из доказанной выше теоремы.

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

Допустим, что в грамматике появился непорождающий нетерминал <tex>A</tex>. Так как до удаления недостижимых нетерминалов существовал вывод из <tex>A</tex> некоторой конечной цепочки терминалов <tex>\omega</tex>, то было удалено хотя бы какое-то одно правило из этого вывода.

Пусть <tex>B\rightarrow\alpha</tex> {{---}} правило, первым из удалённых применяемое в выводе <tex>A \Rightarrow ^* \omega</tex>. Оно могло быть удалено только в том случае, если в <tex>\alpha</tex> присутствуют недостижимые нетерминалы. Но так как было выбрано первое удалённое правило из вывода, то <tex>B</tex> — достижим, следовательно достижимы и все нетерминалы из <tex>\alpha</tex>. Значит, это правило не могло быть удалено.

=== Пример ===

Пусть нам дана грамматика:
<tex>
\begin{array}{l l}
S\rightarrow AS|BS|s \\
E\rightarrow EF|FF \\
A\rightarrow a \\
F\rightarrow f

\end{array}
</tex>. 
Удалим правила, содержащие непорождающие нетерминалы и получим грамматику
<tex>
\begin{array}{l l}
S\rightarrow AS|s \\
E\rightarrow EF|FF \\
A\rightarrow a \\
F\rightarrow f

\end{array}
</tex>. 
Теперь удалим недостижимые нетерминалы и получим грамматику
<tex>
\begin{array}{l l}
S\rightarrow AS|s \\
A\rightarrow a
\end{array}
</tex>.

=== Замечание ===
Шаги алгоритма нельзя менять местами.

Рассмотрим следующую грамматику:
<tex>
\begin{array}{l l}
S\rightarrow AB|a \\
A\rightarrow b
\end{array}.
</tex>
Все нетерминалы в этой грамматике достижимы. Однако, если удалить <tex>B</tex> как непорождающий, то нетерминал <tex>A</tex> станет недостижимым.
== См. также ==
* [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|Контекстно-свободные грамматики]]
* [[Нормальная_форма_Хомского|Нормальная форма Хомского]]
* [http://en.wikipedia.org/wiki/Chomsky_normal_form Chomsky normal form]

== Литература ==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

Удаление бесполезных символов из грамматики

2013-10-31T20:43:54Z

91.215.121.216: /* Пример */

== Порождающие и непорождающие нетерминалы ==
{{Определение
|definition=
Нетерминал <tex>A</tex> называется '''порождающим''', если из него может быть выведена конечная терминальная цепочка. Иначе он называется '''непорождающим'''.
}}

Очевидно, что если и только если все нетерминалы правой части являются порождающими, то порождающим является и нетерминал, стоящий в левой части. Это позволяет обнаружить непорождающие нетерминалы с помощью следующей процедуры.
# Найти правила, не содержащие нетерминалов в правых частях. Составить множество нетерминалов, встречающихся в левых частях таких правил.
# Если найдено такое правило, что все нетерминалы, стоящие в его правой части, уже входят в множество, то добавить в множество нетерминалы, стоящие в его левой части.
# Если на шаге 2 множество изменилось, повторить шаг 2.
# Получено множество всех порождающих нетерминалов грамматики, а все нетерминалы, не попавшие в него, являются непорождающими.

{{Лемма
|statement=
После удаления из грамматики правил, содержащих непорождающие нетерминалы, язык не изменится.
|proof=
Непорождающие нетерминалы по определению не могли участвовать в выводе какого-либо слова.
}}

=== Пример ===
Рассмотрим грамматику:
<tex>
\begin{array}{l l}
S\rightarrow Ac\\
A\rightarrow SD\\
A\rightarrow a
\end{array}
</tex>
# Изначально множество порождающих нетерминалов состоит из одного элемента <tex>A</tex>.
# Добавим в множество нетеминал <tex>S</tex>, так как существует правило <tex>S\rightarrow Ac</tex>, в правой части которого стоят нетерминал <tex>B</tex>, который есть в множестве, и терминал <tex>c</tex>.
# После следуещего обхода правил из грамматики множество не изменится.
# Теперь удалим правило <tex>A\rightarrow SD</tex>, так как оно содержит в правой части нетерминал, которого нет в полученном множестве.

== Достижимые и недостижимые нетерминалы ==
{{Определение
|definition=
Нетерминал <tex>A</tex> называется '''достижимым''' в КС-грамматике <tex>\Gamma</tex>, если существует порождение <tex>S \Rightarrow^* \alpha A \beta</tex>. Иначе он называется '''недостижимым'''.
}}

Очевидно, что если нетерминал в левой части правила является достижимым, то и все нетерминалы правой части являются достижимыми. Найти недостижимые нетерминалы можно с помощью следующей процедуры.
# Возьмём множество, состоящее из единственного элемента: <tex>\lbrace S \rbrace</tex>.
# Если найдено правило, в левой части которого стоит нетерминал, содержащийся в множестве, добавить в множество все нетерминалы из правой части.
# Если на шаге 2 множество изменилось, повторить шаг 2.
# Получено множество всех достижимых нетерминалов, а нетерминалы, не попавшие в него, являются недостижимыми.

{{Лемма
|statement=
После удаления из грамматики правил, содержащих недостижимые нетерминалы, язык не изменится.
|proof=
Недостижимые нетерминалы по определению не достижимы из стартового, следовательно они не могли участвовать в выводе какого-либо слова.
}}

=== Пример ===
Рассмотрим грамматику:
<tex>
\begin{array}{l l}
S\rightarrow AB|CD\\
A\rightarrow EF\\
G\rightarrow AD\\
C\rightarrow c

\end{array}
</tex>
# Возьмём множество, состоящее из единственного элемента: <tex>\lbrace S \rbrace</tex>.
# Из <tex>S</tex> достижимы нетерминалы <tex>A</tex>, <tex>B</tex>, <tex>C</tex> и <tex>D</tex>. Добавим их в множество и получим <tex>\lbrace S, A, B, C, D \rbrace</tex>.
# Множество изменилось. Переберём заново правила из грамматики. Из <tex>A</tex> можно вывести <tex>E</tex> и <tex>F</tex>, добавим их в множество.
# Снова переберём правила. Из <tex>C</tex> можно вывести только терминал, а <tex>G</tex> нету в множестве.
# После последнего обхода правил грамматики множество не изменилось, значит мы нашли все достижимые нетерминалы: <tex>\lbrace S, A, B, C, D, E, F \rbrace</tex>.
# Теперь удалим правило <tex>G\rightarrow AD</tex>, так как оно содержит в левой части нетерминал, которого нет в полученном множестве.

== Полезные и бесполезные нетерминалы ==
{{Определение
|definition=
Нетерминал <tex>A</tex> называется '''полезным''' в КС-грамматике <tex>\Gamma</tex>, если он может участвовать в выводе, то есть существует порождение вида <tex>S \Rightarrow ^* \alpha A \beta \Rightarrow ^* w</tex>. Иначе он называется '''бесполезным'''.
}}

{{Теорема
|id=th1
|statement=
Грамматика <tex>\Gamma</tex> не содержит бесполезных нетерминалов тогда и только тогда, когда грамматика <tex>\Gamma</tex> не содержит ни недостижимых нетерминалов, ни непорождающих.
|proof=
''Необходимость.'' Очевидно, так как недостижимые и непорождающие нетерминалы являются бесполезными.

''Достаточность.'' Рассмотрим любой нетерминал <tex>A</tex>. Так как он достижим, существуют <tex>\alpha</tex> и <tex>\beta</tex> такие, что <tex>S \Rightarrow ^* \alpha A \beta</tex>. Из того, что любой нетерминал является порождающим, следует, что из любой строки можно вывести строку из терминалов. Значит, существует <tex>\omega \in \Sigma ^ *</tex>: <tex>S \Rightarrow ^* \alpha A \beta \Rightarrow ^* \omega</tex>, и <tex>A</tex> {{---}} не бесполезный.
}}

== Алгоритм удаления бесполезных нетерминалов ==
# Удалить из грамматики правила, содержащие непорождающие нетерминалы.
# Удалить из грамматики правила, содержащие недостижимые нетерминалы.

=== Корректность алгоритма ===
Достаточность данных действий следует из доказанной выше теоремы.

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

Допустим, что в грамматике появился непорождающий нетерминал <tex>A</tex>. Так как до удаления недостижимых нетерминалов существовал вывод из <tex>A</tex> некоторой конечной цепочки терминалов <tex>\omega</tex>, то было удалено хотя бы какое-то одно правило из этого вывода.

Пусть <tex>B\rightarrow\alpha</tex> {{---}} правило, первым из удалённых применяемое в выводе <tex>A \Rightarrow ^* \omega</tex>. Оно могло быть удалено только в том случае, если в <tex>\alpha</tex> присутствуют недостижимые нетерминалы. Но так как было выбрано первое удалённое правило из вывода, то <tex>B</tex> — достижим, следовательно достижимы и все нетерминалы из <tex>\alpha</tex>. Значит, это правило не могло быть удалено.

=== Пример ===

Пусть нам дана грамматика:
<tex>
\begin{array}{l l}
S\rightarrow AS|BS|s \\
E\rightarrow EF|FF \\
A\rightarrow a \\
F\rightarrow f

\end{array}
</tex>. 
Удалим правила, содержащие непорождающие нетерминалы и получим грамматику
<tex>
\begin{array}{l l}
S\rightarrow AS|s \\
E\rightarrow EF|FF \\
A\rightarrow a \\
F\rightarrow f

\end{array}
</tex>. 
Теперь удалим недостижимые нетерминалы и получим грамматику
<tex>
\begin{array}{l l}
S\rightarrow AS|s \\
A\rightarrow a
\end{array}
</tex>.

=== Замечание ===
Шаги алгоритма нельзя менять местами.

Рассмотрим следующую грамматику:
<tex>
\begin{array}{l l}
S\rightarrow AB|a \\
A\rightarrow b
\end{array}.
</tex>
Все нетерминалы в этой грамматике достижимы. Однако, если удалить <tex>B</tex> как непорождающий, то нетерминал <tex>A</tex> станет недостижимым.

== Литература ==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

Нормальная форма Хомского

2013-10-30T21:04:21Z

91.215.121.216: /* Пример */

==Несколько определений==

{{Определение
|definition=Грамматикой в '''нормальной форме Хомского''' (''Chomsky normal form'') называется [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]], в которой могут содержатся правила только следующего вида:
<tex>A \rightarrow B C </tex>,

<tex>A \rightarrow a </tex>,

<tex>S \rightarrow \varepsilon </tex>,

где <tex> a </tex> {{---}} терминал, <tex> A, B, C </tex> {{---}} нетерминалы, <tex> S </tex> {{---}} стартовая вершина, <tex> \varepsilon </tex> {{---}} пустая строка, стартовая вершина не содержится в правых частях правил.
}}

==Приведение грамматики к нормальной форме Хомского==

{{Теорема
|statement=Любую контекстно-свободную грамматику можно привести к нормальной форме Хомского.
|proof=
Рассмотрим контекстно-свободную грамматику <tex> \Gamma </tex>. Для приведения ее к нормальной форме Хомского необходимо выполнить пять шагов. На каждом шаге мы строим новую <tex> \Gamma_i </tex>, которая допускает тот же язык, что и <tex> \Gamma </tex>.

# Уберём длинные правила.
#: Воспользуемся [[Удаление длинных правил из грамматики|алгоритмом удаления длинных правил]] из грамматики. Получим грамматику <tex> \Gamma_1 </tex>, эквивалентную исходной, содержащую правила длины 0, 1 и 2.
# Удаление <tex> \varepsilon </tex>-правил.
#:Воспользуемся [[Удаление eps-правил из грамматики|алгоритмом удаления <tex> \varepsilon </tex>-правил ]] из грамматики. Получим грамматику <tex> \Gamma_2 </tex>, эквивалентную исходной, но в которой нет <tex>\varepsilon </tex>-правил.
# Удаление цепных правил.
#:Воспользуемся [[Удаление_цепных_правил_из_грамматики| алгоритмом удаления цепных правил]] из грамматики. Алгоритм работает таким образом, что новые <tex> \varepsilon </tex>-правила не образуются. Получим грамматику <tex> \Gamma_3 </tex>, эквивалентную <tex> \Gamma </tex>.
# Удалим бесполезные символы.
#:Воспользуемся [[Удаление бесполезных символов из грамматики| алгоритмом удаления бесполезных символов]] из грамматики. Так как <tex> \Gamma_3 </tex> эквивалентна <tex> \Gamma </tex>, то бесполезные символы не могли перестать быть бесполезными. Более того, мы только удаляем правила, новые <tex>\varepsilon</tex>-правила и цепные правила не могли появиться.
# Уберём ситуации, когда в правиле встречаются несколько терминалов.
#:Для всех правил вида <tex> A \rightarrow u_1 u_2</tex> (где <tex> u_i </tex> {{---}} терминал или нетерминал) заменим все терминалы <tex> u_i </tex> на новые нетерминалы <tex> U_i </tex> и добавим правила <tex> U_i \rightarrow u_i </tex>. Теперь правила содержат либо одиночный терминал, либо строку из двух нетерминалов.
Таким образом, мы получили грамматику в нормальной форме Хомского, которая допускает тот же язык, что и <tex> \Gamma </tex>.

Заметим, что размеры грамматики при таком порядке действий возрастают полиномиально.

При удалении длинных правил из каждого правила длины <tex> k \ge 3 </tex> могло появиться <tex> k-1 </tex> новых правил, причем их длина не превышает двух. На этом шаге размер грамматики возрастает не более, чем вдвое.

При удалении <tex> \varepsilon </tex>-правил из грамматики, содержащей правила длины 0, 1 и 2, размеры грамматики могли вырасти не больше, чем в 3 раза.

Всего цепных правил в грамматике не больше, чем <tex> n^2 </tex>, где <tex> n </tex> {{---}} число нетерминалов. При удалении цепных правил мы берем каждую из цепных пар и производим добавление нецепных правил, выводимых из второго нетерминала в паре. Если максимальная суммарная длина всех правил, выводимых из какого-либо нетерминала, равна <tex> k </tex>, то размер грамматики возрастет не больше, чем на <tex> k \cdot n^2 </tex>.

Наконец, на последнем шаге может произойти добавление не более, чем <tex>|\Sigma|</tex> (<tex>\Sigma</tex> {{---}} алфавит грамматики) новых правил, причем все они будут длины 1.
}}

== Пример ==
Рассмотрим грамматику для языка правильных скобочных последовательностей: <tex>S\rightarrow \varepsilon|``("S``)"|SS</tex>.
# Удалим длинные правила и получим грамматику <tex>
\begin{array}{l l}
S\rightarrow \varepsilon|A``)"|SS\\
A\rightarrow ``("S
\end{array}
</tex>.
# Удалим ε правила - <tex>
\begin{array}{l l}
S\rightarrow \varepsilon|S'\\
S'\rightarrow A``)"|S'S'\\
A\rightarrow ``("S'|``("
\end{array}
</tex>.
# Удалим цепные правила - <tex>
\begin{array}{l l}
S\rightarrow \varepsilon|A``)"|S'S'\\
S'\rightarrow A``)"|S'S'\\
A\rightarrow ``("S'|``("
\end{array}
</tex>.
# Заменим терминалы на нетерминалы - <tex>
\begin{array}{l l}
S\rightarrow \varepsilon|AB|S'S'\\
S'\rightarrow AB|S'S'\\
A\rightarrow CS'|``("\\
C\rightarrow ``("\\
B\rightarrow ``)"
\end{array}
</tex>.

==Литература==
* http://www.enseignement.polytechnique.fr/informatique/profs/Luc.Maranget/IF/09/chomsky.pdf

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

Нормальная форма Хомского

2013-10-30T19:58:54Z

91.215.121.216:

==Несколько определений==

{{Определение
|definition=Грамматикой в '''нормальной форме Хомского''' (''Chomsky normal form'') называется [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]], в которой могут содержатся правила только следующего вида:
<tex>A \rightarrow B C </tex>,

<tex>A \rightarrow a </tex>,

<tex>S \rightarrow \varepsilon </tex>,

где <tex> a </tex> {{---}} терминал, <tex> A, B, C </tex> {{---}} нетерминалы, <tex> S </tex> {{---}} стартовая вершина, <tex> \varepsilon </tex> {{---}} пустая строка, стартовая вершина не содержится в правых частях правил.
}}

==Приведение грамматики к нормальной форме Хомского==

{{Теорема
|statement=Любую контекстно-свободную грамматику можно привести к нормальной форме Хомского.
|proof=
Рассмотрим контекстно-свободную грамматику <tex> \Gamma </tex>. Для приведения ее к нормальной форме Хомского необходимо выполнить пять шагов. На каждом шаге мы строим новую <tex> \Gamma_i </tex>, которая допускает тот же язык, что и <tex> \Gamma </tex>.

# Уберём длинные правила.
#: Воспользуемся [[Удаление длинных правил из грамматики|алгоритмом удаления длинных правил]] из грамматики. Получим грамматику <tex> \Gamma_1 </tex>, эквивалентную исходной, содержащую правила длины 0, 1 и 2.
# Удаление <tex> \varepsilon </tex>-правил.
#:Воспользуемся [[Удаление eps-правил из грамматики|алгоритмом удаления <tex> \varepsilon </tex>-правил ]] из грамматики. Получим грамматику <tex> \Gamma_2 </tex>, эквивалентную исходной, но в которой нет <tex>\varepsilon </tex>-правил.
# Удаление цепных правил.
#:Воспользуемся [[Удаление_цепных_правил_из_грамматики| алгоритмом удаления цепных правил]] из грамматики. Алгоритм работает таким образом, что новые <tex> \varepsilon </tex>-правила не образуются. Получим грамматику <tex> \Gamma_3 </tex>, эквивалентную <tex> \Gamma </tex>.
# Удалим бесполезные символы.
#:Воспользуемся [[Удаление бесполезных символов из грамматики| алгоритмом удаления бесполезных символов]] из грамматики. Так как <tex> \Gamma_3 </tex> эквивалентна <tex> \Gamma </tex>, то бесполезные символы не могли перестать быть бесполезными. Более того, мы только удаляем правила, новые <tex>\varepsilon</tex>-правила и цепные правила не могли появиться.
# Уберём ситуации, когда в правиле встречаются несколько терминалов.
#:Для всех правил вида <tex> A \rightarrow u_1 u_2</tex> (где <tex> u_i </tex> {{---}} терминал или нетерминал) заменим все терминалы <tex> u_i </tex> на новые нетерминалы <tex> U_i </tex> и добавим правила <tex> U_i \rightarrow u_i </tex>. Теперь правила содержат либо одиночный терминал, либо строку из двух нетерминалов.
Таким образом, мы получили грамматику в нормальной форме Хомского, которая допускает тот же язык, что и <tex> \Gamma </tex>.

Заметим, что размеры грамматики при таком порядке действий возрастают полиномиально.

При удалении длинных правил из каждого правила длины <tex> k \ge 3 </tex> могло появиться <tex> k-1 </tex> новых правил, причем их длина не превышает двух. На этом шаге размер грамматики возрастает не более, чем вдвое.

При удалении <tex> \varepsilon </tex>-правил из грамматики, содержащей правила длины 0, 1 и 2, размеры грамматики могли вырасти не больше, чем в 3 раза.

Всего цепных правил в грамматике не больше, чем <tex> n^2 </tex>, где <tex> n </tex> {{---}} число нетерминалов. При удалении цепных правил мы берем каждую из цепных пар и производим добавление нецепных правил, выводимых из второго нетерминала в паре. Если максимальная суммарная длина всех правил, выводимых из какого-либо нетерминала, равна <tex> k </tex>, то размер грамматики возрастет не больше, чем на <tex> k \cdot n^2 </tex>.

Наконец, на последнем шаге может произойти добавление не более, чем <tex>|\Sigma|</tex> (<tex>\Sigma</tex> {{---}} алфавит грамматики) новых правил, причем все они будут длины 1.
}}

== Пример ==
Рассмотрим грамматику для языка правильных скобочных последовательностей: <tex>S\rightarrow \varepsilon|(S)|SS</tex>.

==Литература==
* http://www.enseignement.polytechnique.fr/informatique/profs/Luc.Maranget/IF/09/chomsky.pdf

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

Удаление eps-правил из грамматики

2013-10-30T19:35:22Z

91.215.121.216: /* Алгоритм удаления ε-правил из грамматики */

== Используемые определения ==
{{Определение
|definition = Правила вида <tex>A \to \varepsilon</tex> называются '''<tex>\varepsilon</tex>-правилами'''.
}}
{{Определение
|definition = Нетерминал <tex>A</tex> называется '''<tex>\varepsilon</tex>-порождающим''', если <tex>A \Rightarrow^* \varepsilon</tex>.
}}

== Алгоритм удаления ε-правил из грамматики ==
'''Вход:''' КС грамматика <tex> G=\langle N,\Sigma, P, S \rangle</tex>. 
'''Выход:''' КС грамматика <tex> G'=\langle N,\Sigma, P', S' \rangle</tex> без <tex>\varepsilon</tex>-правил (может присутствовать правило <tex>S \rightarrow \varepsilon</tex>, но в этом случае <tex>S</tex> не встречается в правых частях правил); <tex>L(G') = L(G)</tex>.

# Добавить все правила из <tex>P</tex> в <tex>P'</tex>.
# [[#.D0.90.D0.BB.D0.B3.D0.BE.D1.80.D0.B8.D1.82.D0.BC_.D0.BF.D0.BE.D0.B8.D1.81.D0.BA.D0.B0_.CE.B5-.D0.BF.D0.BE.D1.80.D0.BE.D0.B6.D0.B4.D0.B0.D1.8E.D1.89.D0.B8.D1.85_.D0.BD.D0.B5.D1.82.D0.B5.D1.80.D0.BC.D0.B8.D0.BD.D0.B0.D0.BB.D0.BE.D0.B2 | Найти все <tex>\varepsilon</tex>-порождаюшие нетерминалы]].
# Для каждого правила вида <tex>A \rightarrow \alpha_0 B_1 \alpha_1 B_2 \alpha_2 ... B_k \alpha_k</tex> (где <tex>\alpha_i</tex> — последовательности из терминалов и нетерминалов, <tex>B_j</tex> — <tex>\varepsilon</tex>-порождающие нетерминалы) добавить в <tex>P'</tex> все возможные варианты правил, в которых либо присутствует, либо удалён каждый из нетерминалов <tex>B_j\; (1 \le j \le k)</tex>.
# Удалить все <tex>\varepsilon</tex>-правила из <tex>P'</tex>.
# Если в исходной грамматике <tex>G</tex> выводилось <tex>\varepsilon</tex>, то необходимо добавить новый нетерминал <tex>S'</tex>, сделать его стартовым, добавить правило <tex>S' \rightarrow S|\varepsilon</tex>.

=== Доказательство корректности ===
{{Теорема
|statement = Если грамматика <tex>G'</tex> была построена с помощью описанного выше алгоритма по грамматике <tex>G</tex>, то <tex>L(G') = L(G)</tex>.
|proof =
Сначала докажем, что, если не выполнять шаг 5 алгоритма, то получится грамматика <tex>G' : L(G') = L(G) \setminus \lbrace \varepsilon \rbrace </tex>. 
Для этого достаточно доказать, что
<tex>A \underset{G'}{\Rightarrow}^*w</tex> тогда и только тогда, когда <tex>A \underset{G}{\Rightarrow}^*w</tex> и <tex>w \ne \varepsilon</tex> (*).

<tex>\Rightarrow</tex><br\>
Пусть <tex>A \underset{G'}{\Rightarrow}^*w</tex>  и  <tex>w \ne \varepsilon</tex>. 
Докажем индукцией по длине порождения в грамматике <tex>G'</tex>, что <tex>A \underset{G}{\Rightarrow}^*w</tex>. 
'''База'''. <tex>A \underset{G'}{\Rightarrow} w</tex>. 
В этом случае в <tex>G'</tex> есть правило <tex>A \rightarrow w</tex>. По построению <tex>G'</tex> в <tex>G</tex> есть правило <tex>A \rightarrow \alpha</tex>, причем <tex>\alpha</tex> — цепочка <tex>w</tex>, элементы которой, возможно, перемежаются <tex>\varepsilon</tex>-порождающими нетерминалами. Тогда в <tex>G</tex> есть порождения <tex>A \underset{G}{\Rightarrow} \alpha \underset{G}{\Rightarrow}^*w</tex>. 
'''Предположение индукции'''. Пусть из <tex>A \underset{G'}{\Rightarrow}^*w \ne \varepsilon</tex> менее, чем за <tex>n</tex> шагов, следует, что <tex>A \underset{G}{\Rightarrow}^*w</tex>. 
'''Переход'''.
Пусть в порождении <tex>n</tex> шагов, <tex>n > 1</tex>. Тогда оно имеет вид <tex>A\underset{G'}{\Rightarrow}X_1 X_2...X_k \underset{G'}{\Rightarrow}^*w</tex>, где <tex>X_i \in N \cup \Sigma </tex>. Первое использованное правило должно быть построено по правилу грамматики <tex>G</tex> <tex>A \rightarrow Y_1 Y_2...Y_m</tex>, где последовательность <tex>Y_1 Y_2...Y_m</tex> совпадает с последовательностью <tex>X_1 X_2...X_k</tex>, символы которой, возможно, перемежаются <tex>\varepsilon</tex>-порождающими нетерминалами. 
Цепочку <tex>w</tex> можно разбить на <tex>w_1 w_2...w_k</tex>, где <tex>X_i \underset{G'}{\Rightarrow}^*w_i</tex>. Если <tex>X_i</tex> — терминал, то <tex>w_i = X_i</tex>, a если нетерминал, то порождение <tex>X_i \underset{G'}{\Rightarrow}^*w_i</tex> содержит менее <tex>n</tex> шагов. По предположению <tex>X_i \underset{G}{\Rightarrow}^*w_i</tex>, значит <tex>A \underset {G}{\Rightarrow} Y_1 Y_2...Y_m \underset{G}{\Rightarrow}^* X_1 X_2...X_k \underset{G}{\Rightarrow}^* w_1 w_2...w_k = w</tex>.

<tex>\Leftarrow</tex> 
Пусть <tex>A \underset{G}{\Rightarrow}^*w</tex>  и  <tex>w \ne \varepsilon</tex>. 
Докажем индукцией по длине порождения в грамматике <tex>G</tex>, что <tex>A \underset{G'}{\Rightarrow}^*w</tex>. 
'''База'''. <tex>A \underset{G}{\Rightarrow} w</tex>. 
Правило <tex>A \rightarrow w</tex> присутствует в <tex>G</tex>. Поскольку <tex>w \ne \varepsilon</tex>, это же правило будет и в <tex>G'</tex>, поэтому <tex>A \underset{G'}{\Rightarrow}^*w</tex>. 
'''Предположение индукции'''. Пусть из <tex>A \underset{G}{\Rightarrow}^*w \ne \varepsilon</tex> менее, чем за <tex>n</tex> шагов, следует, что <tex>A \underset{G'}{\Rightarrow}^*w </tex>. 
'''Переход'''. Пусть в порождении <tex>n</tex> шагов, <tex>n > 1</tex>. Тогда оно имеет вид <tex>A\underset{G}{\Rightarrow}Y_1 Y_2...Y_m \underset{G}{\Rightarrow}^*w</tex>, где <tex>Y_i \in N \cup \Sigma </tex>. Цепочку <tex>w</tex> можно разбить на <tex>w_1 w_2...w_m</tex>, где <tex>Y_i \underset{G}{\Rightarrow}^*w_i</tex>. 
Пусть <tex>Y_{i_1}, Y_{i_2}, ..., Y_{i_p}</tex> — подпоследовательность, состоящая из всех элементов, таких, что <tex>w_{i_k} \ne \varepsilon</tex>, то есть <tex>Y_{i_1} Y_{i_2} ... Y_{i_p} \underset{G}{\Rightarrow}^*w</tex>. <tex>p \ge 1</tex>, поскольку <tex>w \ne \varepsilon</tex>. Значит, <tex>A \rightarrow Y_{i_1} Y_{i_2} ... Y_{i_p}</tex> является правилом в <tex>G'</tex> по построению <tex>G'</tex>. 
Так как каждое из порождений <tex>Y_i \underset{G}{\Rightarrow}^*w_i</tex> содержит менее <tex>n</tex> шагов, к ним можно применить предположение индукции и заключить, что, если <tex>w_i \ne \varepsilon</tex>, то <tex>Y_i \underset{G'}{\Rightarrow}^*w_i</tex>. 
Таким образом, <tex>A \underset{G'}{\Rightarrow} Y_{i_1} Y_{i_2} ... Y_{i_p} \underset{G'}{\Rightarrow}^* w</tex>.

Подставив <tex>S</tex> вместо <tex>A</tex> в утверждение (*), видим, что <tex>w \in L(G)</tex> для <tex>w \ne \varepsilon</tex> тогда и только тогда, когда <tex>w \in L(G')</tex>. Так как после выполнения шага 5 алгоритма в <tex>G'</tex> могло добавиться только пустое слово <tex>\varepsilon</tex>, то язык, задаваемый КС грамматикой <tex>G'</tex>, совпадает с языком, задаваемым КС грамматикой <tex>G</tex>.
}}

=== Пример ===
Рассмотрим грамматику:
<tex>
\begin{array}{l l}
S\rightarrow ABCd\\
A\rightarrow a|\varepsilon\\
B\rightarrow AC\\
C\rightarrow c|\varepsilon
\end{array}
</tex>, в которой <tex>A</tex>, <tex>B</tex> и <tex>C</tex> являются ε-порождающими нетерминалами.
# Переберём для каждого правила все возможные сочетания ε-порождающих нетерминалов и добавим новые правила:
#* <tex>S\rightarrow Ad|ABd|Bd|BCd|Cd|d</tex> для <tex>S \rightarrow ABCd</tex>
#* <tex>B \rightarrow A|C</tex> для <tex>B \rightarrow AC</tex>
# Удалим праила <tex>A\rightarrow \varepsilon</tex> и <tex>C\rightarrow \varepsilon</tex>

В результате мы получим новую грамматику без ε правил:
<tex>\begin{array}{l l}
S\rightarrow Ad|ABd|ABCd|Bd|BCd|Cd|d\\
A\rightarrow a\\
B\rightarrow A|AC|C\\
C\rightarrow c
\end{array}</tex>

== Алгоритм поиска ε-порождающих нетерминалов ==
'''Вход:''' КС грамматика <tex> G=\langle N,\Sigma, P, S \rangle</tex>. 
'''Выход:''' множество <tex>\varepsilon</tex>-порождающих нетерминалов.

# Найти все <tex>\varepsilon</tex>-правила. Составить множество, состоящее из нетерминалов, входящих в левые части таких правил.
# Перебираем правила грамматики <tex>G</tex>. Если найдено правило <tex>A \rightarrow C_1C_2...C_k</tex>, для которого верно, что каждый <tex>C_i</tex> принадлежит множеству, то добавить <tex>A</tex> в множество.
# Если на шаге 2 множество изменилось, то повторить шаг 2.

=== Доказательство корректности ===
{{Теорема
|statement = Описанный выше алгоритм находит все <tex>\varepsilon</tex>-порождающие нетерминалы грамматики <tex>G</tex>.
|proof =

Для доказательства корректности алгоритма достаточно показать, что, если множество <tex>\varepsilon</tex>-порождающих нетерминалов на очередной итерации алгоритма не изменялось, то алгоритм нашел все <tex>\varepsilon</tex>-порождающие нетерминалы.

Пусть после завершения алгоритма существуют нетерминалы такие, что они являются <tex>\varepsilon</tex>-порождающими, но не были найдены алгоритмом. Выберем из этих нетерминалов нетерминал <tex>B</tex>, из которого выводится <tex>\varepsilon</tex> за наименьшее число шагов. Тогда в грамматике есть правило <tex>B \rightarrow C_1C_2...C_k</tex>, где каждый нетерминал <tex>C_i</tex> — <tex>\varepsilon</tex>-порождающий. Каждый <tex>C_i</tex> входит в множество <tex>\varepsilon</tex>-порождающих нетерминалов, так как иначе вместо <tex>B</tex> необходимо было взять <tex>C_i</tex>. Следовательно, на одной из итераций алгоритма <tex>B</tex> уже добавился в множество <tex>\varepsilon</tex>-порождающих нетерминалов. Противоречие. Следовательно, алгоритм находит все <tex>\varepsilon</tex>-порождающие нетерминалы.
}}

=== Пример ===
Рассмотрим грамматику:
<tex>
\begin{array}{l l}
S\rightarrow ABC|DS\\
A\rightarrow \varepsilon\\
B\rightarrow AC\\
C\rightarrow \varepsilon\\
D\rightarrow d
\end{array}
</tex>
# Возьмём множество состоящее ε-порождающих нетерминалов <tex>\lbrace A, C \rbrace</tex>.
# Добавим <tex>B</tex> в множество, так как правая часть правила <tex>B\rightarrow AC</tex> состоит только из нетерминалов из множества.
# Повторим второй пункт для правила <tex>S\rightarrow ABC</tex> и получим множество <tex>\lbrace A, B, C, S \rbrace</tex>.
# Больше нету нерассмотренных правил, содержащих справа только нетерминалы из множества.

Таким образом ε-порождающими нетерминалами являются <tex>A</tex>, <tex>B</tex>, <tex>C</tex> и <tex>S</tex>.

== Литература ==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — С. 273: ISBN 5-8459-0261-4 (рус.)
[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

Удаление eps-правил из грамматики

2013-10-30T19:09:29Z

91.215.121.216: /* Алгоритм поиска ε-порождающих нетерминалов */

== Используемые определения ==
{{Определение
|definition = Правила вида <tex>A \to \varepsilon</tex> называются '''<tex>\varepsilon</tex>-правилами'''.
}}
{{Определение
|definition = Нетерминал <tex>A</tex> называется '''<tex>\varepsilon</tex>-порождающим''', если <tex>A \Rightarrow^* \varepsilon</tex>.
}}

== Алгоритм удаления ε-правил из грамматики ==
'''Вход:''' КС грамматика <tex> G=\langle N,\Sigma, P, S \rangle</tex>. 
'''Выход:''' КС грамматика <tex> G'=\langle N,\Sigma, P', S' \rangle</tex> без <tex>\varepsilon</tex>-правил (может присутствовать правило <tex>S \rightarrow \varepsilon</tex>, но в этом случае <tex>S</tex> не встречается в правых частях правил); <tex>L(G') = L(G)</tex>.

# Добавить все правила из <tex>P</tex> в <tex>P'</tex>.
# [[#.D0.90.D0.BB.D0.B3.D0.BE.D1.80.D0.B8.D1.82.D0.BC_.D0.BF.D0.BE.D0.B8.D1.81.D0.BA.D0.B0_.CE.B5-.D0.BF.D0.BE.D1.80.D0.BE.D0.B6.D0.B4.D0.B0.D1.8E.D1.89.D0.B8.D1.85_.D0.BD.D0.B5.D1.82.D0.B5.D1.80.D0.BC.D0.B8.D0.BD.D0.B0.D0.BB.D0.BE.D0.B2 | Найти все <tex>\varepsilon</tex>-порождаюшие нетерминалы]].
# Для каждого правила вида <tex>A \rightarrow \alpha_0 B_1 \alpha_1 B_2 \alpha_2 ... B_k \alpha_k</tex> (где <tex>\alpha_i</tex> — последовательности из терминалов и нетерминалов, <tex>B_j</tex> — <tex>\varepsilon</tex>-порождающие нетерминалы) добавить в <tex>P'</tex> все возможные варианты правил, в которых либо присутствует, либо удалён каждый из нетерминалов <tex>B_j\; (1 \le j \le k)</tex>.
# Удалить все <tex>\varepsilon</tex>-правила из <tex>P'</tex>.
# Если в исходной грамматике <tex>G</tex> выводилось <tex>\varepsilon</tex>, то необходимо добавить новый нетерминал <tex>S'</tex>, сделать его стартовым, добавить правило <tex>S' \rightarrow S|\varepsilon</tex>.

=== Доказательство корректности ===
{{Теорема
|statement = Если грамматика <tex>G'</tex> была построена с помощью описанного выше алгоритма по грамматике <tex>G</tex>, то <tex>L(G') = L(G)</tex>.
|proof =
Сначала докажем, что, если не выполнять шаг 5 алгоритма, то получится грамматика <tex>G' : L(G') = L(G) \setminus \lbrace \varepsilon \rbrace </tex>. 
Для этого достаточно доказать, что
<tex>A \underset{G'}{\Rightarrow}^*w</tex> тогда и только тогда, когда <tex>A \underset{G}{\Rightarrow}^*w</tex> и <tex>w \ne \varepsilon</tex> (*).

<tex>\Rightarrow</tex><br\>
Пусть <tex>A \underset{G'}{\Rightarrow}^*w</tex>  и  <tex>w \ne \varepsilon</tex>. 
Докажем индукцией по длине порождения в грамматике <tex>G'</tex>, что <tex>A \underset{G}{\Rightarrow}^*w</tex>. 
'''База'''. <tex>A \underset{G'}{\Rightarrow} w</tex>. 
В этом случае в <tex>G'</tex> есть правило <tex>A \rightarrow w</tex>. По построению <tex>G'</tex> в <tex>G</tex> есть правило <tex>A \rightarrow \alpha</tex>, причем <tex>\alpha</tex> — цепочка <tex>w</tex>, элементы которой, возможно, перемежаются <tex>\varepsilon</tex>-порождающими нетерминалами. Тогда в <tex>G</tex> есть порождения <tex>A \underset{G}{\Rightarrow} \alpha \underset{G}{\Rightarrow}^*w</tex>. 
'''Предположение индукции'''. Пусть из <tex>A \underset{G'}{\Rightarrow}^*w \ne \varepsilon</tex> менее, чем за <tex>n</tex> шагов, следует, что <tex>A \underset{G}{\Rightarrow}^*w</tex>. 
'''Переход'''.
Пусть в порождении <tex>n</tex> шагов, <tex>n > 1</tex>. Тогда оно имеет вид <tex>A\underset{G'}{\Rightarrow}X_1 X_2...X_k \underset{G'}{\Rightarrow}^*w</tex>, где <tex>X_i \in N \cup \Sigma </tex>. Первое использованное правило должно быть построено по правилу грамматики <tex>G</tex> <tex>A \rightarrow Y_1 Y_2...Y_m</tex>, где последовательность <tex>Y_1 Y_2...Y_m</tex> совпадает с последовательностью <tex>X_1 X_2...X_k</tex>, символы которой, возможно, перемежаются <tex>\varepsilon</tex>-порождающими нетерминалами. 
Цепочку <tex>w</tex> можно разбить на <tex>w_1 w_2...w_k</tex>, где <tex>X_i \underset{G'}{\Rightarrow}^*w_i</tex>. Если <tex>X_i</tex> — терминал, то <tex>w_i = X_i</tex>, a если нетерминал, то порождение <tex>X_i \underset{G'}{\Rightarrow}^*w_i</tex> содержит менее <tex>n</tex> шагов. По предположению <tex>X_i \underset{G}{\Rightarrow}^*w_i</tex>, значит <tex>A \underset {G}{\Rightarrow} Y_1 Y_2...Y_m \underset{G}{\Rightarrow}^* X_1 X_2...X_k \underset{G}{\Rightarrow}^* w_1 w_2...w_k = w</tex>.

<tex>\Leftarrow</tex> 
Пусть <tex>A \underset{G}{\Rightarrow}^*w</tex>  и  <tex>w \ne \varepsilon</tex>. 
Докажем индукцией по длине порождения в грамматике <tex>G</tex>, что <tex>A \underset{G'}{\Rightarrow}^*w</tex>. 
'''База'''. <tex>A \underset{G}{\Rightarrow} w</tex>. 
Правило <tex>A \rightarrow w</tex> присутствует в <tex>G</tex>. Поскольку <tex>w \ne \varepsilon</tex>, это же правило будет и в <tex>G'</tex>, поэтому <tex>A \underset{G'}{\Rightarrow}^*w</tex>. 
'''Предположение индукции'''. Пусть из <tex>A \underset{G}{\Rightarrow}^*w \ne \varepsilon</tex> менее, чем за <tex>n</tex> шагов, следует, что <tex>A \underset{G'}{\Rightarrow}^*w </tex>. 
'''Переход'''. Пусть в порождении <tex>n</tex> шагов, <tex>n > 1</tex>. Тогда оно имеет вид <tex>A\underset{G}{\Rightarrow}Y_1 Y_2...Y_m \underset{G}{\Rightarrow}^*w</tex>, где <tex>Y_i \in N \cup \Sigma </tex>. Цепочку <tex>w</tex> можно разбить на <tex>w_1 w_2...w_m</tex>, где <tex>Y_i \underset{G}{\Rightarrow}^*w_i</tex>. 
Пусть <tex>Y_{i_1}, Y_{i_2}, ..., Y_{i_p}</tex> — подпоследовательность, состоящая из всех элементов, таких, что <tex>w_{i_k} \ne \varepsilon</tex>, то есть <tex>Y_{i_1} Y_{i_2} ... Y_{i_p} \underset{G}{\Rightarrow}^*w</tex>. <tex>p \ge 1</tex>, поскольку <tex>w \ne \varepsilon</tex>. Значит, <tex>A \rightarrow Y_{i_1} Y_{i_2} ... Y_{i_p}</tex> является правилом в <tex>G'</tex> по построению <tex>G'</tex>. 
Так как каждое из порождений <tex>Y_i \underset{G}{\Rightarrow}^*w_i</tex> содержит менее <tex>n</tex> шагов, к ним можно применить предположение индукции и заключить, что, если <tex>w_i \ne \varepsilon</tex>, то <tex>Y_i \underset{G'}{\Rightarrow}^*w_i</tex>. 
Таким образом, <tex>A \underset{G'}{\Rightarrow} Y_{i_1} Y_{i_2} ... Y_{i_p} \underset{G'}{\Rightarrow}^* w</tex>.

Подставив <tex>S</tex> вместо <tex>A</tex> в утверждение (*), видим, что <tex>w \in L(G)</tex> для <tex>w \ne \varepsilon</tex> тогда и только тогда, когда <tex>w \in L(G')</tex>. Так как после выполнения шага 5 алгоритма в <tex>G'</tex> могло добавиться только пустое слово <tex>\varepsilon</tex>, то язык, задаваемый КС грамматикой <tex>G'</tex>, совпадает с языком, задаваемым КС грамматикой <tex>G</tex>.
}}

== Алгоритм поиска ε-порождающих нетерминалов ==
'''Вход:''' КС грамматика <tex> G=\langle N,\Sigma, P, S \rangle</tex>. 
'''Выход:''' множество <tex>\varepsilon</tex>-порождающих нетерминалов.

# Найти все <tex>\varepsilon</tex>-правила. Составить множество, состоящее из нетерминалов, входящих в левые части таких правил.
# Перебираем правила грамматики <tex>G</tex>. Если найдено правило <tex>A \rightarrow C_1C_2...C_k</tex>, для которого верно, что каждый <tex>C_i</tex> принадлежит множеству, то добавить <tex>A</tex> в множество.
# Если на шаге 2 множество изменилось, то повторить шаг 2.

=== Доказательство корректности ===
{{Теорема
|statement = Описанный выше алгоритм находит все <tex>\varepsilon</tex>-порождающие нетерминалы грамматики <tex>G</tex>.
|proof =

Для доказательства корректности алгоритма достаточно показать, что, если множество <tex>\varepsilon</tex>-порождающих нетерминалов на очередной итерации алгоритма не изменялось, то алгоритм нашел все <tex>\varepsilon</tex>-порождающие нетерминалы.

Пусть после завершения алгоритма существуют нетерминалы такие, что они являются <tex>\varepsilon</tex>-порождающими, но не были найдены алгоритмом. Выберем из этих нетерминалов нетерминал <tex>B</tex>, из которого выводится <tex>\varepsilon</tex> за наименьшее число шагов. Тогда в грамматике есть правило <tex>B \rightarrow C_1C_2...C_k</tex>, где каждый нетерминал <tex>C_i</tex> — <tex>\varepsilon</tex>-порождающий. Каждый <tex>C_i</tex> входит в множество <tex>\varepsilon</tex>-порождающих нетерминалов, так как иначе вместо <tex>B</tex> необходимо было взять <tex>C_i</tex>. Следовательно, на одной из итераций алгоритма <tex>B</tex> уже добавился в множество <tex>\varepsilon</tex>-порождающих нетерминалов. Противоречие. Следовательно, алгоритм находит все <tex>\varepsilon</tex>-порождающие нетерминалы.
}}

=== Пример ===
Рассмотрим грамматику:
<tex>
\begin{array}{l l}
S\rightarrow ABC|DS\\
A\rightarrow \varepsilon\\
B\rightarrow AC\\
C\rightarrow \varepsilon\\
D\rightarrow d
\end{array}
</tex>
# Возьмём множество состоящее ε-порождающих нетерминалов <tex>\lbrace A, C \rbrace</tex>.
# Добавим <tex>B</tex> в множество, так как правая часть правила <tex>B\rightarrow AC</tex> состоит только из нетерминалов из множества.
# Повторим второй пункт для правила <tex>S\rightarrow ABC</tex> и получим множество <tex>\lbrace A, B, C, S \rbrace</tex>.
# Больше нету нерассмотренных правил, содержащих справа только нетерминалы из множества.

Таким образом ε-порождающими нетерминалами являются <tex>A</tex>, <tex>B</tex>, <tex>C</tex> и <tex>S</tex>.

== Литература ==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — С. 273: ISBN 5-8459-0261-4 (рус.)
[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

Удаление цепных правил из грамматики

2013-10-30T19:02:22Z

91.215.121.216: /* Пример */

{{Определение
|definition=
'''Цепное правило''' — правило вида <tex>A\rightarrow B</tex>, где <tex>A</tex> и <tex>B</tex> — нетерминалы.
}}

== Постановка задачи ==
Пусть <tex>\Gamma</tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]], содержащая цепные правила. Требуется построить эквивалентную грамматику <tex>\Gamma'</tex>, не содержащую цепных правил. 
Задача удаления цепных правил из грамматики возникает при попытке её приведения к [[нормальная форма Хомского|нормальной форме Хомского]].

==Алгоритм==
{{Определение
|definition=
'''Цепная пара''' — упорядоченная пара <tex>(A,B)</tex>, в которой <tex>A\Rightarrow ^* B</tex>, используя только цепные правила.
}}

Алгоритм удаления цепных правил из грамматики:
#Найти все цепные пары в грамматике <tex>\Gamma</tex>.
#Для каждой цепной пары <tex>(A,B)</tex> добавить в грамматику <tex>\Gamma'</tex> все правила вида <tex>A\rightarrow\alpha</tex>, где <tex>B\rightarrow\alpha</tex> {{---}} нецепное правило из <tex>\Gamma</tex>.
#Удалить все цепные правила

Найти все цепные пары можно по индукции:

'''Базис.''' <tex>(A,A)</tex> {{---}} цепная пара для любого нетерминала, так как <tex>A\Rightarrow ^* A</tex> за ноль шагов.

'''Индукция.''' Если пара <tex>(A,B)</tex> {{---}} цепная, и есть правило <tex>B\rightarrow C</tex>, то <tex>(A,C)</tex> {{---}} цепная пара.

Нетрудно понять, что такой алгоритм найдет все цепные правила грамматики <tex>\Gamma</tex>, и только их.

===Корректность алгоритма===
{{Теорема
|statement=Пусть <tex>\Gamma</tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]]. <tex>\Gamma'</tex> {{---}} грамматика, полученная в результате применения алгоритма к <tex>\Gamma</tex>. Тогда <tex>L(\Gamma) = L(\Gamma').</tex>
|proof=
<tex>\Rightarrow </tex> 
Покажем, что <tex>L(\Gamma) \subseteq L(\Gamma')</tex>. 
Пусть <tex>w\in L(\Gamma)</tex>. Тогда <tex>w</tex> имеет левое порождение <tex>S\overset{*}{\underset{lm}{\Rightarrow}} w</tex>. Где бы в левом порождении ни использовалось цепное правило, нетерминал в правой части становится крайним слева в выводимой цепочке и сразу же заменяется. Таким образом, левое порождение в <tex>\Gamma</tex> можно разбить на последовательность шагов, в которых ноль или несколько цепных правил сопровождаются нецепным. Заметим, что любое нецепное правило, перед которым нет цепных, образует такой шаг. Но по построению <tex>\Gamma'</tex> каждый из этих шагов может быть выполнен одним её правилом. Таким образом, <tex>S\overset{*}{\underset{\Gamma'}{\Rightarrow}} w</tex>, то есть <tex>w\in L(\Gamma')</tex>.

<tex>\Leftarrow </tex> 
Покажем, что <tex>L(\Gamma') \subseteq L(\Gamma)</tex>. 
Пусть <tex>w\in L(\Gamma')</tex>, то есть <tex>S\overset{*}{\underset{\Gamma'}{\Rightarrow}} w</tex>. Так как каждое правило <tex>\Gamma'</tex> эквивалентно последовательности из нуля или нескольких цепных правил <tex>\Gamma</tex>, за которой следует нецепное правило из <tex>\Gamma</tex>, то из <tex>\alpha{\underset{\Gamma'}{\Rightarrow}} \beta</tex> следует <tex>\alpha\overset{*}{\underset{\Gamma}{\Rightarrow}} \beta</tex>. Таким образом, каждый шаг порождения в <tex>\Gamma'</tex> может быть заменен одним или несколькими шагами в <tex>\Gamma</tex>. Собрав эти последовательности шагов, получим, что <tex>S\overset{*}{\underset{\Gamma}{\Rightarrow}} w</tex>, то есть <tex>w\in L(\Gamma)</tex>.

}}

=== Пример ===
Рассмотрим грамматику:
<tex>
\begin{array}{l l}
A\rightarrow B|a\\
B\rightarrow C|b\\
C\rightarrow DD|c
\end{array}</tex>

# В этой грамматике два цепных правила <tex>A\rightarrow B</tex> и <tex>B\rightarrow C</tex>. Для каждого такого правила создадим цепную пару. Теперь множество цепных пар будет состоять из <tex>(A, A)</tex> и <tex>(B, B)</tex>.
# Рассмотрим цепное правило <tex>A\rightarrow B</tex>. Так как существует цепная пара <tex>(A, A)</tex>, второй элемент которой совпадает с левым нетерминалом из правила, добавим в множество пару <tex>(A, B)</tex>, у которой первый элемент такой же как у найденной, а второй равен правому нетерминалу из текущего правила.
# Повторим второй пункт для правила <tex>B\rightarrow C</tex> и пары <tex>(B, B)</tex>. Теперь множество цепных пар будет состоять из <tex>(A, A)</tex>, <tex>(B, B)</tex>, <tex>(A, B)</tex> и <tex>(B, C)</tex>.
# Повторим второй пункт для правила <tex>B\rightarrow C</tex> и пары <tex>(A, B)</tex>, и получим множество <tex>\lbrace (A, A), (A, B), (A, C), (B, B), (B, C) \rbrace</tex>.
# Для каждой пары добавим в <tex>\Gamma'</tex> новые правила:
#* <tex>A\rightarrow b</tex> для <tex>(A, B)</tex>
#* <tex>A\rightarrow c</tex> и <tex>A\rightarrow DD</tex> для <tex>(A, C)</tex>
#* <tex>B\rightarrow c</tex> и <tex>B\rightarrow DD</tex> для <tex>(B, C)</tex>
#* Пары <tex>(A, A)</tex> и <tex>(B, B)</tex> новых правил не добавят.

==Литература==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

Удаление цепных правил из грамматики

2013-10-30T18:43:55Z

91.215.121.216: /* Пример */

{{Определение
|definition=
'''Цепное правило''' — правило вида <tex>A\rightarrow B</tex>, где <tex>A</tex> и <tex>B</tex> — нетерминалы.
}}

== Постановка задачи ==
Пусть <tex>\Gamma</tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]], содержащая цепные правила. Требуется построить эквивалентную грамматику <tex>\Gamma'</tex>, не содержащую цепных правил. 
Задача удаления цепных правил из грамматики возникает при попытке её приведения к [[нормальная форма Хомского|нормальной форме Хомского]].

==Алгоритм==
{{Определение
|definition=
'''Цепная пара''' — упорядоченная пара <tex>(A,B)</tex>, в которой <tex>A\Rightarrow ^* B</tex>, используя только цепные правила.
}}

Алгоритм удаления цепных правил из грамматики:
#Найти все цепные пары в грамматике <tex>\Gamma</tex>.
#Для каждой цепной пары <tex>(A,B)</tex> добавить в грамматику <tex>\Gamma'</tex> все правила вида <tex>A\rightarrow\alpha</tex>, где <tex>B\rightarrow\alpha</tex> {{---}} нецепное правило из <tex>\Gamma</tex>.
#Удалить все цепные правила

Найти все цепные пары можно по индукции:

'''Базис.''' <tex>(A,A)</tex> {{---}} цепная пара для любого нетерминала, так как <tex>A\Rightarrow ^* A</tex> за ноль шагов.

'''Индукция.''' Если пара <tex>(A,B)</tex> {{---}} цепная, и есть правило <tex>B\rightarrow C</tex>, то <tex>(A,C)</tex> {{---}} цепная пара.

Нетрудно понять, что такой алгоритм найдет все цепные правила грамматики <tex>\Gamma</tex>, и только их.

===Корректность алгоритма===
{{Теорема
|statement=Пусть <tex>\Gamma</tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]]. <tex>\Gamma'</tex> {{---}} грамматика, полученная в результате применения алгоритма к <tex>\Gamma</tex>. Тогда <tex>L(\Gamma) = L(\Gamma').</tex>
|proof=
<tex>\Rightarrow </tex> 
Покажем, что <tex>L(\Gamma) \subseteq L(\Gamma')</tex>. 
Пусть <tex>w\in L(\Gamma)</tex>. Тогда <tex>w</tex> имеет левое порождение <tex>S\overset{*}{\underset{lm}{\Rightarrow}} w</tex>. Где бы в левом порождении ни использовалось цепное правило, нетерминал в правой части становится крайним слева в выводимой цепочке и сразу же заменяется. Таким образом, левое порождение в <tex>\Gamma</tex> можно разбить на последовательность шагов, в которых ноль или несколько цепных правил сопровождаются нецепным. Заметим, что любое нецепное правило, перед которым нет цепных, образует такой шаг. Но по построению <tex>\Gamma'</tex> каждый из этих шагов может быть выполнен одним её правилом. Таким образом, <tex>S\overset{*}{\underset{\Gamma'}{\Rightarrow}} w</tex>, то есть <tex>w\in L(\Gamma')</tex>.

<tex>\Leftarrow </tex> 
Покажем, что <tex>L(\Gamma') \subseteq L(\Gamma)</tex>. 
Пусть <tex>w\in L(\Gamma')</tex>, то есть <tex>S\overset{*}{\underset{\Gamma'}{\Rightarrow}} w</tex>. Так как каждое правило <tex>\Gamma'</tex> эквивалентно последовательности из нуля или нескольких цепных правил <tex>\Gamma</tex>, за которой следует нецепное правило из <tex>\Gamma</tex>, то из <tex>\alpha{\underset{\Gamma'}{\Rightarrow}} \beta</tex> следует <tex>\alpha\overset{*}{\underset{\Gamma}{\Rightarrow}} \beta</tex>. Таким образом, каждый шаг порождения в <tex>\Gamma'</tex> может быть заменен одним или несколькими шагами в <tex>\Gamma</tex>. Собрав эти последовательности шагов, получим, что <tex>S\overset{*}{\underset{\Gamma}{\Rightarrow}} w</tex>, то есть <tex>w\in L(\Gamma)</tex>.

}}

=== Пример ===
Рассмотрим грамматику:
<tex>
\begin{array}{l l}
A\rightarrow B|a\\
B\rightarrow C|b\\
C\rightarrow DD|c
\end{array}</tex>

# В этой грамматике два цепных правила <tex>A\rightarrow B</tex> и <tex>B\rightarrow C</tex>. Для каждого такого правила создадим цепную пару. Теперь множество цепных пар будет состоять из <tex>(A, A)</tex> и <tex>(B, B)</tex>.
# Рассмотрим цепное правило <tex>A\rightarrow B</tex>. Так как существует цепная пара <tex>(A, A)</tex>, второй элемент которой совпадает с левым нетерминалом из правила, добавим в множество пару <tex>(A, B)</tex>, у которой первый элемент такой же как у найденной, а второй равен правому нетерминалу из текущего правила.
# Повторим второй пункт для правила <tex>B\rightarrow C</tex> и пары <tex>(B, B)</tex>. Теперь множество цепных пар будет состоять из <tex>(A, A)</tex>, <tex>(B, B)</tex>, <tex>(A, B)</tex> и <tex>(B, C)</tex>.
# Повторим второй пункт для правила <tex>B\rightarrow C</tex> и пары <tex>(A, B)</tex>, и получем множество <tex>\lbrace (A, A), (A, B), (A, C), (B, B), (B, C) \rbrace</tex>.
# Для каждой пары добавим в <tex>\Gamma'</tex> новые правила:
#* <tex>A\rightarrow b</tex> для <tex>(A, B)</tex>
#* <tex>A\rightarrow c</tex> и <tex>A\rightarrow DD</tex> для <tex>(A, C)</tex>
#* <tex>B\rightarrow c</tex> и <tex>B\rightarrow DD</tex> для <tex>(B, C)</tex>
#* Пары <tex>(A, A)</tex> и <tex>(B, B)</tex> новых правил не добавят.

==Литература==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

Удаление цепных правил из грамматики

2013-10-30T18:24:55Z

91.215.121.216: /* Алгоритм */

{{Определение
|definition=
'''Цепное правило''' — правило вида <tex>A\rightarrow B</tex>, где <tex>A</tex> и <tex>B</tex> — нетерминалы.
}}

== Постановка задачи ==
Пусть <tex>\Gamma</tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]], содержащая цепные правила. Требуется построить эквивалентную грамматику <tex>\Gamma'</tex>, не содержащую цепных правил. 
Задача удаления цепных правил из грамматики возникает при попытке её приведения к [[нормальная форма Хомского|нормальной форме Хомского]].

==Алгоритм==
{{Определение
|definition=
'''Цепная пара''' — упорядоченная пара <tex>(A,B)</tex>, в которой <tex>A\Rightarrow ^* B</tex>, используя только цепные правила.
}}

Алгоритм удаления цепных правил из грамматики:
#Найти все цепные пары в грамматике <tex>\Gamma</tex>.
#Для каждой цепной пары <tex>(A,B)</tex> добавить в грамматику <tex>\Gamma'</tex> все правила вида <tex>A\rightarrow\alpha</tex>, где <tex>B\rightarrow\alpha</tex> {{---}} нецепное правило из <tex>\Gamma</tex>.
#Удалить все цепные правила

Найти все цепные пары можно по индукции:

'''Базис.''' <tex>(A,A)</tex> {{---}} цепная пара для любого нетерминала, так как <tex>A\Rightarrow ^* A</tex> за ноль шагов.

'''Индукция.''' Если пара <tex>(A,B)</tex> {{---}} цепная, и есть правило <tex>B\rightarrow C</tex>, то <tex>(A,C)</tex> {{---}} цепная пара.

Нетрудно понять, что такой алгоритм найдет все цепные правила грамматики <tex>\Gamma</tex>, и только их.

===Корректность алгоритма===
{{Теорема
|statement=Пусть <tex>\Gamma</tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]]. <tex>\Gamma'</tex> {{---}} грамматика, полученная в результате применения алгоритма к <tex>\Gamma</tex>. Тогда <tex>L(\Gamma) = L(\Gamma').</tex>
|proof=
<tex>\Rightarrow </tex> 
Покажем, что <tex>L(\Gamma) \subseteq L(\Gamma')</tex>. 
Пусть <tex>w\in L(\Gamma)</tex>. Тогда <tex>w</tex> имеет левое порождение <tex>S\overset{*}{\underset{lm}{\Rightarrow}} w</tex>. Где бы в левом порождении ни использовалось цепное правило, нетерминал в правой части становится крайним слева в выводимой цепочке и сразу же заменяется. Таким образом, левое порождение в <tex>\Gamma</tex> можно разбить на последовательность шагов, в которых ноль или несколько цепных правил сопровождаются нецепным. Заметим, что любое нецепное правило, перед которым нет цепных, образует такой шаг. Но по построению <tex>\Gamma'</tex> каждый из этих шагов может быть выполнен одним её правилом. Таким образом, <tex>S\overset{*}{\underset{\Gamma'}{\Rightarrow}} w</tex>, то есть <tex>w\in L(\Gamma')</tex>.

<tex>\Leftarrow </tex> 
Покажем, что <tex>L(\Gamma') \subseteq L(\Gamma)</tex>. 
Пусть <tex>w\in L(\Gamma')</tex>, то есть <tex>S\overset{*}{\underset{\Gamma'}{\Rightarrow}} w</tex>. Так как каждое правило <tex>\Gamma'</tex> эквивалентно последовательности из нуля или нескольких цепных правил <tex>\Gamma</tex>, за которой следует нецепное правило из <tex>\Gamma</tex>, то из <tex>\alpha{\underset{\Gamma'}{\Rightarrow}} \beta</tex> следует <tex>\alpha\overset{*}{\underset{\Gamma}{\Rightarrow}} \beta</tex>. Таким образом, каждый шаг порождения в <tex>\Gamma'</tex> может быть заменен одним или несколькими шагами в <tex>\Gamma</tex>. Собрав эти последовательности шагов, получим, что <tex>S\overset{*}{\underset{\Gamma}{\Rightarrow}} w</tex>, то есть <tex>w\in L(\Gamma)</tex>.

}}

=== Пример ===
Рассмотрим грамматику:
<tex>
\begin{array}{l l}
A\rightarrow B|a\\
B\rightarrow C|b\\
C\rightarrow DD|c
\end{array}</tex>

# В этой грамматике два цепных правила <tex>A\rightarrow B</tex> и <tex>B\rightarrow C</tex>. Для каждого такого правила создадим цепную пару. Теперь множество цепных пар будет состоять из <tex>(A, A)</tex> и <tex>(B, B)</tex>.
# Рассмотрим цепное правило <tex>A\rightarrow B</tex>. Так как существует цепная пара <tex>(A, A)</tex>, второй элемент которой совпадает с левым нетерминалом из правила, добавим в множество пару <tex>(A, B)</tex>, у которой первый элемент такой же как у найденной, а второй равен правому нетерминалу из текущего правила.
# Повторим второй пункт для правила <tex>B\rightarrow C</tex> и пары <tex>(B, B)</tex>. Теперь множество цепных пар будет состоять из <tex>(A, A)</tex>, <tex>(B, B)</tex>, <tex>(A, B)</tex> и <tex>(B, C)</tex>.
# Повторим второй пункт для правила <tex>B\rightarrow C</tex> и пары <tex>(A, B)</tex>, и получем множество <tex>\lbrace (A, A), (A, B), (A, C), (B, B), (B, C) \rbrace</tex>.
# Для каждой пары добавим в <tex>\Gamma'</tex> новые правила:
#* <tex>A\rightarrow a</tex> для <tex>(A, A)</tex>
#* <tex>A\rightarrow b</tex> для <tex>(A, B)</tex>
#* <tex>A\rightarrow c</tex> и <tex>A\rightarrow DD</tex> для <tex>(A, C)</tex>
#* <tex>B\rightarrow b</tex> для <tex>(B, B)</tex>
#* <tex>B\rightarrow c</tex> и <tex>B\rightarrow DD</tex> для <tex>(B, C)</tex>
#* <tex>C\rightarrow c</tex> и <tex>C\rightarrow DD</tex> для <tex>(C, C)</tex>

==Литература==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

Удаление бесполезных символов из грамматики

2013-10-30T16:45:43Z

91.215.121.216: /* Порождающие и непорождающие нетерминалы */

== Порождающие и непорождающие нетерминалы ==
{{Определение
|definition=
Нетерминал <tex>A</tex> называется '''порождающим''', если из него может быть выведена конечная терминальная цепочка. Иначе он называется '''непорождающим'''.
}}

Очевидно, что если и только если все нетерминалы правой части являются порождающими, то порождающим является и нетерминал, стоящий в левой части. Это позволяет обнаружить непорождающие нетерминалы с помощью следующей процедуры.
# Найти правила, не содержащие нетерминалов в правых частях. Составить множество нетерминалов, встречающихся в левых частях таких правил.
# Если найдено такое правило, что все нетерминалы, стоящие в его правой части, уже входят в множество, то добавить в множество нетерминалы, стоящие в его левой части.
# Если на шаге 2 множество изменилось, повторить шаг 2.
# Получено множество всех порождающих нетерминалов грамматики, а все нетерминалы, не попавшие в него, являются непорождающими.

{{Лемма
|statement=
После удаления из грамматики правил, содержащих непорождающие нетерминалы, язык не изменится.
|proof=
Непорождающие нетерминалы по определению не могли участвовать в выводе какого-либо слова.
}}

=== Пример ===
Рассмотрим грамматику:
<tex>
\begin{array}{l l}
S\rightarrow Ac|Bc\\
A\rightarrow SD\\
A\rightarrow a\\
B\rightarrow b
\end{array}
</tex>
# Изначально множество порождающих нетерминалов состоит из одного элемента <tex>B</tex>. Нетерминал <tex>A</tex> нам не подходит, так как из него можно вывести нетерминалы <tex>S</tex> и <tex>D</tex>.
# Добавим в множество нетеминал <tex>S</tex>, так как существует правило <tex>S\rightarrow Bc</tex>, в правой части которого стоят нетерминал <tex>B</tex>, который есть в множестве, и терминал <tex>c</tex>.
# После следуещего обхода правил из грамматики множество не изменится.
# Теперь удалим правило <tex>S\rightarrow Ac</tex>, так как оно содержит в правой части нетерминал, которого нет в полученном множестве.

== Достижимые и недостижимые нетерминалы ==
{{Определение
|definition=
Нетерминал <tex>A</tex> называется '''достижимым''' в КС-грамматике <tex>\Gamma</tex>, если существует порождение <tex>S \Rightarrow^* \alpha A \beta</tex>. Иначе он называется '''недостижимым'''.
}}

Очевидно, что если нетерминал в левой части правила является достижимым, то и все нетерминалы правой части являются достижимыми. Найти недостижимые нетерминалы можно с помощью следующей процедуры.
# Возьмём множество, состоящее из единственного элемента: <tex>\lbrace S \rbrace</tex>.
# Если найдено правило, в левой части которого стоит нетерминал, содержащийся в множестве, добавить в множество все нетерминалы из правой части.
# Если на шаге 2 множество изменилось, повторить шаг 2.
# Получено множество всех достижимых нетерминалов, а нетерминалы, не попавшие в него, являются недостижимыми.

{{Лемма
|statement=
После удаления из грамматики правил, содержащих недостижимые нетерминалы, язык не изменится.
|proof=
Недостижимые нетерминалы по определению не достижимы из стартового, следовательно они не могли участвовать в выводе какого-либо слова.
}}

=== Пример ===
Рассмотрим грамматику:
<tex>
\begin{array}{l l}
S\rightarrow AB|CD\\
A\rightarrow EF\\
G\rightarrow AD\\
C\rightarrow c

\end{array}
</tex>
# Возьмём множество, состоящее из единственного элемента: <tex>\lbrace S \rbrace</tex>.
# Из <tex>S</tex> достижимы нетерминалы <tex>A</tex>, <tex>B</tex>, <tex>C</tex> и <tex>D</tex>. Добавим их в множество и получим <tex>\lbrace S, A, B, C, D \rbrace</tex>.
# Множество изменилось. Переберём заново правила из грамматики. Из <tex>A</tex> можно вывести <tex>E</tex> и <tex>F</tex>, добавим их в множество.
# Снова переберём правила. Из <tex>C</tex> можно вывести только терминал, а <tex>G</tex> нету в множестве.
# После последнего обхода правил грамматики множество не изменилось, значит мы нашли все достижимые нетерминалы: <tex>\lbrace S, A, B, C, D, E, F \rbrace</tex>.
# Теперь удалим правило <tex>G\rightarrow AD</tex>, так как оно содержит в левой части нетерминал, которого нет в полученном множестве.

== Полезные и бесполезные нетерминалы ==
{{Определение
|definition=
Нетерминал <tex>A</tex> называется '''полезным''' в КС-грамматике <tex>\Gamma</tex>, если он может участвовать в выводе, то есть существует порождение вида <tex>S \Rightarrow ^* \alpha A \beta \Rightarrow ^* w</tex>. Иначе он называется '''бесполезным'''.
}}

{{Теорема
|id=th1
|statement=
Грамматика <tex>\Gamma</tex> не содержит бесполезных нетерминалов тогда и только тогда, когда грамматика <tex>\Gamma</tex> не содержит ни недостижимых нетерминалов, ни непорождающих.
|proof=
''Необходимость.'' Очевидно, так как недостижимые и непорождающие нетерминалы являются бесполезными.

''Достаточность.'' Рассмотрим любой нетерминал <tex>A</tex>. Так как он достижим, существуют <tex>\alpha</tex> и <tex>\beta</tex> такие, что <tex>S \Rightarrow ^* \alpha A \beta</tex>. Из того, что любой нетерминал является порождающим, следует, что из любой строки можно вывести строку из терминалов. Значит, существует <tex>\omega \in \Sigma ^ *</tex>: <tex>S \Rightarrow ^* \alpha A \beta \Rightarrow ^* \omega</tex>, и <tex>A</tex> {{---}} не бесполезный.
}}

== Алгоритм удаления бесполезных нетерминалов ==
# Удалить из грамматики правила, содержащие непорождающие нетерминалы.
# Удалить из грамматики правила, содержащие недостижимые нетерминалы.

=== Корректность алгоритма ===
Достаточность данных действий следует из доказанной выше теоремы.

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

Допустим, что в грамматике появился непорождающий нетерминал <tex>A</tex>. Так как до удаления недостижимых нетерминалов существовал вывод из <tex>A</tex> некоторой конечной цепочки терминалов <tex>\omega</tex>, то было удалено хотя бы какое-то одно правило из этого вывода.

Пусть <tex>B\rightarrow\alpha</tex> {{---}} правило, первым из удалённых применяемое в выводе <tex>A \Rightarrow ^* \omega</tex>. Оно могло быть удалено только в том случае, если в <tex>\alpha</tex> присутствуют недостижимые нетерминалы. Но так как было выбрано первое удалённое правило из вывода, то <tex>B</tex> — достижим, следовательно достижимы и все нетерминалы из <tex>\alpha</tex>. Значит, это правило не могло быть удалено.

=== Пример ===

Пусть нам дана грамматика:
<tex>
\begin{array}{l l}
S\rightarrow AS|BS|s \\
E\rightarrow EF|FF \\
A\rightarrow a \\
F\rightarrow f

\end{array}
</tex>. 
Удалим правила, содержащие непорождающие нетерминалы и получим грамматику
<tex>
\begin{array}{l l}
S\rightarrow AS|s \\
E\rightarrow EF|FF \\
A\rightarrow a \\
F\rightarrow f

\end{array}
</tex>. 
Теперь удалим недостижимые нетерминалы и получим грамматику
<tex>
\begin{array}{l l}
S\rightarrow AS|s \\
A\rightarrow a
\end{array}
</tex>.

=== Замечание ===
Шаги алгоритма нельзя менять местами.

Рассмотрим следующую грамматику:
<tex>
\begin{array}{l l}
S\rightarrow AB|a \\
A\rightarrow b
\end{array}.
</tex>
Все нетерминалы в этой грамматике достижимы. Однако, если удалить <tex>B</tex> как непорождающий, то нетерминал <tex>A</tex> станет недостижимым.

== Литература ==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

Удаление бесполезных символов из грамматики

2013-10-30T16:13:16Z

91.215.121.216: /* Пример */

== Порождающие и непорождающие нетерминалы ==
{{Определение
|definition=
Нетерминал <tex>A</tex> называется '''порождающим''', если из него может быть выведена конечная терминальная цепочка. Иначе он называется '''непорождающим'''.
}}

Очевидно, что если и только если все нетерминалы правой части являются порождающими, то порождающим является и нетерминал, стоящий в левой части. Это позволяет обнаружить непорождающие нетерминалы с помощью следующей процедуры.
# Найти правила, не содержащие нетерминалов в правых частях. Составить множество нетерминалов, встречающихся в левых частях таких правил.
# Если найдено такое правило, что все нетерминалы, стоящие в его правой части, уже входят в множество, то добавить в множество нетерминалы, стоящие в его левой части.
# Если на шаге 2 множество изменилось, повторить шаг 2.
# Получено множество всех порождающих нетерминалов грамматики, а все нетерминалы, не попавшие в него, являются непорождающими.

{{Лемма
|statement=
После удаления из грамматики правил, содержащих непорождающие нетерминалы, язык не изменится.
|proof=
Непорождающие нетерминалы по определению не могли участвовать в выводе какого-либо слова.
}}

== Достижимые и недостижимые нетерминалы ==
{{Определение
|definition=
Нетерминал <tex>A</tex> называется '''достижимым''' в КС-грамматике <tex>\Gamma</tex>, если существует порождение <tex>S \Rightarrow^* \alpha A \beta</tex>. Иначе он называется '''недостижимым'''.
}}

Очевидно, что если нетерминал в левой части правила является достижимым, то и все нетерминалы правой части являются достижимыми. Найти недостижимые нетерминалы можно с помощью следующей процедуры.
# Возьмём множество, состоящее из единственного элемента: <tex>\lbrace S \rbrace</tex>.
# Если найдено правило, в левой части которого стоит нетерминал, содержащийся в множестве, добавить в множество все нетерминалы из правой части.
# Если на шаге 2 множество изменилось, повторить шаг 2.
# Получено множество всех достижимых нетерминалов, а нетерминалы, не попавшие в него, являются недостижимыми.

{{Лемма
|statement=
После удаления из грамматики правил, содержащих недостижимые нетерминалы, язык не изменится.
|proof=
Недостижимые нетерминалы по определению не достижимы из стартового, следовательно они не могли участвовать в выводе какого-либо слова.
}}

=== Пример ===
Рассмотрим грамматику:
<tex>
\begin{array}{l l}
S\rightarrow AB|CD\\
A\rightarrow EF\\
G\rightarrow AD\\
C\rightarrow c

\end{array}
</tex>
# Возьмём множество, состоящее из единственного элемента: <tex>\lbrace S \rbrace</tex>.
# Из <tex>S</tex> достижимы нетерминалы <tex>A</tex>, <tex>B</tex>, <tex>C</tex> и <tex>D</tex>. Добавим их в множество и получим <tex>\lbrace S, A, B, C, D \rbrace</tex>.
# Множество изменилось. Переберём заново правила из грамматики. Из <tex>A</tex> можно вывести <tex>E</tex> и <tex>F</tex>, добавим их в множество.
# Снова переберём правила. Из <tex>C</tex> можно вывести только терминал, а <tex>G</tex> нету в множестве.
# После последнего обхода правил грамматики множество не изменилось, значит мы нашли все достижимые нетерминалы: <tex>\lbrace S, A, B, C, D, E, F \rbrace</tex>.
# Теперь удалим правило <tex>G\rightarrow AD</tex>, так как оно содержит в левой части нетерминал, которого нет в полученном множестве.

== Полезные и бесполезные нетерминалы ==
{{Определение
|definition=
Нетерминал <tex>A</tex> называется '''полезным''' в КС-грамматике <tex>\Gamma</tex>, если он может участвовать в выводе, то есть существует порождение вида <tex>S \Rightarrow ^* \alpha A \beta \Rightarrow ^* w</tex>. Иначе он называется '''бесполезным'''.
}}

{{Теорема
|id=th1
|statement=
Грамматика <tex>\Gamma</tex> не содержит бесполезных нетерминалов тогда и только тогда, когда грамматика <tex>\Gamma</tex> не содержит ни недостижимых нетерминалов, ни непорождающих.
|proof=
''Необходимость.'' Очевидно, так как недостижимые и непорождающие нетерминалы являются бесполезными.

''Достаточность.'' Рассмотрим любой нетерминал <tex>A</tex>. Так как он достижим, существуют <tex>\alpha</tex> и <tex>\beta</tex> такие, что <tex>S \Rightarrow ^* \alpha A \beta</tex>. Из того, что любой нетерминал является порождающим, следует, что из любой строки можно вывести строку из терминалов. Значит, существует <tex>\omega \in \Sigma ^ *</tex>: <tex>S \Rightarrow ^* \alpha A \beta \Rightarrow ^* \omega</tex>, и <tex>A</tex> {{---}} не бесполезный.
}}

== Алгоритм удаления бесполезных нетерминалов ==
# Удалить из грамматики правила, содержащие непорождающие нетерминалы.
# Удалить из грамматики правила, содержащие недостижимые нетерминалы.

=== Корректность алгоритма ===
Достаточность данных действий следует из доказанной выше теоремы.

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

Допустим, что в грамматике появился непорождающий нетерминал <tex>A</tex>. Так как до удаления недостижимых нетерминалов существовал вывод из <tex>A</tex> некоторой конечной цепочки терминалов <tex>\omega</tex>, то было удалено хотя бы какое-то одно правило из этого вывода.

Пусть <tex>B\rightarrow\alpha</tex> {{---}} правило, первым из удалённых применяемое в выводе <tex>A \Rightarrow ^* \omega</tex>. Оно могло быть удалено только в том случае, если в <tex>\alpha</tex> присутствуют недостижимые нетерминалы. Но так как было выбрано первое удалённое правило из вывода, то <tex>B</tex> — достижим, следовательно достижимы и все нетерминалы из <tex>\alpha</tex>. Значит, это правило не могло быть удалено.

=== Пример ===

Пусть нам дана грамматика:
<tex>
\begin{array}{l l}
S\rightarrow AS|BS|s \\
E\rightarrow EF|FF \\
A\rightarrow a \\
F\rightarrow f

\end{array}
</tex>. 
Удалим правила, содержащие непорождающие нетерминалы и получим грамматику
<tex>
\begin{array}{l l}
S\rightarrow AS|s \\
E\rightarrow EF|FF \\
A\rightarrow a \\
F\rightarrow f

\end{array}
</tex>. 
Теперь удалим недостижимые нетерминалы и получим грамматику
<tex>
\begin{array}{l l}
S\rightarrow AS|s \\
A\rightarrow a
\end{array}
</tex>.

=== Замечание ===
Шаги алгоритма нельзя менять местами.

Рассмотрим следующую грамматику:
<tex>
\begin{array}{l l}
S\rightarrow AB|a \\
A\rightarrow b
\end{array}.
</tex>
Все нетерминалы в этой грамматике достижимы. Однако, если удалить <tex>B</tex> как непорождающий, то нетерминал <tex>A</tex> станет недостижимым.

== Литература ==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

Удаление бесполезных символов из грамматики

2013-10-30T07:49:49Z

91.215.121.216: /* Достижимые и недостижимые нетерминалы */

== Порождающие и непорождающие нетерминалы ==
{{Определение
|definition=
Нетерминал <tex>A</tex> называется '''порождающим''', если из него может быть выведена конечная терминальная цепочка. Иначе он называется '''непорождающим'''.
}}

Очевидно, что если и только если все нетерминалы правой части являются порождающими, то порождающим является и нетерминал, стоящий в левой части. Это позволяет обнаружить непорождающие нетерминалы с помощью следующей процедуры.
# Найти правила, не содержащие нетерминалов в правых частях. Составить множество нетерминалов, встречающихся в левых частях таких правил.
# Если найдено такое правило, что все нетерминалы, стоящие в его правой части, уже входят в множество, то добавить в множество нетерминалы, стоящие в его левой части.
# Если на шаге 2 множество изменилось, повторить шаг 2.
# Получено множество всех порождающих нетерминалов грамматики, а все нетерминалы, не попавшие в него, являются непорождающими.

{{Лемма
|statement=
После удаления из грамматики правил, содержащих непорождающие нетерминалы, язык не изменится.
|proof=
Непорождающие нетерминалы по определению не могли участвовать в выводе какого-либо слова.
}}

== Достижимые и недостижимые нетерминалы ==
{{Определение
|definition=
Нетерминал <tex>A</tex> называется '''достижимым''' в КС-грамматике <tex>\Gamma</tex>, если существует порождение <tex>S \Rightarrow^* \alpha A \beta</tex>. Иначе он называется '''недостижимым'''.
}}

Очевидно, что если нетерминал в левой части правила является достижимым, то и все нетерминалы правой части являются достижимыми. Найти недостижимые нетерминалы можно с помощью следующей процедуры.
# Возьмём множество, состоящее из единственного элемента: <tex>\lbrace S \rbrace</tex>.
# Если найдено правило, в левой части которого стоит нетерминал, содержащийся в множестве, добавить в множество все нетерминалы из правой части.
# Если на шаге 2 множество изменилось, повторить шаг 2.
# Получено множество всех достижимых нетерминалов, а нетерминалы, не попавшие в него, являются недостижимыми.

{{Лемма
|statement=
После удаления из грамматики правил, содержащих недостижимые нетерминалы, язык не изменится.
|proof=
Недостижимые нетерминалы по определению не достижимы из стартового, следовательно они не могли участвовать в выводе какого-либо слова.
}}

=== Пример ===
Рассмотрим грамматику:
<tex>
\begin{array}{l l}
S\rightarrow AB|CD\\
A\rightarrow EF\\
G\rightarrow AD\\
C\rightarrow c

\end{array}
</tex>
# Возьмём множество, состоящее из единственного элемента: <tex>\lbrace S \rbrace</tex>.
# Из <tex>S</tex> достижимы нетерминалы <tex>A</tex>, <tex>B</tex>, <tex>C</tex> и <tex>D</tex>. Добавим их в множество и получим <tex>\lbrace S, A, B, C, D \rbrace</tex>.
# Множество изменилось. Рассмотрим следующие элементы в нём. Из <tex>B</tex>, <tex>C</tex> и <tex>D</tex> нельзя вывести нетермиалы, а из <tex>A</tex> можно вывести <tex>E</tex> и <tex>F</tex>.
# Полученное множество нетерминалов будет таким: <tex>\lbrace S, A, B, C, D, E, F \rbrace</tex>. Больше оно меняться не будет.
# Теперь удалим правило <tex>G\rightarrow AD</tex>, так как оно содержит в левой части нетерминал, которого нет в полученном множестве.

== Полезные и бесполезные нетерминалы ==
{{Определение
|definition=
Нетерминал <tex>A</tex> называется '''полезным''' в КС-грамматике <tex>\Gamma</tex>, если он может участвовать в выводе, то есть существует порождение вида <tex>S \Rightarrow ^* \alpha A \beta \Rightarrow ^* w</tex>. Иначе он называется '''бесполезным'''.
}}

{{Теорема
|id=th1
|statement=
Грамматика <tex>\Gamma</tex> не содержит бесполезных нетерминалов тогда и только тогда, когда грамматика <tex>\Gamma</tex> не содержит ни недостижимых нетерминалов, ни непорождающих.
|proof=
''Необходимость.'' Очевидно, так как недостижимые и непорождающие нетерминалы являются бесполезными.

''Достаточность.'' Рассмотрим любой нетерминал <tex>A</tex>. Так как он достижим, существуют <tex>\alpha</tex> и <tex>\beta</tex> такие, что <tex>S \Rightarrow ^* \alpha A \beta</tex>. Из того, что любой нетерминал является порождающим, следует, что из любой строки можно вывести строку из терминалов. Значит, существует <tex>\omega \in \Sigma ^ *</tex>: <tex>S \Rightarrow ^* \alpha A \beta \Rightarrow ^* \omega</tex>, и <tex>A</tex> {{---}} не бесполезный.
}}

== Алгоритм удаления бесполезных нетерминалов ==
# Удалить из грамматики правила, содержащие непорождающие нетерминалы.
# Удалить из грамматики правила, содержащие недостижимые нетерминалы.

=== Корректность алгоритма ===
Достаточность данных действий следует из доказанной выше теоремы.

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

Допустим, что в грамматике появился непорождающий нетерминал <tex>A</tex>. Так как до удаления недостижимых нетерминалов существовал вывод из <tex>A</tex> некоторой конечной цепочки терминалов <tex>\omega</tex>, то было удалено хотя бы какое-то одно правило из этого вывода.

Пусть <tex>B\rightarrow\alpha</tex> {{---}} правило, первым из удалённых применяемое в выводе <tex>A \Rightarrow ^* \omega</tex>. Оно могло быть удалено только в том случае, если в <tex>\alpha</tex> присутствуют недостижимые нетерминалы. Но так как было выбрано первое удалённое правило из вывода, то <tex>B</tex> — достижим, следовательно достижимы и все нетерминалы из <tex>\alpha</tex>. Значит, это правило не могло быть удалено.

=== Пример ===

Пусть нам дана грамматика:
<tex>
\begin{array}{l l}
S\rightarrow AS|BS|s \\
E\rightarrow EF|FF \\
A\rightarrow a \\
F\rightarrow f

\end{array}
</tex>. 
Удалим правила, содержащие непорождающие нетерминалы и получим грамматику
<tex>
\begin{array}{l l}
S\rightarrow AS|s \\
E\rightarrow EF|FF \\
A\rightarrow a \\
F\rightarrow f

\end{array}
</tex>. 
Теперь удалим недостижимые нетерминалы и получим грамматику
<tex>
\begin{array}{l l}
S\rightarrow AS|s \\
A\rightarrow a
\end{array}
</tex>.

=== Замечание ===
Шаги алгоритма нельзя менять местами.

Рассмотрим следующую грамматику:
<tex>
\begin{array}{l l}
S\rightarrow AB|a \\
A\rightarrow b
\end{array}.
</tex>
Все нетерминалы в этой грамматике достижимы. Однако, если удалить <tex>B</tex> как непорождающий, то нетерминал <tex>A</tex> станет недостижимым.

== Литература ==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

Удаление бесполезных символов из грамматики

2013-10-30T07:16:18Z

91.215.121.216: /* Алгоритм удаления бесполезных нетерминалов */

== Порождающие и непорождающие нетерминалы ==
{{Определение
|definition=
Нетерминал <tex>A</tex> называется '''порождающим''', если из него может быть выведена конечная терминальная цепочка. Иначе он называется '''непорождающим'''.
}}

Очевидно, что если и только если все нетерминалы правой части являются порождающими, то порождающим является и нетерминал, стоящий в левой части. Это позволяет обнаружить непорождающие нетерминалы с помощью следующей процедуры.
# Найти правила, не содержащие нетерминалов в правых частях. Составить множество нетерминалов, встречающихся в левых частях таких правил.
# Если найдено такое правило, что все нетерминалы, стоящие в его правой части, уже входят в множество, то добавить в множество нетерминалы, стоящие в его левой части.
# Если на шаге 2 множество изменилось, повторить шаг 2.
# Получено множество всех порождающих нетерминалов грамматики, а все нетерминалы, не попавшие в него, являются непорождающими.

{{Лемма
|statement=
После удаления из грамматики правил, содержащих непорождающие нетерминалы, язык не изменится.
|proof=
Непорождающие нетерминалы по определению не могли участвовать в выводе какого-либо слова.
}}

== Достижимые и недостижимые нетерминалы ==
{{Определение
|definition=
Нетерминал <tex>A</tex> называется '''достижимым''' в КС-грамматике <tex>\Gamma</tex>, если существует порождение <tex>S \Rightarrow^* \alpha A \beta</tex>. Иначе он называется '''недостижимым'''.
}}

Очевидно, что если нетерминал в левой части правила является достижимым, то и все нетерминалы правой части являются достижимыми. Найти недостижимые нетерминалы можно с помощью следующей процедуры.
# Возьмём множество, состоящее из единственного элемента: <tex>\lbrace S \rbrace</tex>.
# Если найдено правило, в левой части которого стоит нетерминал, содержащийся в множестве, добавить в множество все нетерминалы из правой части.
# Если на шаге 2 множество изменилось, повторить шаг 2.
# Получено множество всех достижимых нетерминалов, а нетерминалы, не попавшие в него, являются недостижимыми.

{{Лемма
|statement=
После удаления из грамматики правил, содержащих недостижимые нетерминалы, язык не изменится.
|proof=
Недостижимые нетерминалы по определению не достижимы из стартового, следовательно они не могли участвовать в выводе какого-либо слова.
}}

== Полезные и бесполезные нетерминалы ==
{{Определение
|definition=
Нетерминал <tex>A</tex> называется '''полезным''' в КС-грамматике <tex>\Gamma</tex>, если он может участвовать в выводе, то есть существует порождение вида <tex>S \Rightarrow ^* \alpha A \beta \Rightarrow ^* w</tex>. Иначе он называется '''бесполезным'''.
}}

{{Теорема
|id=th1
|statement=
Грамматика <tex>\Gamma</tex> не содержит бесполезных нетерминалов тогда и только тогда, когда грамматика <tex>\Gamma</tex> не содержит ни недостижимых нетерминалов, ни непорождающих.
|proof=
''Необходимость.'' Очевидно, так как недостижимые и непорождающие нетерминалы являются бесполезными.

''Достаточность.'' Рассмотрим любой нетерминал <tex>A</tex>. Так как он достижим, существуют <tex>\alpha</tex> и <tex>\beta</tex> такие, что <tex>S \Rightarrow ^* \alpha A \beta</tex>. Из того, что любой нетерминал является порождающим, следует, что из любой строки можно вывести строку из терминалов. Значит, существует <tex>\omega \in \Sigma ^ *</tex>: <tex>S \Rightarrow ^* \alpha A \beta \Rightarrow ^* \omega</tex>, и <tex>A</tex> {{---}} не бесполезный.
}}

== Алгоритм удаления бесполезных нетерминалов ==
# Удалить из грамматики правила, содержащие непорождающие нетерминалы.
# Удалить из грамматики правила, содержащие недостижимые нетерминалы.

=== Корректность алгоритма ===
Достаточность данных действий следует из доказанной выше теоремы.

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

Допустим, что в грамматике появился непорождающий нетерминал <tex>A</tex>. Так как до удаления недостижимых нетерминалов существовал вывод из <tex>A</tex> некоторой конечной цепочки терминалов <tex>\omega</tex>, то было удалено хотя бы какое-то одно правило из этого вывода.

Пусть <tex>B\rightarrow\alpha</tex> {{---}} правило, первым из удалённых применяемое в выводе <tex>A \Rightarrow ^* \omega</tex>. Оно могло быть удалено только в том случае, если в <tex>\alpha</tex> присутствуют недостижимые нетерминалы. Но так как было выбрано первое удалённое правило из вывода, то <tex>B</tex> — достижим, следовательно достижимы и все нетерминалы из <tex>\alpha</tex>. Значит, это правило не могло быть удалено.

=== Пример ===

Пусть нам дана грамматика:
<tex>
\begin{array}{l l}
S\rightarrow AS|BS|s \\
E\rightarrow EF|FF \\
A\rightarrow a \\
F\rightarrow f

\end{array}
</tex>. 
Удалим правила, содержащие непорождающие нетерминалы и получим грамматику
<tex>
\begin{array}{l l}
S\rightarrow AS|s \\
E\rightarrow EF|FF \\
A\rightarrow a \\
F\rightarrow f

\end{array}
</tex>. 
Теперь удалим недостижимые нетерминалы и получим грамматику
<tex>
\begin{array}{l l}
S\rightarrow AS|s \\
A\rightarrow a
\end{array}
</tex>.

=== Замечание ===
Шаги алгоритма нельзя менять местами.

Рассмотрим следующую грамматику:
<tex>
\begin{array}{l l}
S\rightarrow AB|a \\
A\rightarrow b
\end{array}.
</tex>
Все нетерминалы в этой грамматике достижимы. Однако, если удалить <tex>B</tex> как непорождающий, то нетерминал <tex>A</tex> станет недостижимым.

== Литература ==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]