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