Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 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: SSabA | ba; AAbA|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.
Входную ленту можно рассматривать как линейную последовательность ячеек, причем
каждая ячейка может хранить один символ из некоторого конечного входного алфавита.
Лента автомата бесконечна, но занято на ней в каждый момент времени только конечное
число ячеек. Граничные слева и справа от занятой области ячейки могут занимать