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

UptoLike

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

Также предполагается, что правые части правил, для которых совпадают левые части,
можно записать в одну строку с использованием разделителя. Так, правила вывода из
приведенного примера можно записать следующим образом: S aSb | ab.
4.3. Классификация грамматик
Правила порождающих грамматик позволяют осуществлять преобразования строк.
Ограничения же на виды правил позволяют выделить классы грамматик. Рассмотрим
классификацию, которую предложил Н. Хомский.
Грамматики типа 0 - это грамматики, на правила вывода которых нет ограничений.
Грамматики типа 1, или контекcтные грамматики -это грамматики, все правила которых
имеют следующий вид: хАу хϕу, где A V
N
, x, y, ϕ (V
N
V
T
)
+
.
Грамматики типа 2 - это бесконтекстные, или контекстно-свободные грамматики (КС-
грамматики). Правила вывода для этих грамматик имеют следующий вид: А ϕ, где А
V
N
, ϕ (V
N
V
T
)
*
.
Грамматики типа 3 - это автоматные грамматики, которые делятся на два типа:
а) леволинейные (леворекурсивные), правила вывода для которых имеют следующий
вид: А Аа | a, где А V
N
;
б) праволинейные (праворекурсивные), правила вывода для которых имеют следующий
вид: А Aа | a.
Язык L называется языком типа i, если существует грамматика типа i, порождающая
язык L.
4.3.1. Методика решения задач
Пример 1. Дана порождающая грамматика G = (V
T
, V
N
, Р, S), в которой V
T
= {a, d, е}, V
N
= {В, С, S}, Р = {S аВ, В Cd | dC, С е}. Выписать терминальные цепочки,
порожденные данной грамматикой, и определить длину их вывода.
Решение. Получим следующие терминальные цепочки:
S аВ aCd aed,
S аВ adC ade,
длина вывода которых равна 3.
Пример 2. Дана грамматика G = (V
T
, V
N
, Р, C), в которой V
T
= {a, b, c, d, е}, V
N
= {A, В,
С, D, E}, Р = {A ed, В Ab, С Bc, С dD, D Ae, E bc}. Определить,
принадлежит ли языку L(G) цепочка eadabcb.
Решение. Выведем возможные терминальные цепочки из аксиомы с помощью заданных
правил вывода:
С Bc Abc edbc,
С dD dAe dede.
Так как первые же терминальные символы полученных цепочек не совпадают с
заданной, можно сделать вывод о том, что цепочка eadabcb не принадлежит языку L(G).
Пример 3. Построить КС-грамматику (грамматику типа 2), порождающую цепочки из 0
и 1 с одинаковым числом тех и других символов.
Решение. Определим множества, задающие грамматику: V
T
= {0, 1}; V
N
= {S}; Р =
{S 0S1, S 1S0, S ε, S S01, S S10}.
Пример 4. Описать язык, порождаемый следующими правилами: S bSS | а.
Решение. Построим несколько терминальных цепочек, применяя заданные правила
вывода:
S a;
S bSS baa;
S bSS bbSSS bbaaa;