Форум программистов, компьютерный форум, киберфорум
Теория автоматов
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/6: Рейтинг темы: голосов - 6, средняя оценка - 4.67
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}\bigcuphttps://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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
04.12.2017, 18:17
Ответы с готовыми решениями:

Реализовать рекурсивный алгоритм вывода строки в обратном порядке путём устранения последнего символа в строке
Кто-нибудь помогите пожалуйста решить данную задачку: Реализовать рекурсивный алгоритм вывода...

Нужен алгоритм поиска пути в этом лабиринте (будь то волновой алгоритм или алгоритм правой/левой руки )
#include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; void lab...

Удаление недостижимых символов в КС грамматике
На вход подается описание контестно-свободной грамматики, состоящая из левой и правой частей. Это...

алгоритм построения ТИ
Здравствуйте, вопрос вот в чем: у меня есть программа которая строит ТИ, а последний столбец просит...

2
Эксперт по математике/физике
2746 / 1887 / 636
Регистрация: 01.09.2014
Сообщений: 5,086
05.12.2017, 00:07 2
Я не уверен в названиях, но мне кажется, что продуктивные нетерминалы вы нашли правильно.

Видно, что слова с C и G нельзя получить из S. Вообще в этой грамматике из S не вывозится ни одно слово из терминалов.
1
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
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
05.12.2017, 04:16

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

Алгоритм построения круга
Не могу понять почему рисует только круг. using System; using System.Collections.Generic;...

Алгоритм построения звезды
Проблема заключается в следующем: Есть фигура, построенная из 4 примитивов(треугольников). При...

Алгоритм построения функции
привет, 1. не подскажите где найти алгоритм решения? 2. или готовое решение(исходники) на...

Алгоритм построения окружности
Подскажите с помощью какого алгоритма можно построить окружность на TASM! Добавлено через 1 час...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.