Форум программистов, компьютерный форум, киберфорум
Наши страницы
C для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/3: Рейтинг темы: голосов - 3, средняя оценка - 5.00
Olga1994
0 / 0 / 1
Регистрация: 12.03.2013
Сообщений: 24
1

Определить, пуст ли язык L(G) для заданной грамматики G

12.05.2013, 14:45. Просмотров 576. Ответов 1
Метки нет (Все метки)

Определить, пуст ли язык L(G) для заданной грамматики G.
нужно написать программу, а я даже не представляю с чего начинать(
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.05.2013, 14:45
Ответы с готовыми решениями:

Определить пуст ли язык в заданной грамматике
задача Определить пуст ли язык в заданной грамматике..мне выдает кучу ошибок...вот алгоритм:Шаг 1....

Определить тип грамматики и язык, который порождает грамматика
Дана следующая грамматика: G = ({S, {L}_{a}, {L}_{b}, {R}_{a}, {R}_{b}, {W}_{a}, {W}_{b} }, {a, b},...

Построить язык, порожденный такой грамматикой. Определить тип грамматики
Дано грамматику G = (V, T, S, P), где , V={0, 1, S, A, B}, T={0,1}, P = {{S\rightarrow 0S,...

Составить грамматику, порождающую формальный язык. Определить тип формальной грамматики и языка по классификации
Помогите, пожалуйста с данным заданием: 1. Составить грамматику, порождающую формальный язык;...

Построение дерева вывода для заданной грамматики
ЗАДАНИЕ: ПОСТРОЕНИЕ ДЕРЕВА ВЫВОДА ДЛЯ ЗАДАННОЙ ГРАММАТИКИ По заданной грамматике построить...

1
Olga1994
0 / 0 / 1
Регистрация: 12.03.2013
Сообщений: 24
28.05.2013, 07:26  [ТС] 2
вот алгоритм :Алгоритм, определяющий, является ли язык L(G) пустым, можно организо-
вать следующим образом. Сначала надо построить коллекцию деревьев, пред-
ставляющихвыводыв грамматикеG:
Шаг 1. Начать коллекцию с единственного дерева, представленного только
корнем — узлом с меткой S.
Шаг 2. Добавить к коллекции любое дерево, которое может быть получено
из дерева, уже имеющегося в коллекции, посредством применения единственно-
го правила, если образующееся дерево не имеет ни одной ветви, длиннее m, и
если такого еще нет в коллекции. Поскольку число таких деревьев конечно, то
процесс в конце концов закончится
Шаг 3.Теперь язык L(G) непуст, если в построенной коллекции есть хотя бы
одно дерево, представляющее вывод терминальной цепочки. Иначе язык L(G)
пуст


Грамматику можно задавать, как угодно - как удобно.

Например, все заглавные буквы можно считать нетерминалами, а строчные терминалами.
Зададим начальный нетерминал:
char S = 'A';

Правила для нетерминалов в программе можно задать строками:
char* A = "aBa a";
char* B = "bBb b"

Которые соответствуют правилам: А->aBa, A->a, B->bBb, B->b
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.05.2013, 07:26

Для данной грамматики построить вывод заданной цепочки
Дали задание S ->T | T+S | T-S T -> F | F*T F -> a | b | c для b*c+a. Я особо в этом не шарю,...

Построение грамматики через язык
Хай. Как построить грамматику по этому такому представлению языка L(G) = { a^n00b^n, n = 0,1,......

Построить множество follow(1) на основе заданной ll-грамматики
Есть относительно понятная реализация здесь...


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

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

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