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

@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 не уйдёт.

@DariaGris 1 / 11 / 0 Регистрация: 24.09.2016 Сообщений: 98
		1
	Алгоритм устранения непродуктивных нетерминалов, алгоритм построения недостижимых символов 04.12.2017, 18:17. Просмотров 1208. Ответов 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 $Эксперт по математике/физике$ 2746 / 1887 / 636 Регистрация: 01.09.2014 Сообщений: 5,086
	05.12.2017, 00:07	2
	Я не уверен в названиях, но мне кажется, что продуктивные нетерминалы вы нашли правильно. Видно, что слова с C и G нельзя получить из S. Вообще в этой грамматике из S не вывозится ни одно слово из терминалов. 1

iifat 2522 / 1619 / 146 Регистрация: 05.06.2011 Сообщений: 4,537
	05.12.2017, 04:16	3
	Сообщение от DariaGris получается грамматика будет иметь вид Ну собственно, да. Именно так и получается. Либо где-то ошибка при переписывании грамматики, либо вот такая вот задача с грамматикой, из которой ничего терминального не выведешь. Да оно и видно, собственно: $https://www.cyberforum.ru/cgi-bin/latex.cgi?S\rightarrow 1D1\rightarrow 11B1\rightarrow 11B101\dots$ и никуда эта B не уйдёт. 1

Опции темы