Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 28 стр.

    S → bSS → bbSSbSS → bbaabaa;
    S → bSS → bbSSbSS → bbbSSbSSbbSSbSS → ...
    Из полученных цепочек видно, что:
    а) цепочки всегда начинаются с терминала b, кроме аксиомы, и заканчиваются
терминалом а;
    б) количество терминалов а в любой цепочке всегда на 1 больше, чем b.
    Исходя из этих выводов, определим язык, порождаемый заданными правилами,
следующим образом:
    L(G) = {α | α ∈ {a, b}*}, |a| = |b| + 1, причем цепочки начинаются с терминала b и
заканчиваются терминалом а.

      4.4. Грамматический разбор
    В КС-грамматике может быть несколько выводов, эквивалентных в том смысле, что в
них применяются одни и те же правила к одинаковым в промежуточном выводе цепочкам,
но в различном порядке. Например, для грамматики G с правилами вывода S → ScS|b|a
возможны следующие эквивалентные выводы терминальной цепочки acb: S → ScS →
Scb → acb и S → ScS → acS → acb.
    Деревом вывода цепочки х в КС-грамматике G = (VT, VN, Р, S) называется
упорядоченное дерево, каждая вершина которого помечена символом из множества V ∪ VN
∪ {ε} так, что каждому правилу А → b1b2b3 ... bk, использующемуся при выводе цепочки х, в
дереве вывода соответствует поддерево с корнем А и прямыми потомками b1, b2, b3, ..., bk,
которое приведено на рисунке:

                                             A

                    b1 b2     …     bk
    В силу того, что цепочка х ∈ L(G) выводится из аксиомы S, корнем вывода всегда
является аксиома. Внутренние узлы вывода соответствуют нетерминальным символам.
Концевые вершины дерева вывода - листья - это вершины, не имеющие потомков. Такие
вершины соответствуют либо терминалам, либо пустым символам (ε) при условии, что среди
правил грамматики имеются правила с пустой правой частью. При чтении слева направо
концевые вершины дерева вывода образуют цепочку х.
    Дерево      вывода      часто   называют      деревом грамматического разбора, или
синтаксическим деревом, а процесс построения дерева вывода - грамматическим разбором
(синтаксическим анализом). Одной цепочке языка может соответствовать больше одного
дерева, так как эта цепочка может иметь разные выводы, порождающие разные деревья.
    КС-грамматика G == (VT, VN, Р, S) называется неоднозначной (неопределенной), если
существует цепочка х ∈ L(G), имеющая два или более дерева вывода.

   Рассмотрим пример.
   Пусть даны две КС-грамматики:

    G1 = (VT, VN, Р1, S), VN = {S},
    P1={S → S+S | S | S⋅S | (S) | a};
    G2= (VT, VN, Р2, S), VN = {S, A, B},
    P2 = {S → S + A | A | A, A → A⋅B | A / B | B, B → a| (S)}, содержащие в множестве
терминальных символов знаки операций, круглые скобки и символ а. Определить, являются