Алгоритм устранения непродуктивных нетерминалов, алгоритм построения недостижимых символов

@DariaGris · Регистрация: 24.09.2016

Студворк — интернет-сервис помощи студентам

Задание: найдите лишние нетерминалы в следующей грамматике с начальным нетерминалом S и в соответствии с алгоритмом устранения лишних символов необходимо применить алгоритмы устранения непродуктивных нетерминалов, а потом алгоритм устранения недостижимых символов. Сложноствь в том, что я не до конца понимаю сам алгоритм, может кто то подробно объяснить по шагам???
$https://www.cyberforum.ru/cgi-bin/latex.cgi?S\rightarrow 1D1 S\rightarrow oEF A\rightarrow 1SF B\rightarrow B10 C\rightarrow 0 D\rightarrow 1B G\rightarrow 0F0 F\rightarrow 0A E\rightarrow 00d$

Алгоритм устранения непродуктивных нетерминалов.
Определяю множество продуктивных нетерминалов
1 шаг - выбираю те из которых выводятся либо чисто терминальные цепочки либо $https://www.cyberforum.ru/cgi-bin/latex.cgi?\varepsilon$ цепочки
$https://www.cyberforum.ru/cgi-bin/latex.cgi?{N}_{0}=$ ∅
$https://www.cyberforum.ru/cgi-bin/latex.cgi?{N}_{1}={N}_{0}\bigcup \begin{Bmatrix} C,&E \end{Bmatrix}$
2 шаг
выбираем те цепочки которые содержат терминальную цепочку и продуктивные нетерминалы(т.к. у нас таких нет то будет пустое множество )
$https://www.cyberforum.ru/cgi-bin/latex.cgi?{N}_{2}={N}_{1}\bigcup$ ∅ $https://www.cyberforum.ru/cgi-bin/latex.cgi?= {N}_{2}={N}_{*}=\begin{Bmatrix} C,&E \end{Bmatrix}$
получается грамматика будет иметь вид
$https://www.cyberforum.ru/cgi-bin/latex.cgi?C\rightarrow 0 E\rightarrow ood$
Алгоритм устранения недостижимых символов (если я правильно понимаю это только те правила которые можно вывести из начального нетерминала )
а как в данном примере сделать ??
можете подробно объяснить сами алгоритмы и указать где я рассуждаю неправильно ??

@3D Homer · 05.12.2017, 00:07

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

Видно, что слова с C и G нельзя получить из S. Вообще в этой грамматике из S не вывозится ни одно слово из терминалов.

iifat · 05.12.2017, 04:16

Сообщение от DariaGris

получается грамматика будет иметь вид

Ну собственно, да. Именно так и получается. Либо где-то ошибка при переписывании грамматики, либо вот такая вот задача с грамматикой, из которой ничего терминального не выведешь. Да оно и видно, собственно: $https://www.cyberforum.ru/cgi-bin/latex.cgi?S\rightarrow 1D1\rightarrow 11B1\rightarrow 11B101\dots$ и никуда эта B не уйдёт.

