Materiał pomocniczy cz. 1 (poprawkowa)

1.Minimalizacja DAS
Opis postępowania:
a)Eliminujemy stany do których nie możemy dotrzeć ze stanu 
początkowego (jeśli takie istnieją)
b)Identyfikujemy zbiory (bloki) stanów równoważnych (poprzez 
tablicę rozróżnialności) a następnie budujemy nowy DAS w oparciu o 
te bloki (każdy blok/zbiór traktujemy jako jeden stan)

Konstrukcja tablicy rozróżnialności:
I.Każda para stanów (p,q) gdzie p jest stanem akceptującym a q jest 
nieakceptującym jest rozróżnialna.
II.Indukcyjnie: jeżeli p i q są rozróżnialną parą stanów, oraz p=(r,a) i 

q= (s,a) (gdzie a – dodolwny symbol z alfabetu minializowanego 

DAS; r,s – inne stany) wówczas para (r,s) jest rozróżnialna.
przykład:
rozważmy następujący DAS:

stan

pobierane 

symbole / nowy 

stan

0

1

A

B

A

B

A

C

C

D

B

*D

D

A

E

D

F

F

G

E

G

F

G

H

G

D

ponieważ macierz rozróżnialności jest symetryczna, 
będziemy zajmowali się tylko jej dolną częścią. 
Stosując wyżej opisany algorytm (zamiast symbolu „” 

pojawi się symbol „ƒƒƒf”) dla wspomnianego przykładu 
otrzymujemy (napisałem dla Państwa funkcję w 
matlabie która dla wejścia w pliku excelowym pokazuje 
kolejne kroki):

Ponieważ stan H jest nieosiągalny, możemy go od razu usunąć z naszych 
rozważań:

>> tablica_rozroznialnosci('przyklad1.xls')
po zidentyfikowaniu par: (stan akceptujący, stan_nieakceptujący) nasza tablica rozróżnialności wygląda tak:
 
tablica teraz wyglada tak: 
    ' '    'A'      'B'      'C'      'D'      'E'      'F'      'G'  
    'A'    '   '    '   '    '   '    '   '    '   '    '   '    '   '
    'B'    '[ ]'    '   '    '   '    '   '    '   '    '   '    '   '
    'C'    '[ ]'    '[ ]'    '   '    '   '    '   '    '   '    '   '
    'D'    '[x]'    '[x]'    '[x]'    '   '    '   '    '   '    '   '
    'E'    '[ ]'    '[ ]'    '[ ]'    '[x]'    '   '    '   '    '   '
    'F'    '[ ]'    '[ ]'    '[ ]'    '[x]'    '[ ]'    '   '    '   '
    'G'    '[ ]'    '[ ]'    '[ ]'    '[x]'    '[ ]'    '[ ]'    '   '

poniewaz stany D i A sa rozroznialne oraz f(C,0)=D i f(B,0)=A wiec stany: C i B sa rozroznialne
poniewaz stany D i A sa rozroznialne oraz f(E,0)=D i f(B,0)=A wiec stany: E i B sa rozroznialne
poniewaz stany D i B sa rozroznialne oraz f(C,0)=D i f(A,0)=B wiec stany: C i A sa rozroznialne
poniewaz stany D i B sa rozroznialne oraz f(E,0)=D i f(A,0)=B wiec stany: E i A sa rozroznialne
poniewaz stany F i D sa rozroznialne oraz f(G,0)=F i f(C,0)=D wiec stany: G i C sa rozroznialne
poniewaz stany F i D sa rozroznialne oraz f(G,0)=F i f(E,0)=D wiec stany: G i E sa rozroznialne
poniewaz stany G i D sa rozroznialne oraz f(F,0)=G i f(C,0)=D wiec stany: F i C sa rozroznialne
poniewaz stany G i D sa rozroznialne oraz f(F,0)=G i f(E,0)=D wiec stany: F i E sa rozroznialne

tablica teraz wyglada tak: 
    ' '    'A'      'B'      'C'      'D'      'E'      'F'      'G'  
    'A'    '   '    '   '    '   '    '   '    '   '    '   '    '   '
    'B'    '[ ]'    '   '    '   '    '   '    '   '    '   '    '   '
    'C'    '[x]'    '[x]'    '   '    '   '    '   '    '   '    '   '
    'D'    '[x]'    '[x]'    '[x]'    '   '    '   '    '   '    '   '
    'E'    '[x]'    '[x]'    '[ ]'    '[x]'    '   '    '   '    '   '
    'F'    '[ ]'    '[ ]'    '[x]'    '[x]'    '[x]'    '   '    '   '
    'G'    '[ ]'    '[ ]'    '[x]'    '[x]'    '[x]'    '[ ]'    '   '

poniewaz stany C i A sa rozroznialne oraz f(B,1)=C i f(A,1)=A wiec stany: B i A sa rozroznialne
poniewaz stany E i A sa rozroznialne oraz f(F,1)=E i f(A,1)=A wiec stany: F i A sa rozroznialne
poniewaz stany G i C sa rozroznialne oraz f(G,1)=G i f(B,1)=C wiec stany: G i B sa rozroznialne
poniewaz stany G i E sa rozroznialne oraz f(G,1)=G i f(F,1)=E wiec stany: G i F sa rozroznialne
 
tablica teraz wyglada tak: 
    ' '    'A'      'B'      'C'      'D'      'E'      'F'      'G'  
    'A'    '   '    '   '    '   '    '   '    '   '    '   '    '   '
    'B'    '[x]'    '   '    '   '    '   '    '   '    '   '    '   '
    'C'    '[x]'    '[x]'    '   '    '   '    '   '    '   '    '   '
    'D'    '[x]'    '[x]'    '[x]'    '   '    '   '    '   '    '   '
    'E'    '[x]'    '[x]'    '[ ]'    '[x]'    '   '    '   '    '   '
    'F'    '[x]'    '[ ]'    '[x]'    '[x]'    '[x]'    '   '    '   '
    'G'    '[ ]'    '[x]'    '[x]'    '[x]'    '[x]'    '[x]'    '   '

 
wiecej par rozroznialnych nie jestesmy juz w stanie zidentyfikowac

wiemy zatem, że bloki {G,A}, {F,B} , {C,E}, {D} są blokami stanów 
równoważnych (możemy zatem traktować ja jako jeden stan (ogólnie 
bloki mogą zawierać oczywiście większą liczbę stanów niż 2) ).
Teraz pozostała już najłatwiejsza część przedstawienia DASu w 
oparciu o wyznaczone wcześniej bloki czyli:

                                       albo lepiej 
                                       rozpisując od 
                                       razu w oparciu
                                       o bloki:        ->

w ogólności pamiętajmy, że blok który zawiera stan początkowy jest 
teraz stanem początkowym, wszystkie bloki, które zawierają choć 
jeden stan końcowy są stanami końcowymi

teraz możemy jeszcze ładniej zaetykietować nowe stany (A:={G,A,} 
B:={F,B}, C:={C,E}, D:=D) i otrzymamy:

                                                                                   i to jest 
ostateczna odpowiedź.

stan

pobierane symbole 

/ nowy stan

0

1

G,A}

{F,B}

{G,A}

{F,B}

{G,A}

{C,E}

{C,E}

D

{F,B}

*D

D

{G,A}

{C,E}

D

{F,B}

{F,B}

{G,A}

{C,E}

G,A}

{F,B}

{G,A}