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

    S → DK; K → BK | ε.
    Подставим в эти правила B и D и получим эквивалентную праворекурсивную
грамматику G1:
    S → baK; K → aK | ε.
    Рассмотрим вывод цепочки baaaa в исходной леворекурсивной грамматике G:
    S → Sa → Saa → Saaa → baaaa.
    Эту же цепочку можно вывести в эквивалентной праворекурсивной грамматике G1:
    S → baK → baaK → baaaK → baaaaK → baaaa.


      4.6. Задания для самостоятельной работы
       1.   Построить КС-грамматику, порождающую язык an для n>0.
       2.   Построить КС-грамматику, порождающую язык anbn для n>0.
       3.   Построить КС-грамматику, порождающую язык (ab)nc*an+m для n>0 и m>0.
       4.   Построить КС-грамматику, порождающую язык (ab)*ca*bn+m для n>0 и m>0.
       5.   Построить КС-грамматику, порождающую язык anb3mcma2n = an(bbb)mcm(aa)n для
   n>1 и m>1.
       6.   Построить КС-грамматику, порождающую язык (ab)n(ca)*bn+2(abc)* для n>0.
       7.   Для леворекурсивной грамматики G: S→SabA | ba; A→AbA|bAa|c построить
   эквивалентную праворекурсивную грамматику.
       8.   Построить алгоритм устранения правой рекурсии и доказать эквивалентность
   соответствующего преобразования.
       9.   Построить КС-грамматику, порождающую идентификаторы, при этом
   обозначить символом t любую букву, а символом f - любую цифру.
       10. Дана КС-грамматика G:
        S → Aab | bSb | abB;
       A→ abS | ba | bbA;
       B → bB | Da | Aa;
       D → Dbb | aDa.
       Построить эквивалентную грамматику, все нетерминалы которой продуктивны.


                                5. ТЕОРИЯ АВТОМАТОВ


      5.1. Понятие автомата. Типы автоматов
    Автомат - это алгоритм, определяющий некоторое множество и, возможно,
преобразующий его в другое множество. Неформальное описание автоматов выглядит
следующим образом: автомат имеет входную ленту, управляющее устройство с конечной
памятью для хранения номера состояния, а также может иметь вспомогательную (рабочую)
и выходную ленты.
    Существует два типа автоматов:
    1) распознаватели - автоматы без выхода, которые распознают, принадлежит ли входная
цепочка заданному множеству L;
    2) преобразователи - автоматы с выходом, которые преобразуют входную цепочку x в
цепочку y при условии, что x ∈ L.
    Входную ленту можно рассматривать как линейную последовательность ячеек, причем
каждая ячейка может хранить один символ из некоторого конечного входного алфавита.
Лента автомата бесконечна, но занято на ней в каждый момент времени только конечное
число ячеек. Граничные слева и справа от занятой области ячейки могут занимать