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

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
 
== Порождающие и непорождающие нетерминалы ==
 
== Порождающие и непорождающие нетерминалы ==
===Описание===
 
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
 
[[Формальные_грамматики|Нетерминал]] <tex>A</tex> называется '''порождающим''' (англ. ''generating''), если из него может быть выведена конечная терминальная цепочка. Иначе он называется '''непорождающим'''.
 
[[Формальные_грамматики|Нетерминал]] <tex>A</tex> называется '''порождающим''' (англ. ''generating''), если из него может быть выведена конечная терминальная цепочка. Иначе он называется '''непорождающим'''.
 
}}
 
}}
Очевидно, что если и только если все нетерминалы правой части правила являются порождающими, то порождающим является и нетерминал, стоящий в его левой части.  
+
 
 +
Очевидно, что если и только если все нетерминалы правой части правила являются порождающими, то порождающим является и нетерминал, стоящий в его левой части. Это позволяет обнаружить непорождающие нетерминалы с помощью следующей процедуры:
 +
# Найти правила, не содержащие нетерминалов в правых частях. Составить множество нетерминалов, встречающихся в левых частях таких правил.
 +
# Если найдено такое правило, что все нетерминалы, стоящие в его правой части, уже входят в множество, то добавить в множество нетерминалы, стоящие в его левой части.
 +
# Если на шаге 2 множество изменилось, повторить шаг 2.
 +
# Получено множество всех порождающих нетерминалов грамматики, а все нетерминалы, не попавшие в него, являются непорождающими.
 +
 
 +
 
 
{{Лемма
 
{{Лемма
 
|statement=
 
|statement=
Строка 12: Строка 18:
 
Непорождающие нетерминалы по определению не могли участвовать в выводе какого-либо слова.
 
Непорождающие нетерминалы по определению не могли участвовать в выводе какого-либо слова.
 
}}
 
}}
 
===Алгоритм===
 
'''Шаг 0'''. Множество порождающих нетерминалов пустое.<br>
 
'''Шаг 1'''. Находим правила, не содержащие нетерминалов в правых частях и добавляем нетерминалы, встречающихся в левых частях таких правил, в множество.<br>
 
'''Шаг 2'''. Если найдено такое правило, что все нетерминалы, стоящие в его правой части, уже входят в множество, то добавим в множество нетерминалы, стоящие в его левой части. <br>
 
'''Шаг 3'''. Повторим предыдущий шаг, если множество порождающих нетерминалов изменилось.<br>
 
В результате получаем множество всех порождающих нетерминалов грамматики, а все нетерминалы, не попавшие в него, являются непорождающими.
 
  
 
=== Время работы алгоритма ===
 
=== Время работы алгоритма ===

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)