Сведение недетерминированного автомата к детерминированному

U, B
I, мА
R, Ом

Вывод:

Ø Фоторезистор уменьшает свое сопротивление при усилении освещенности и увеличивает его при ослаблении освещенности.

Изм.

Лист

№ докум.

Подпись

Дата

Лист

КФ ОГУ 270106.9 0 12.02 О

Разраб.

Дорофеева Д.И.

Провер.

Бондарев А.В.

Реценз.

Н. Контр.

Утверд.

Резисторы с зависимостью от освещенности (фоторезисторы)

Лит.

Листов

Кафедра ПСК.гр.10-ПСК

 

 

Цель работы

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

Индивидуальное задание

 

Исходными данными являются Таблица 1, Таблица 2 и правило вывода R.

 

Таблица 1

ci

c1

c2

c3

c4

c5

c6

c7

c8

c9

c10

c11

c12

c13

c14

c15

c16

c17

c18

si

А

Л

Е

К

С

Е

Е

В

_

С

Е

Р

Г

Е

Й

_

Н

И

xi

x1

x0

x6

x7

x5

x6

x6

x2

x5

x4

x6

x0

x4

x6

x0

x5

x7

x3

 

Таблица 2

А

Б

В

Г

Д

Е

Ж

З

И

Й

К

Л

М

Н

О

П

x1

x5

x2

x4

x6

x6

x4

x3

x3

x0

x7

x0

x3

x7

x4

x5

Р

С

Т

У

Ф

Х

Ц

Ч

Ш

Щ

Ы

Ь

Э

Ю

Я

_

x0

x4

x5

x7

x2

x5

x1

x2

x2

x0

x1

x6

x1

x3

x7

x5

 

Задана формальная грамматика G = < V_T, V_N, S, R >, где

V_T = {C₁, C₂, C₃, …, C₁₈} – терминальный словарь;

V_N = { S, A, B, C, D, E, F } – нетерминальный словарь;

S ∈ V_n – начальный символ грамматики;

R – множество правил вывода, которые имеют следующий вид:

S → C₁C₂C₃A;

S → C₁C₄C₅B;

S → C₆C;

S → C₇F;

A → C₈D;

A → C₉;

B → C₈E;

B → C₉;

C → C₈E;

C → C₉;

D →C₁₀S;

D → C₁₁;

E → C₁₁S;

E → C₁₁;

F → C₁₂C₁₃C₁₄C₁₅;

F → C₁₆C₁₃C₁₄C₁₅;

F → C₁₇C₁₈C₁₅.

 

Приведем эту праволинейную грамматику к виду G' = < V_T', V_N', S, R' >, где

V_T'= { x ₀, x ₁,…, x ₇} – новый терминальный словарь;

R' – множество правил вывода, получаемых из заданных заменой символов из алфавита V_T

символами из алфавита V_T' в соответствии с Таблицей 1.

 

R':

S →;x₁x₀x₆A|x₁x₇x₅B|x₆C|x₆F;

A → x₂D|x₅;

B → x₂E|x₅;

C → x₂E|x₅;

D → x₄S|x₆;

E → x₆S|x₆;

F → x₀x₄x₆x₀|x₅x₄x₆x₀|x₇x₃x₀;

 

Здесь | − металингвистический символ (связка), читаемый как “ИЛИ”.

Мощность |Vt’| словаря Vt’ (число символов в нем) 8: словарь содержит все символы x _{0 –} x _7.

 

Переход от праволинейной грамматики к автоматной

Этот этап выполняется путем расширения нетерминального символа способом, вытекающим из возможности преобразования праволинейной грамматики в автоматную, G'' = < V_T', V_N'', S, R'' >.

 

Для нашего задания получим множество R'' правил вывода:

 

R'':

S → x₁S₁; S₁ → x₀S₂; S₂ → x₆A;

S → x₁S₃; S₃ → x₇S₄; S₄ → x₅B

S → x₆C; S → x₆F;

A → x₂D; A → x₅;

B → x₂E; B → x₅;

C → x₂E; C → x₅;

D → x₄S; D → x₆;

E → x₆S; E → x₆;

F → x₀F₁; F₁ → x₄ F₂; F₂ → x₆F₃ ; F₃ → x₀;

F → x₅F₄; F₄ → x₄F₅; F₅ → x₆F₆; F₆ → x₀;

F → x₇F₇; F₇ → x₃F₈; F₈→x₀;

 

Таким образом, нетерминальный словарь теперь имеет вид:

V_N'' = < S, S₁, S₂, S₃, S₄, A, B, C, D, E, F, F₁, F₂, F₃, F₄, F₅, F₆, F₇, F₈ >;

 

Его мощность |V_N''| равна 19.

Построение недетерминированного конечного автомата

Создадим недетерминированный конечный распознающий автомат

A = < Q, X, δ, q₀, q_k >, где:

Q – множество внутренних состояний;

Х – входной алфавит; δ — отображение δ:X×Q → P(Q);

P(Q) – множество подмножеств из Q;

q₀ ∈ Q – начальное состояние;

q_k ∈ Q – заключительное состояние, q_k ≠ q₀;

 

Нетерминальным символам сопоставим состояния автомата, как указано в Таблице 3.

Таблица 3

S

S1

S2

S3

S4

A

B

C

D

E

F

F1

F2

F3

F4

F5

F6

F7

F8

-

q0

q1

q2

q3

q4

q5

q6

q7

q8

q9

q10

q11

q12

q13

q14

q15

q16

q17

q18

q19

Заключительное состояние обозначено через q₁₉.

По правилам вывода поставим в соответствие переходы автомата. Тогда получим таблицу переходов (Таблица 4) недетерминированного конечного автомата, соответствующего предложенному заданию.

 

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

	x0	x1	x2	x3	x4	x5	x6	x7
q0		q1, q3					q7, q10
q1	q2
q2							q5
q3								q4
q4						q6
q5			q8			q19
q6			q9			q19
q7			q9			q19
q8					q0		q19
q9							q19,q0
q10	q11					q14		q17
q11					q12
q12							q13
q13	q19
q14					q15
q15							q16
q16	q19
q17				q18
q18	q19
q19

По таблице 4 составим граф переходов:

Рисунок 1. Граф переходов недетерминированного автомата.

Сведение недетерминированного автомата к детерминированному

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

	x0	x1	x2	x3	x4	x5	x6	x7	x8
q0		q1,3					q7,10
q0,19		q1,3					q7,10		q20
q1,3	q2							q4
q2							q5
q4						q6
q5			q8			q19
q6			q9			q19
q7,10	q11		q9			q14,19		q17
q8					q0		q19
q9							q19, 0
q11					q12
q12							q13
q13	q19
q14,19					q15				q20
q15							q16
q16	q19
q17				q18
q18	q19
q19									q20
q20

q₂₁ – состояние ошибки. Во все пустые клетки таблицы 5 следует вписать q_21, так как только в этом случае эта таблица задает полностью определенный детерминированный конечный автомат.

Рисунок 2. Граф переходов детерминированного автомата.