в таких грамматиках имеют вид:

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

называют автоматными грамматиками (А - грамматиками). Правила вывода в таких грамматиках имеют вид:
 



<A> ® a

или <A> ® a<B>

или <A> ® <B>

a,
 


где a О Vт, <A>, <B> О Va, причем грамматика может иметь только правила вида <A>

® a<B> - правосторонние правила, либо только  вида <A> ® <B>a

- левосторонние правила. Примерами автоматных грамматик могут служить правосторонняя грамматика Г1. 6

и левосторонняя грамматика Г1. 7.


Г1. 6:


Vт = {a, b}, Va = {<I>, <A>},





R = { <I> ® a<I>,


<I> ® a<A>,

<A> ® b<A>,

<A> ® b<Z>,

<Z> ® $ }.


Г1. 7:


Vт = {a, b}, Va = {<I>, <A>},


R = { <I> ® <A>b,


<A> ® <A>b,

<A> ® <Z>a,

<Z> ® <Z>a,

<Z> ® $ }.


 


Эти грамматики являются эквивалентными и порождают язык



L(Г7) = {a...ab...b | n,m > 0}.


Между множествами языков различных типов существует отношение включения:



{ L типа 3 } М

{ L типа 2 }

М{ L типа 1 } М{ L типа 0}.


Доказано, что существуют языки типа 0, не являющиеся языками типа 1, языки типа 2, не являющиеся языками типа 1, и языки типа 3, не являющиея языками типа 2.

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

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


Содержание раздела






---