Классификация грамматик по Хомскому

Тип 0

Любая порождающая грамматика является грамматикой типа 0. На вид правил грамматик этого типа не накладывается никаких дополнительных ограничений. Класс языков типа 0 совпадает с классом рекурсивно перечислимых языков.

Тип 1

Грамматика G = 〈 T, N, P, S 〉 называется неукорачивающей, если правая часть каждого правила из P не короче левой части (т. е. для любого правила α → β P выполняется неравенство | α | ≤ | β |). В виде исключения в неукорачивающей грамматике допускается наличие правила S → l, при условии, что S (начальный символ, аксиома) не встречается в правых частях

правил. Грамматикой типа 1 будем называть неукорачивающую грамматику. Тип 1 в некоторых источниках определяют с помощью так называемых контекстно-зависимых грамматик.

Грамматика G = 〈 T, N, P, S 〉 называется контекстно-зависимой (КЗ), если каждое правило из P имеет вид α → β, где α = ξ₁ A ξ₂, β = ξ₁γξ₂, A N, γ (T N)⁺, ξ₁, ξ₂ (T N)^*.

В виде исключения в КЗ-грамматике допускается наличие правила с пустой правой частью S → l, при условии, что S (начальный символ) не встречается в правых частях правил. Цепочку ξ₁ называют левым контекстом, цепочку ξ₂ называют правым контекстом. Язык, порождаемый контекстно-зависимой грамматикой, называется контекстно-

зависимым языком.

Тип 2

Грамматика G = 〈 T, N, P, S 〉 называется контекстно-свободной (КС), если каждое правило из Р имеет вид A → β, где A N, β (T N)^*. Заметим, что в КС-грамматиках допускаются правила с пустыми правыми частями. Язык, порождаемый контекстно-свободной грамматикой, называется контекстно-свободным языком.

Грамматикой типа 2 будем называть контекстно-свободную грамматику. КС-грамматика может являться неукорачивающей, т.е. удовлетворять ограничениям неукорачивающей грамматики.

Тип 3

Грамматика G = 〈 T, N, P, S 〉 называется праволинейной, если каждое правило из Р имеет вид A → wB либо A → w, где A, B N, w T *.

Грамматика G = 〈 T, N, P, S 〉 называется леволинейной, если каждое правило из Р имеет вид A → Bw либо A → w, где A, B N, w T *.

Леволинейные и праволинейные грамматики определяют один и тот же класс языков. Такие языки называются регулярными. Право- и леволинейные грамматики также будем называть регулярными.

Регулярная грамматика является грамматикой типа 3.

Автоматной грамматикой называется праволинейная (леволинейная) грамматика, такая, что каждое правило с непустой правой частью имеет вид: A → a либо A → aB (для леволинейной, соответственно, A → a либо A → Ba), где A, B N, a T. 4)

 

Лабораторная работа №9

Построение разных|различных| типов конечных автоматов

(Детерминированные и недетерминированные конечные автоматы)

 

Цель работы: изучить основные понятия конечных автоматов, научиться преобразовывать недетерминированный конечный автомат в эквивалентный ему детерминированный конечный автомат.

 

Задание

По недетерминированному конечному автомату, диаграмма которого представлена в индивидуальном задании, построить детерминированный конечный автомат, распознающий тот же язык.

В ходе выполнения задания должны быть выполнены и описаны следующие подзадачи:

 

1. Записать параметры заданного НКА в виде:

M = {S, I, О, f, g, s₀, F), (4.1)

 

где S ={ s ₀, s ₁, s ₂,..., s_m } – конечное множество число состояний |;

I – конечное множество допустимых входных символов;

О – конечное множество допустимых выходных символов;

f – функция переходов недетерминированного конечного автомата, т.е. отображение множества S х Iво множестве S, которое определяет выбор следующего состояния |НКА;

g – отображение множества S х I во множестве О, которое определяет выходной выходной символ (функцию g называют функцией выходов);

s₀| S – начальное |первоначальное| состояние|стан| управляющего устройства;

F S – множество завершающих состояний|стана|.

2. Построить таблицу переходов для заданного НКА

3. Преобразовать НКА в КА.

4.Проверить состояния полученного КА на достижимость и эквивалентность

5. Записать параметры заданного КА в виде:

M = {S, I, g, s₀, F), (4.2)

 

 

6. Построить диаграмму состояний полученного КА.

7. Проверить, допускает ли полученный КА цепочки, которые были допущены НКА.

8. Составить программу, реализующую работу полученного КА.

Таблица 9.1 – Варианты заданий

№ вариан та	Задание

 

№ вариан та	Задание

 

Продолжение таблицы 9.1

 

 

Продолжение таблицы 9.1

 

Пример. Преобразовывать НКА в эквивалентный ему ДКА

 

Конечный автомат – это структура вида

M = {S, I, О, f, g, s₀, F),

где S – конечное множество число состояний |;

I – конечное множество допустимых входных символов;

О – конечное множество допустимых выходных символов;

f – отображение множества S х Iво множестве S, которое определяет выбор следующего состояния (функцию f называют функцией переходов|);

g – отображение множества S х I во множестве О, которое определяет выходной выходной символ (функцию g называют функцией выходов);

s₀| S – начальное состояние управляющего устройства;

F S – множество завершающих состояний|стана|.

Для заданного конечного автомата

S={q0,q1,q2}

I={0,1,┴}

S₀=q1

F={q0}

Функция переходов недетерминированного конечного автомата представлена в таблице

f

S			┴
q0	q0	q2
q1	q2	q0q1
q2	q2	q0q1q2

 

Переходим к построению детерминированного автомата

S			┴
q1	q2	q0q1		a
q0	q0	q2		b
q2	q2	q0q1q2		c
q0q1	q0q2	q0q1q2		d
q0q1q2	q0q2	q0q1q2		e
q0q2	q2	q0q1q2		f

 

Таблица переходов f детерминированного автомата

S			┴
a	b	c
b	c	d
c	c	e	0
d	f	e
e	f	e	1
f	c	e

Проверим состояния конечного автомата на достижимость.

Во все состояния можно попасть из начального, значит – все состояния достижимы.

Проверим состояния конечного автомата на эквивалентность.

По входному символу ┴

{b,d,e,f},{a,c}

По входному символу 0

{a},{b},{f,c},{d,e}

По входному символу 1

Эквивалентные вычеркнуты.

Новая таблица переходов f’ детерминированного автомата

S			┴
a	b	f
b	f	d	1
d	f	d	1
f	f	d

 

В итоге минимизированный конечный автомат принимает вид:

 

S			┴
a	f	f
f	f	f

 

 

Лабораторная работа №10