Zbiór - pojęcie pierwotne

iloczyn kartezjański zbiorów

to pojęcie można rozszerzyć

Relacja

każdy podzbiór iloczynu kartezjańskiego
spełniający relację
.

Relacja dwuargumentowa
określona w zbiorze A jest

zwrotna

symetryczna

przechodnia

Relacja porządkująca
(dwuargumentowa w zbiorze A)

jeżeli jest przechodnia i dla dowolnych dwóch elementów a, b zbioru A spełniony jest jeden i tylko jeden z trzech następujących warunków:

Oznacza to, że dla dowolnych elementów
albo
albo też jedna i tylko jedna z par (a,b) i (b,a) należy do zbioru
.

Zbiorem uporządkowanym nazywamy parę (A,
).

Określenie w zbiorze A kilku relacji porządkujących oznacza uporządkowanie tego zbioru na kilka sposobów.

Dwuargumentową relację
określoną w zbiorze A nazywamy relację równoważności, jeżeli jest to relacja zwrotna, symetryczna i przechodnia.

Klasa równoważności elementu a.

ze zwrotności:
jest

Jeżeli
i z definicji
.

Na odwrót, jeśli
to
jest
.

Z przechodniości relacji
, czyli
, co oznacza, że
.

a więc mamy równoważność

z analogicznych powodów jest

Dla dowolnych elementów a i b zbioru A mamy związek:

Dwie klasy równoważności
,
albo nie mają żadnych elementów wspólnych, albo są identyczne.

Jeżeli para a,b spełnia relację
to można napisać

Relacja równoważności
dzieli zbiór A na rozłączne klasy równoważności. Dwa elementy a i b ze zbioru A należą do jednej klasy równoważności wtedy i tylko wtedy, gdy spełniają relację
, w przeciwnym wypadku należą zawsze do innych klas.

Przykłady relacji różnowartościowych

A - zbiór wszystkich liczb całkowitych

m - dowolna liczba całkowita dodatnia

liczby całkowite a,b równe modulo m, jeżeli ich różnica jest podzielna przez m.

Ta relacja jest r. różnowartościową. Dzieli ona zbiór A liczb całkowitych na m zbiorów rozłącznych.

A₀ wszystkie liczby podzielne przez m

A₁ wszystkie liczby, dla których reszta z dzielenia przez m wynosi 1

A₂ wszystkie liczby, dla których reszta z dzielenia przez m wynosi 2

Dla m=2
liczby całkowite a, b równe modulo 2.

Minimalizacja automatu.

Można rozszerzyć funkcję przejść δ i wyjść  tak, by mogły wskazywać następne stany i wyjścia nie tylko dla pojedynczych liter alfabetu wejściowego, ale także dla słów ze zbioru X^*.

Odpowiedź automatu na słowo
k = 1, 2, …, m

Pod tym pojęciem rozumiemy ciąg symboli wejściowych. Muszą być spełnione warunki:

1. Słowo
   jest w pełni dopuszczalne, tzn. dla każdego k = 1, 2, …, m wartość funkcji (q,x_k) jest określona.

2. 
   

3. 
   

Dla ustalenia uwagi przyjmijmy model Moore'a.

A - automat Moore'a deterministyczny zupełny. A=(Q, X, δ, Y, )

Słowo x rozróżnia dwa stany q_i oraz q_j jeżeli
tzn. wyjścia w stanach osiągalnych ze stanów q_i oraz q_j pod wpływem słowa x są różne.

Dwa stany automatu k-równoważne

czyli nie istnieje taki ciąg wejściowy x (o długości k), który by rozróżnił stany q_i,q_j.

Wniosek 1. Stany q_i oraz q_j k-równoważne są również l-równoważne
.

Wniosek 2. Stany q_i oraz q_j k-rozróżnialne są również l-rozróżnialne
.

Automat minimalny

A_min - automat, którego zbiór stanów nie zawiera stanów różnych wzajemnie równoważnych.

Jak badać, czy dwa stany automatu są równoważne?

Jak długie słowa trzeba podawać na wejście automatu, by sprawdzić równoważność stanów?

Twierdzenie.

Zał.: A=(Q, X, δ, Y, ) automat Moore'a deterministyczny zupełny posiadający n stanów.

Teza: stany q_i oraz q_j są równoważne
,
.

Dowód.

Warunek konieczny:
dla dowolnego
(z wniosku 2).

Warunek dostateczny:

1)

2)

Jeżeli
to relacja
dzieli zbiór stanów wewn. automatu na dwie klasy
oraz

.

Jeżeli
to relacja
zawiera co najmniej jedną klasę równoważności więcej niż relacja
. Zbiory Q1 i Q0 mają nie więcej niż n-1 elementów (w tym miejscu wykluczamy przypadki gdy f. wyjść przyjmuje jedną wartość - wtedy dowód jest trywialny). Z relacji
możemy otrzymać nie więcej niż n-2 kolejnych nowych relacji k-równoważności. Jeżeli dla pewnego k mamy
to na podstawie (2)
Czyli równoważność
oznacza pierwszą z relacji
dla której zachodzi
.

A więc ma miejsce następujące zawieranie klas równoważności:

