Грамматика

[Коптелова Ольга]

Я ноль в программирование..но для зачёта нужно сделать эту задачу на с#:

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

вот алгоритм :Алгоритм, определяющий, является ли язык 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