Классификация грамматик

1.

КЛАССИФИКАЦИЯ ГРАММАТИК

2.

Правила порождающих грамматик позволяют
порождать цепочки языка. Ограничения же на виды
правил позволяют выделить классы грамматик.
Такую классификацию грамматик предложил Ноам
Хомский.

3.

Грамматики типа 0 – это грамматики общего вида,
правила вывода которых не имеют ограничений.
Грамматики типа 1, или контекстно-зависимые
грамматики – это грамматики, все правила вывода
которых имеют вид:
xAy → xφу, где АϵVn; х, у, ф ϵ (VnᴗVt)+

4.

Грамматика типа 2 – это бесконтекстные, или
контекстные свободные грамматики (КСграмматики), правила вывода которых имеют вид:
А→ф, где АϵVn, фϵ(VnᴗVt)*
Грамматика типа 3 – это автоматные грамматики,
которые делятся на два класса:
a)
Леворекурсивные, правила вывода которых имеют
вид:
А→Ab|a где, Aϵ Vn ; a,b ϵ Vt

5.

b) Праворекурсивные, правила которых имеют вид:
А→сA|a где, Aϵ Vn ; a,с ϵ Vt
Классы грамматик типа 0, 1, 2, 3 образуют
иерархию Хомского.
Язык L называется языком типа i, если существует
грамматика типа i, порождающая язык L

6.

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ
Дана порождающая грамматика G=(Vt, Vn,
P,S), в которой Vt = {a, b, c}, Vn = {B,C,S}, Р = {S
→ aB, B → Cd|dC, C →c}
Получить терминальные цепочки,
порождаемые данной грамматикой, и
определить длину их вывода.

7.

РЕШЕНИЕ
Получим следующие терминальные цепочки:
S → aB →aCd → aсd
2.
S → aB → adC → adc
Длины вывода цепочек равна 3.
1.