Название: Информатика (формальные языки и грамматики) - Методическая разработка(С.Е. Рояк)

Жанр: Информатика

Просмотров: 1363


Занятие  5.  классификация грамматик и языков по хомскому

 

Цель занятия: уметь определять класс языков по виду грамматик; обсудить принципы классификации формальных языков и их связь с проблемой разрешимости.

 

Методические указания

 

Что необходимо знать:

· что такое укорачивающие и не укорачивающие грамматики?

· доказательство разрешимости языков, порождаемых не уко-рачивающими грамматиками;

· знать определение HC-грамматик, KC-грамматик,

A-грамматик;

 

Основные определения

 

1. Не укорачивающая грамматика имеет правило вывода a ® b, где l(a) £ l(b).

2. HC-грамматики имеют правила вывода xAh ® xbh, где A ÎN, b Î(N È T)+,   x,hÎ( N  È T)*.

3. KC-грамматики имеют правила вывода A ®a, где AÎ N, aÎ (N  È T )*.

4. НУКС-грамматики имеют правила вывода A ® a, где AÎ N, aÎ (NÈT)+.

5. А-грамматики имеют правила вывода A ® aB и A ® a, где A,BÎN, aÎT. Такие грамматики называются праволинейные. Автоматные грамматики могут иметь правила вывода A ® Ba и A ® a, где A,BÎN, aÎT и тогда они называются леволинейные. Существует еще одна форма автоматных грамматик, называемых модифицированные автоматные грамматики. Правила вывода в таких грамматиках имеют схему: A ® aB и A ® е, где A,BÎN.

Задачи и упражнения

 

1. Какие из приведенных ниже грамматик являются

А-грамматиками?

G1=<{a,b},  {S}, S, {S®ab½aSb}>,

G2=<{a,b},  {S,A,B}, S, {S®AB, A®aA½e, B®bB½e }>,

G3=<{a,b},  {S}, S, {S®aS½bS½e}>,

G4=<{a,b},  {S,A}, S, {S®aSb½aA, A®aA½e}>,

G5=<{a,b},  {S,A,B}, S, {S®aA½bB, A®aA½bA,

            B®aB½bB½b}>,

G6=<{a,b}, {S}, S ,{S®aS½Sb½a½b} >,

G7=<{3,4}, {S,1,2,0}, S, {S®S312½302, 0®21,

           12®4, 2®e}>,

G8=<{a,b,1,2}, {S,A,B}, S, {S®aB½bB½a½b, B®AB,

            A®a½b½1½2} >,

G9=<{a,b}, {S,A,B}, S, {S®aАа, A®aABa½b, aB®Ba,

            bB®bb}>.

2. Какие из грамматик из задания 1 являются линейными?

3. Какие из грамматик из задания 1 являются КС-грам-матиками?

4. Какие из грамматик из задания 1 являются НС-грам-матиками?

5. Какие из грамматик из задания 1 задают А-языки?

6. Какие из грамматик из задания 1 задают КС-языки?

7. Какие из грамматик из задания 1 задают НС-языки?

8. Определите какие из следующих языков

   L1={(a,ba)*},

L2={(ab)m½m³0}

L3=L1U L2

L4=L1°L2

L5={anbmdk½n,m,k³1},

L6={anbmdk½n,m,k³1, m³n},

L7={(ab)n(ab)n½n³0},

L8={w½wÎ{a,b}*}

L9=L6 U L8,

L10=L7°L6,

L11={anbncmdm½n,m,k³1, m³n},

L12={ambncndm½n,m,k³0},

L13=L6 U L12

L14=L5°L11

являются   a) А-языками   b) КС-языками  c) НС-языками?