LFA - Curs,Saptamana a 11-a

Buna ziua,

Astazi in saptamana a 11-a va rog sa cititi, pentru inceput ceea ce am numit "Cursul din saptamana a 10-a", in realitate notitele sunt scrise tot azi, dar am separat pe o pagina noua o tema tehnica, Minimizarea automatelor. Continutul e in manual, pe blog aveti explicatii.

Aici este continuarea:deschideti maualul la pagina 65 [mergem pina la pg 68]

Automate finite cu epsilon-miscari (eu le mai zic, cu epsilon-tranzitii) [pg65]

De ce ne ocupam de ele ? Fiindca ajuta in procesul de definire al automatului echivalent cu o expresie regulara. Da, acele reg-exp-uri folosite de programatori.

Cititi def 2.12 pg 65.
Va las sa va ganditi oleaca la ea. Ce inseamna formula:

    δ :Q x ( Σ U {ε} ) -> P(Q)

unde P(Q) sunt partile lui Q, ca la AFN-uri. Unde este modificarea fata de AFN-uri (automate finite nedeterministe)?

Indicatie: acolo aveam:
     δ :Q x ( Σ ) -> P(Q)

Este evident ca mai avem ceva, un epsilon, sirul vid, care "se adauga" alfabetului.Ca si cum automatul ar putea trece dintr-o stare in alta, nu prin citirea UNEI litere (simbol) de la intrare ci prin citirea a nimic (stringul vid "", notat epsilon) de la intrare.

Grafic locul unde va avea loc epsilon tranzitia se deseneaza exact cum erati
obisnuiti dar nu e o litera pe "sageata" ci un epsilon. ε
                
                   ε
(p) ------------------ > (q)

 linia e continua, iar p si q sunt incercuite cu cercuri complete nu cu paranteze.

Ce e cu teorema 2.6 ?

Cititi va rog teorema 2.6. [pg 65]

Ea ne spune ca desi ni se pare ca aceste automate "pot" mai mult, in materie de recunoastere a limbajelor, ele nu aduc de fapt nimic nou, sunt echivalente cu
cele fara epsilon-tranzitii.

Demonstratia este constructiva, iar pentru a construi acea multime, "I indice epsilon de delta" de la pg 67 jos, putem folosi un tabel cum este cel de la pagina 67 sus.

Considerati pagina 66 un exemplu de pregatiri pentru a construi automatul echivalent.

 Plan:

Observati ca daca luam automatul (de la pg 66 sus), ca exemplu,
putem elimina din el arcele cu litere si raman numai cele cu epsilon,
(pagina 66 mijloc) si fiindca starile legate prin epsilon-uri sunt impreuna  ;) , putem sa facem o tabela cum este cea de la pagina 67 sus.

 Un exemplu clasic de automat (e in multe carti):

Acum am inlaturat arcele cu litere pe ele.

 Iar aceasta tabela care imi da valoarea de adevar a predicatului: "Exista drum in graf de la i la j ?"

Acum  puteti citi algoritmul general de transformare,la punctul 2 pg 67-pg 68.

In final, automatul din ultima tabela se poate desena, vedeti desenul alaturi.

Exercitiul 1: Refaceti , intai dupa carte, apoi dupa formulele de la pagina 68 sus toate calculele pentru D si delta1 de la pagina  68.

Exercitiul 2:  Luati alt automat cu epsilon tranzitii, dat prin tabela ca la pg 68 sus si transformati-l, ca la pg 68 jos.

Urmeaza laboratorul de compilatoare, pagina noua.