Новые блоги и статьи Все статьи Все блоги /
Angular: Вопросы и ответы на собеседовании Reangularity 15.06.2025 Готовишься к техническому интервью по Angular? Я собрал самые распространенные вопросы, с которыми сталкиваются разработчики на собеседованиях в этом году. От базовых концепций до продвинутых. . .	Архитектура Onion в ASP.NET Core MVC stackOverflow 15.06.2025 Что такое эта "луковая" архитектура? Термин предложил Джеффри Палермо (Jeffrey Palermo) в 2008 году, и с тех пор подход только набирал обороты. Суть проста - представьте себе лук с его. . .	Unity 4D GameUnited 13.06.2025 Четырехмерное пространство. . . Звучит как что-то из научной фантастики, правда? Однако для меня, как разработчика со стажем в игровой индустрии, четвертое измерение давно перестало быть абстракцией из. . .	SSE (Server-Sent Events) в ASP.NET Core и .NET 10 UnmanagedCoder 13.06.2025 Кажется, Microsoft снова подкинула нам интересную фичу в новой версии фреймворка. Работая с превью . NET 10, я наткнулся на нативную поддержку Server-Sent Events (SSE) в ASP. NET Core Minimal APIs. Эта. . .	С днём независимости России! Hrethgir 13.06.2025 Решил побеседовать, с утра праздничного дня, с LM о завоеваниях. То что она написала о народе, представителем которого я являюсь сам сначала возмутило меня, но дальше только смешило. Это чисто. . .
Лето вокруг. kumehtar 13.06.2025 Лето вокруг. Наполненное бурями и ураганами событий. На фоне магии Жизни, священной и вечной, неумелой рукой человека рисуется панорама душевного непокоя. Странные серые краски проникают и. . .	Популярные LM модели ориентированы на увеличение затрат ресурсов пользователями сгенерированного кода (грязь -заслуги чистоплюев). Hrethgir 12.06.2025 Вообще обратил внимание, что они генерируют код (впрочем так-же ориентированы разработчики чипов даже), чтобы пользователь их использующий уходил в тот или иной убыток. Это достаточно опытные модели,. . .	Топ10 библиотек C для квантовых вычислений bytestream 12.06.2025 Квантовые вычисления - это та область, где теория встречается с практикой на границе наших знаний о физике. Пока большая часть шума вокруг квантовых компьютеров крутится вокруг языков высокого уровня. . .	Dispose и Finalize в C# stackOverflow 12.06.2025 Работая с C# больше десяти лет, я снова и снова наблюдаю одну и ту же историю: разработчики наивно полагаются на сборщик мусора, как на волшебную палочку, которая решит все проблемы с памятью. Да,. . .	Повышаем производительность игры на Unity 6 с GPU Resident Drawer GameUnited 11.06.2025 Недавно копался в новых фичах Unity 6 и наткнулся на GPU Resident Drawer - штуку, которая заставила меня присвистнуть от удивления. По сути, это внутренний механизм рендеринга, который автоматически. . .

@DariaGris 1 / 11 / 0 Регистрация: 24.09.2016 Сообщений: 98

	Алгоритм устранения непродуктивных нетерминалов, алгоритм построения недостижимых символов 04.12.2017, 18:17. Показов 2959. Ответов 2 Метки нет (Все метки) Задание: найдите лишние нетерминалы в следующей грамматике с начальным нетерминалом S и в соответствии с алгоритмом устранения лишних символов необходимо применить алгоритмы устранения непродуктивных нетерминалов, а потом алгоритм устранения недостижимых символов. Сложноствь в том, что я не до конца понимаю сам алгоритм, может кто то подробно объяснить по шагам??? $https://www.cyberforum.ru/cgi-bin/latex.cgi?S\rightarrow 1D1<br /> S\rightarrow oEF<br /> A\rightarrow 1SF<br /> B\rightarrow B10<br /> C\rightarrow 0<br /> D\rightarrow 1B<br /> G\rightarrow 0F0<br /> F\rightarrow 0A<br /> E\rightarrow 00d$ Алгоритм устранения непродуктивных нетерминалов. Определяю множество продуктивных нетерминалов 1 шаг - выбираю те из которых выводятся либо чисто терминальные цепочки либо $https://www.cyberforum.ru/cgi-bin/latex.cgi?\varepsilon$ цепочки $https://www.cyberforum.ru/cgi-bin/latex.cgi?{N}_{0}=$ ∅ $https://www.cyberforum.ru/cgi-bin/latex.cgi?{N}_{1}={N}_{0}\bigcup \begin{Bmatrix}<br /> C,&E<br /> \end{Bmatrix}$ 2 шаг выбираем те цепочки которые содержат терминальную цепочку и продуктивные нетерминалы(т.к. у нас таких нет то будет пустое множество ) $https://www.cyberforum.ru/cgi-bin/latex.cgi?{N}_{2}={N}_{1}\bigcup$ ∅ $https://www.cyberforum.ru/cgi-bin/latex.cgi?= {N}_{2}={N}_{*}=\begin{Bmatrix}<br /> C,&E<br /> \end{Bmatrix}$ получается грамматика будет иметь вид $https://www.cyberforum.ru/cgi-bin/latex.cgi?C\rightarrow 0<br /> E\rightarrow ood$ Алгоритм устранения недостижимых символов (если я правильно понимаю это только те правила которые можно вывести из начального нетерминала ) а как в данном примере сделать ?? можете подробно объяснить сами алгоритмы и указать где я рассуждаю неправильно ?? 0

@3D Homer $Эксперт по математике/физике$ 5016 / 3628 / 1164 Регистрация: 01.09.2014 Сообщений: 9,789
	05.12.2017, 00:07
	Я не уверен в названиях, но мне кажется, что продуктивные нетерминалы вы нашли правильно. Видно, что слова с C и G нельзя получить из S. Вообще в этой грамматике из S не вывозится ни одно слово из терминалов. 1

Опции темы