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

@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$
Алгоритм устранения недостижимых символов (если я правильно понимаю это только те правила которые можно вывести из начального нетерминала )
а как в данном примере сделать ??
можете подробно объяснить сами алгоритмы и указать где я рассуждаю неправильно ??

Вернуться к обсуждению:
Алгоритм устранения непродуктивных нетерминалов, алгоритм построения недостижимых символов Теория автоматов

Следующий ответ

Другие темы раздела
Теория автоматов неизвестная задача https://www.cyberforum.ru/ automata-theory/ thread2149335.html попались задачи в тесте.Как решить .Объясните по шагам.	Как построить дерево Прюфера по коду Харари? Теория автоматов Добрый день дорогие друзья. Подскажите пожалуйста как построить дерево Прюфера по коду Харари. Код Харари = {674}. Если можно картинку дерева Прюфера и поподробнее как построить. Да и как найти сам...
Теория автоматов Машина Тьюринга. Перевод из двоичной в четверичную СС https://www.cyberforum.ru/ automata-theory/ thread2149181.html Перевод числа из двоичной в четверичную СС.	Теория автоматов Что такое конечные автоматы? https://www.cyberforum.ru/ automata-theory/ thread2144333.html Что такое конечные автоматы? И как их понимать? В вики и на хабре как-то слишком сложное написано TL;DR :(
Теория автоматов Определить, в какое слово перерабатывает машина каждое из следующих слов, исходя из стандартного начального состояния Помогите решить. Определите, в какое слово перерабатывает машина каждое из следующих слов, исходя из стандартного начального состояния. Запишите последовательность конфигураций при работе машины....	Теория автоматов Конечный автомат для языка https://www.cyberforum.ru/ automata-theory/ thread2142197.html Необходимо определить КА для языка L = {bnabm\|n,m>0} и удалить из него лямбда переходы. Правильно ли я понимаю, что здесь лямбда переходоа не будет?
Теория автоматов Построить накапливающий сумматор https://www.cyberforum.ru/ automata-theory/ thread2141881.html Здравствуйте. Простите, что второй раз с одним вопросом... Нужно построить накапливающий сумматор для формирования поразрядных сумм и переносов в темпе поступления на вход сумматора 2 двоичных чисел...	Теория автоматов Какие цепочки будут входить в регулярное множество? Добрый день. Есть задача: Какие цепочки будут входить в регулярное множество, определяемое регулярным выражением axq? Указания: Цепочки приводите в порядке возрастания длины. Не указывайте...
Теория автоматов Исключить эквивалентные состояния конечного автомата Исключить эквивалентные состояния конечного автомата. Как это делается? По графу или по таблице? Можно хотя бы примерчик как это сделать или опишите, пожалуйста, что вообще надо делать.... https://www.cyberforum.ru/ automata-theory/ thread2141218.html	Теория автоматов Построить регулярное выражение, задающее множество всех слов над данным словарем https://www.cyberforum.ru/ automata-theory/ thread2126125.html 2. Построить регулярное выражение, задающее множество всех таких слов над словарем {a,b,c}, в которых за символом b а) обязательно стоит символ с; б) не может стоять символ с. Построить конечные...
Построить автоматы, распознающие языки, задаваемые регулярными выражениями Теория автоматов 1. Построить автоматы, распознающие языки, задаваемые регулярными выражениями: а) a+b б) (a+b)*	Теория автоматов Построение регулярного выражения Здравствуйте, дана цепочка начинается с 10 и заканчивается на 1, необходимо построить дкр ,и написать по нему регулярные выражения. Я написала дкр и построила по нему регулярные выражения, но они... https://www.cyberforum.ru/ automata-theory/ thread2123042.html

@DariaGris 1 / 11 / 0 Регистрация: 24.09.2016 Сообщений: 98
		0
	Алгоритм устранения непродуктивных нетерминалов, алгоритм построения недостижимых символов - Теория автоматов - Ответ 11911976 04.12.2017, 18:17. Показов 2562. Ответов 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