LFA - Curs Saptamana a 10- a

Buna ziua,

Acest curs este  inclus in cursul saptamanii 11. Desi are pagina web separata.
Aceasta pagina web sprijina citirea paginilor :58-65 din manual.

In saptamana a 10- a au fost sarbatorile Pascale si zi libera.
In mod normal predam aici niste rezultate tehnice, cum ar fi :

MINIMIZAREA AUTOMATELOR

Continut:
2.6 Minimizarea automatelor finite (deterministe) [pg 58]
 Un algoritm pentru a determina daca doua stari sunt echivalente [pg61-62]
Def 2.11. Defineste un AFD redus.
2.7  Constructia unui AFD redus.
2.8 Automate cu epsilon-miscari [pg 65-68]


Cateva comentarii despre ele, atentie, partea matematica este mai dificila aici, incerc sa dau niste explicatii intuitive:

2.6 Minimizarea automatelor finite (deterministe) [pg 58]
Ideea de aici:

Fie un automat:
       x
 (A)----->(B) 
   |          |
y |          | z
   |          |
  \|/        \|/
 (D)      (E)
   |       /
a |      / a
  \|/  |/_
  (F)

Unde (F)  este starea finala.

Observati ca in raport cu starea finala, cele doua stari (D) si (E) sunt cumva echivalente, "de grad 1".
Se vede ca exista un cuvant de lungime 1, cu proprietatea:

( D, a)  |--* (F, epsilon)
( E, a)  |--* (F, epsilon)

Si in acest caz automatul poate fi cumva "impaturit" folosind aceasta relatie de echivalenta, suprapunand nodurile echivalente...

       x
 (A)----->(B) 
   |          |
y |          | z
   |          |
  \|/        \|/
     (DE)
      |     
   a |     
     \|/ 
    (F)

Deabia acum puteti citi definitia 2.7. Care este inspirata dar nu identica cu ceea ce am desenat mai sus ... vedeti pg[58].

Abia acum puteti vedea def 2.7, 2.8, 2.9.

Def 2.7. [pg 58] Defineste doua stari q1,q2, ca fiind diferentiate de un x din sigma stelat, daca avem :

  (q1,x) |---* (q3,epsilon)                (1)
  (q2,x) |---* (q4,epsilon)

si daca impartim starile in doua parti, F si Q-F, se mai impune o conditie:
q3 si q4 nu apartin simultan lui F sau lui Q-F, ori cel putin una dintre relatiile (1) nu are loc.

Din pacate, acest fel de diferentiabilitate / echivalenta depinde de lungimea cuvintelor implicate. De aici definitia 2.8.

Def 2.8 [pg 59] Doua stari q1,q2 sunt k-diferentiate de un cuvant x din sigma stelat , |x| < k, daca si numai daca au loc conditiile definitiei 2.7.

Cumva, daca gasim un cuvant de lungime |x| <k, pt care starile sunt diferentiabile, deci evolutia automatului din cele doua stari cu acel cuvant la intrare NU se termina la fel (fie in F fie in Q-F), atunci pot spune ca starile sunt k diferentiate..

Obs: k-diferentiate  implica k+1 diferentiate. Invers, in termeni de echivalenta de stari (se def in def 2.9):
 k+1 echivalente implica faptul ca sunt  k echivalente
k echivalente implica faptul ca sunt k-1 echivalente
samd.

Obsercati ca diferentiabilitatea depinde de existenta unor cuvinte cu anumite proprietati. Atunci echivalenta depinde de INexistenta unor cuvinte cu acele proprietati.

De aici ajungem usor la def 2.9:

Def 2.9: Doua stari q1 si q2 sunt echivalente daca nu gasim nici o secventa care sa le diferentieze.
 Adica pt orice k, ele nu sunt k-diferentiate.

Atunci cand luam in considerare si pe k, obtinem o notiune de k-echivalenta.

Def 2.10: Pt un automat M si un numar natural nenengativ, doua stari q1 q2 sunt k-echivalente daca si numai daca nu exista nici o secventa x, |x| <= k care sa le diferentieze.
                 
                 k      
                 _
Notam q1 = q2.  [pg 60 sus].

Urmeaza o serie de proprietati tehnice ale relatiei de echivalenta:

Cititi pg [60, 61,62,63,64]

Si in final putem construi un automat:  [pg 63-64]
- fara stari inaccesibile
- fara stari neproductive
- si pe multimea partilor multimii Q in raport cu relatia de echivalenta.
(Relatia de echivalenta imparte Q in clase de echivalenta).

Pauza.
Trecem la o alta pagina.