Пред.Страница  След.Страница   Раздел   Содержание

1.3.4. Грамматики типа 3

Грамматики типа 3 называют автоматными грамматиками (А - грамматиками). Правила вывода в таких грамматиках имеют вид:
 
<A> ® a или <A> ® a<B> или <A> ® <B> a,
 
где a О V_т, <A>, <B> О V_a, причем грамматика может иметь только правила вида <A> ® a<B> - правосторонние правила, либо только  вида <A> ® <B>a - левосторонние правила. Примерами автоматных грамматик могут служить правосторонняя грамматика Г_{1. 6} и левосторонняя грамматика Г_{1. 7}.
Г_{1. 6}:
V_т = {a, b}, V_a = {<I>, <A>},
R = { <I> ® a<I>,
<I> ® a<A>,
<A> ® b<A>,
<A> ® b<Z>,
<Z> ® $ }.
Г_{1. 7}:
V_т = {a, b}, V_a = {<I>, <A>},
R = { <I> ® <A>b,
<A> ® <A>b,
<A> ® <Z>a,
<Z> ® <Z>a,
<Z> ® $ }.
 
Эти грамматики являются эквивалентными и порождают язык

L(Г₇) = {a...ab...b | n,m > 0}.
Между множествами языков различных типов существует отношение включения:
{ L _{типа 3} } М { L _{типа 2} } М{ L _{типа 1} } М{ L _{типа 0}}.
Доказано, что существуют языки типа 0, не являющиеся языками типа 1, языки типа 2, не являющиеся языками типа 1, и языки типа 3, не являющиея языками типа 2.

Учитывая, что наибольшее практическое применение находят грамматики типа 2 и типа 3, дальнейшее изложение посвящается рассмотрению именно этих типов грамматик.

---

• Пред.Страница  След.Страница   Раздел   Содержание