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

UptoLike

ВУЗ: 

ВСГУТУ | Улан-Удэ

Составители: 

Рубрика: 

S → DK; K → BK | ε.
Подставим в эти правила B и D и получим эквивалентную праворекурсивную
грамматику G
1
:
S → baK; K → aK | ε.
Рассмотрим вывод цепочки baaaa в исходной леворекурсивной грамматике G:
S → Sa → Saa → Saaa → baaaa.
Эту же цепочку можно вывести в эквивалентной праворекурсивной грамматике G
1
:
S → baK → baaK → baaaK → baaaaK → baaaa.
4.6. Задания для самостоятельной работы
1. Построить КС-грамматику, порождающую язык a
n
для n>0.
2. Построить КС-грамматику, порождающую язык a
n
b
n
для n>0.
3. Построить КС-грамматику, порождающую язык (ab)
n
c
*
a
n+m
для n>0 и m>0.
4. Построить КС-грамматику, порождающую язык (ab)
*
ca
*
b
n+m
для n>0 и m>0.
5. Построить КС-грамматику, порождающую язык a
n
b
3m
c
m
a
2n
= a
n
(bbb)
m
c
m
(aa)
n
для
n>1 и m>1.
6. Построить КС-грамматику, порождающую язык (ab)
n
(ca)
*
b
n+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.
Входную ленту можно рассматривать как линейную последовательность ячеек, причем
каждая ячейка может хранить один символ из некоторого конечного входного алфавита.
Лента автомата бесконечна, но занято на ней в каждый момент времени только конечное
число ячеек. Граничные слева и справа от занятой области ячейки могут занимать 
    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.
    Входную ленту можно рассматривать как линейную последовательность ячеек, причем
каждая ячейка может хранить один символ из некоторого конечного входного алфавита.
Лента автомата бесконечна, но занято на ней в каждый момент времени только конечное
число ячеек. Граничные слева и справа от занятой области ячейки могут занимать

Страницы