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

---

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, дальнейшее изложение посвящается рассмотрению именно этих типов грамматик.

---

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