Wniosek. Dwa stany, jeżeli są rozróżnialne, to za pomocą słowa wejściowego o długości mniejszej niż liczba stanów automatu.

Algorytm minimalizacji deterministycznego automatu zupełnego.

Input: deterministyczny automat zupełny Moore'a. A=(Q, X, δ, Y, )

Output: deterministyczny automat zupełny Moore'a minimalny względem A.

A_min=(Q_min, X, δ_min, Y, _min)

Krok 1.

Wyznaczyć relacje równoważności
,
, … aż dla pewnego k otrzyma się
.

Przyjąć jako relację równoważności relację
dla której
.

Krok 2.

Wyznaczyć automat minimalny A_min następująco:

(zbiór klas równoważności relacji
),

,

dla
.

Przykład.

Automat

	δ
Q	x1	x2	
q1	q2	q1	0
q2	q1	q3	0
q3	q4	q2	0
q4	q4	q1	1
q5	q4	q6	0
q6	q7	q5	0
q7	q6	q7	0
q8	q7	q4	0

Relacje równoważności
dzielą zbiór stanów Q na następujące klasy równoważności:

,

,

Trójkątna tabela relacji równoważności

v - stany równoważne

x - stany rozróżnialne

(q_k,q_l) - równoważność (rozróżnialność) q_i, q_j zależna od równoważności (rozróżnialności) stanów q_i, q_j.

Dla n-stanowego automatu n² par stanów.

Nie sprawdza się wszystkich, a tylko

q2	(q1,q2) x (q1,q3)
q3	(q2,q4) x	(q1,q4) x (q2,q3)
q4	x	x	x
q5	(q2,q4) x (q1,q6)	(q1q4) x (q3q6)	(q2q6) v	x
q6	(q2,q7) x (q1,q2)	(q1q7) v (q3q5)	(q4q7) x (q2q5)	x	(q4q7) x (q5q6)
q7	(q2,q6) v (q1,q7)	(q1,q6) x (q3,q7)	(q4,q6) x (q2,q7)	x	(q4,q6) x (q6,q7)	(q7,q6) x (q5,q7)
q8	(q2,q7) x (q1,q4)	(q1,q7) x (q3,q4)	(q4,q7) x (q2,q4)	x	(q4,q7) x (q4,q6)	(q4,q5) x	(q6,q7) x (q4,q7)
	q1	q2	q3	q4	q5	q6	q7

Automat minimalny A_min dla automatu A.

Qmin	δmin		min
		x1		x2
a	b	a	0
b	a	c	0
c	d	b	0
d	d	a	1
e	a	d	0

Minimalizacja deterministycznego automatu niezupełnego.

Relacja zgodności (oznaczana
) - zwrotna, symetryczna, ale nieprzechodnia.

Relacja ta indukuje pokrycie w zbiorze stanów.

Stany q_i oraz q_j automatu A=(Q, X, δ, Y, ) nazywamy niezgodnymi jeżeli istnieje ciąg dopuszczalny
taki, że funkcje wyjść są różne:

nieprawda, że

Co to jest ciąg dopuszczalny
?

Jest to taki ciąg liter, że funkcja przejść jest określona dla kolejnych liter, a funkcja wyjść jest określona co najmniej dla ostatniej litery w słowie, co w zapisie wygląda tak:

słowo:
jest dopuszczalne dla stanu q₁ jeżeli istnieje ciąg stanów q₁, q₂, …, q_k taki, że

oraz

(Moore)
(Mealy)

Jeżeli para stanów nie jest niezgodna, to nazywamy ją zgodną.

Podzbiór zbioru stanów
nazywamy zgodnym, jeśli każda para stanów w tym zbiorze jest zgodna.

Maksymalnym zbiorem stanów zgodnych
to taki podzbiór podzbiór, że każda para stanów jest zgodna, ale dołączenie stanu
do zbioru
powoduje, że zbiór
nie jest zgodny.

Można też zdefiniować maksymalny zbiór stanów niezgodnych

Tworzymy graf o n wierzchołkach (ilość odpowiadająca liczbie stanów).

Prosty przykład.

1	1,3 2,4
2	1,4	3,4
3	0,1 2,4	0,3	0,4
4	0,2	1,3 0,4	1,4	x
	0	1	2	3

Q\X	0	1	Y
0	1	2	-
1	3	4	-
2	4	-	-
3	0	4	0
4	1	0	1

x - niezgodne, v - zgodne, (q_i,q_j) - zgodne warunkowo

Zbiór par stanów niezgodnych

Zbiór stanów zgodnych

zwrotność

symetryczność

1

2

3

4

0

Krawędzią łączymy te wierzchołki grafu, które odpowiadają stanom niezgodnym.

Teraz należy znaleźć Z_min - minimalny zbiór stanów zgodnych.

Muszą być spełnione 2 warunki:

1. warunek pełności (w zbiorach Z_min muszą być reprezentowane wszystkie pierwotne stany)

2. Warunek zamknięcia względem funkcji przejścia δ. Stany należące do jednego ze zbiorów Z_min muszą przejść do innego zbioru Z_min pod działaniem δ.

0

4

3

2

1

0

4

3

2

1