Note de curs, clasele 9-10, 16 ianuarie 2014

From Algopedia
Jump to: navigation, search

Căutări pe stringuri folosind automate finite

Să considerăm din nou automatul finit determinist care recunoaște șirurile care conțin subșirul abacaba. Observăm că tranzițiile (atât cele înainte, cât și cele înapoi) au forma

δ(q, a) = r, unde r este starea maximă pentru care Pr ⊐ Pqa

Putem generaliza această observație într-un algoritm de construire a DFA pentru orice pattern P, astfel:

  • definim funcția de sufix: Pentru un pattern P fixat, σ(x) = max {k | Pkx}
    • σ(x) este minim 0 și maxim m când Px
  • construim automatul folosind funcția de tranziție: δ(q, a) = σ(Pqa)

Scriem pseudocodul pentru căutare. Odată ce am construit automatul (adică matricea de tranziție), algoritmul de căutare este banal și durează O(n).

Rămâne, deci, să arătăm că automatul definit mai sus se comportă corect. Ideea demonstrației este că automatul este în starea σ(Si) după citirea caracterului primelor i caractere din S, deci va fi în starea m (de acceptare) ori de câte ori găsește șablonul P (și numai atunci). Demonstrația riguroasă se face în trei pași:

  1. Pentru orice șir x și orice caracter a, σ(xa) ≤ σ(x) + 1
    1. demonstrație: fie r = σ(xa). Atunci Pr ⊐ xa, deci Pr-1 ⊐ x, deci r - 1 ≤ σ(x).
    2. în cuvinte, săgețile automatului merg cel mult cu un pas spre dreapta
  2. Pentru orice șir x și orice caracter a, dacă q = σ(x), atunci σ(xa) = σ(Pqa)
    1. demonstrație: grafică, cu șirurile xa, Pqa și Pr
    2. în cuvinte, funcția de sufix (și implicit matricea de tranziție) nu depind de tot șirul, ci doar de ultimele caractere relevante (care sunt prefix al lui P)
  3. Dacă Φ(Si) este starea automatului după citirea a i caractere din S"', atunci Φ(Si) = σ(Si)
    1. demonstrație: prin inducție după i

Cum construim automatul? Mergând după definiție, pentru fiecare q = 0, 1, ..., m și pentru fiecare aΣ, trebuie să calculăm cel mai lung prefix al lui P care este sufix al lui Pqa. Implementarea naivă rulează în O(m3 |Σ|).

Există o metodă de a reduce această complexitate la O(m |Σ|), despre care vom vorbi după algoritmul KMP. Ea ne oferă, așadar un timp total de O(m |Σ| + n) pentru preprocesare + căutare. Deoarece algoritmul KMP este O(n), el este net superior, iar metoda cu DFA prezintă un interes pur teoretic.

Algoritmul Knuth-Morris-Pratt (KMP)

Algoritmul KMP pornește de la teoria automatelor finite, dar îmbunătățește mult algoritmul de căutare cu DFA. El ignoră funcția de tranziție δ, ceea ce înseamnă că nu mai depinde de mărimea alfabetului, |Σ|.

Care este scopul căutărilor cu automate? Este să evite să verifice shift-uri (deplasări) care sunt garantat invalide. Dacă automatul este în starea q, iar următorul caracter nu se potrivește, automatul va trece în starea maximă posibilă k unde ultimele k caractere citite se potrivesc. Toate stările între k și q corespund, în mod necesar, unor deplasări invalide, din modalitatea de construire a automatului.

De aceea, ne este util să răspundem la întrebarea: dacă primele q caractere din P se potrivesc la deplasarea curentă (fie ea i), care este următoarea deplasare j pe care are rost să o încercăm? Desigur, numărul de caractere potrivite la poziția j respectă relația i + q = j + k. Dorim deci să minimizăm valoarea j sau, echivalent, să maximizăm valoarea k. În mod natural, Pk ⊏ Pq. Dorim și ca Pk ⊐ Pq.

Definim funcția de prefix, π astfel: π[q] = max{k | k < q și PkPq }

În cuvinte, π[q] este lungimea cel mai lung prefix care este și sufix al lui Pq.

Din nou, algoritmul naiv de construcție al lui π este O(m3). Totuși, algoritmul KMP construiește π în O(n):

<source>

 function preprocesare(P) {
   π[0] = 0;
   k = 0;
   for (q = 1; q < m; q++) {
     while ((k > 0)) && (P[k] != P[q]) {
       k = π[k - 1];
     }
     if (P[k] == P[q]) {
       k++;
     }
     π[q] = k;
   }
 }

</source>

Se demonstrează ușor că complexitatea totală a algoritmului este O(m): k este incrementat de cel mult m ori, deci și numărul de decrementări este O(m).

Algoritmul de căutare este:

<source>

 function KMP(S, P) {
   q = 0; // starea curentă
   for (i = 0; i < n; i++) {
     while ((q > 0)) && (P[q] != S[i]) {
       q = π[q - 1];
     }
     if (P[q] == S[i]) {
       q++;
     }
     if (q == m) {
       print "Am găsit P în S la poziția i" // i este poziția de final
     }
   }
 }

</source>

Ca fapt divers, putem folosi vectorul π pentru a calcula matricea de tranziție în O(m |Σ|) pentru algoritmul de căutare cu DFA. Linia q din matrice se obține copiind linia π[q], mai puțin δ(q, P[q]) = q + 1.

Automate finite, continuare

Verificăm tema de lecția trecută (DFA-uri pentru patru limbaje).

Vom construi diverse alte exemple de automate finite, ca să ne obișnuim cu designul lor. Să se construiască DFA pentru limbajele:

  • *temă* șiruri care conțin un număr par de 0 și conțin cel puțin un 1
  • *temă* șiruri care încep și se termină cu același simbol
  • șiruri de forma Σ*1Σ*1Σ*1Σ*, ΣΣ0Σ*, !(Σ*110Σ*), orice în afară de ε.
  • *temă* să se arate că, pentru orice număr natural n, există un DFA care acceptă șiruri de cifre zecimale care reprezintă numere divizibile cu n.

Automatele ne ajută adesea în multe probleme de analiză a șirurilor de caractere. Pentru aceasta, funcția de tranziție poate conține și acțiuni (cod de executat).

  • *temă* Să se deseneze un automat care decide dacă un număr are exact două cifre distincte;
  • *temă* Să se deseneze un automat care numără cuvintele și numerele dintr-un text.

Operații pe limbaje regulate

  • operații regulate: ∪ (reuniune), ∩ (intersecție), ∘ (concatenare), * (star)
  • exemplu: dacă L1 = { câine, lup } și L2 = { alb, negru }, atunci
    • L1 ∪ L2 = { câine, lup, alb, negru },
    • L1 ∩ L2 = ∅
    • L1 ∘ L2 = { câinealb, câinenegru, lupalb, lupnegru }
    • L1* = { ε, câine, lup, câinecâine, câinelup, lupcâine, luplup, câinecâinecâine, câinecâinelup, ... }

Teoremă: Clasa limbajelor regulate este închisă sub operația de reuniune.

În primul rând, ce înseamnă „închiderea”? Înseamnă că, pentru orice limbaje regulate A și B, limbajul A ∪ B este de asemenea regulat. Echivalent, dându-se DFA care decid A și respectiv B, există un DFA care decide A ∪ B.

Cum demonstrăm aceasta? Am vrea să rulăm A pe șirul de intrare, apoi să derulăm banda și să rulăm B pe același șir. Dar modelul automatelor finite nu permite derularea benzii. De aceea, A și B trebuie rulate în paralel. Ne închipuim că ținem câte un deget pe starea curentă din A și B. Atunci automatul care decide A ∪ B va avea atâtea stări câte combinații de poziții ale degetelor.

Concret, fie M1 și M2 automatele care decid limbajul A și respectiv B. Vom construi automatul M care decide limbajul A ∪ B.

Construcția formală: Q = A ⨯ B = { (r1, r2) | r1 ∈ A și r2 ∈ B } etc.

În mod similar putem demonstra că, dacă A, B și C sunt limbaje regulate, atunci și limbajul Vot este regulat, unde Vot(A, B, C) = { w | w este în cel puțin două dintre A, B și C }.

Demonstrația pentru închiderea sub operația de intersecție este aproape identică. Pentru concatenare și star, mai avem nevoie de o noțiune.

Nedeterminism

Într-un automat determinist, la fiecare pas avem o singură variantă de a continua, căci există exact o săgeată pentru fiecare simbol din alfabet. Într-un automat finit nedeterminist (NFA), se modifică două lucruri:

  • Pot exista una sau mai multe variante sau nicio variantă pentru o stare și un simbol.
  • Între două stări se poate face o tranziție pe șirul vid, notat cu ε. Această tranziție nu consumă niciun simbol de pe bandă.

Un NFA funcționează simultan pe toate ramurile. Dacă ajunge într-o stare și citește un simbol care permite continuări multiple, NFA-ul se ramifică. Dacă simbolul nu permite nicio continuare, acea copie a NFA-ului moare. Dacă oricare din copiile NFA-ului acceptă șirul, atunci NFA-ul acceptă șirul.

Exemplu: un NFA cu 4 stări. Starea q3 este finală. Matricea de tranziții este: δ(0, 0) = 0; δ(0, 1) = {0, 1}; δ(1, 0) = 2; δ(1, ε) = 2; δ(2, 1) = 3; δ(3, 0) = 3; δ(3, 1) = 3;

Ce face acest NFA pe șirurile 010110 și 010? Ce limbaj decide el? Cum ar arăta un DFA echivalent?

Alte exemple:

  • NFA și DFA pentru șirurile care au pe antepenultima poziție valoarea 1;
  • *temă* NFA și DFA pentru șirurile de forma 0^k | k multiplu de 2 sau de 3.

Observăm că automatele finite nedeterministe arată mai scurt și mai ușor de înțeles decât echivalentele lor deterministe.

  • Definiție formală: δ este acum o funcție definită pe Σ ∪ { ε } cu valori în 𝒫(Q).

Teoremă: pentru orice NFA există un DFA echivalent (care decide același limbaj).

Demonstrație intuitivă: construim un DFA cu 2|Q| stări. *temă* Care sunt specificațiile acestui DFA?

Cu ajutorul automatelor nedeterministe, putem arăta că clasa limbajelor regulate este închisă sub toate cele patru operații regulate. *temă* Construiți demonstrațiile pentru operațiile de concatenare și star!

Expresii regulate

Expresiile regulate servesc (printre altele) la descrierea mai succintă a limbajelor. O expresie regulată R poate fi:

  1. un simbol a ∈ Σ
  2. ε (șirul vid)
  3. Φ (limbajul vid)
  4. R1 ∪ R2, unde R1 și R2 sunt expresii regulate
  5. R1 ∘ R2, unde R1 și R2 sunt expresii regulate
  6. R1*, unde R1 este o expresie regulată

Exemple etc.

Un limbaj este regulat dacă și numai dacă este descris de o expresie regulată. Demonstrație: construim NFA din expresia regulată și invers.

Limbaje neregulate

Nu toate limbajele sunt regulate. Cu alte cuvinte, unele limbaje nu pot fi decise de niciun DFA. Să considerăm, de exemplu, limbajul șirurilor de forma 0n1n. Intuitiv, ce ar trebui să rețină un automat despre șirul citit până atunci? Ar trebui să rețină cel puțin numărul de zerouri văzute. Dar, pentru a stoca numărul n, este nevoie de O(log n) biți, iar n poate fi arbitrar de mare. Din această cauză, și numărul de stări ale automatului va fi arbitrar de mare, ceea ce contrazice condiția de finitudine a automatului.

Intuiția noastră despre care limbaje sunt sau nu regulate ne poate păcăli. De exemplu:

  • L = { w | w palindrom } este neregulat
  • L = { w | w are un număr egal de 0 și 1 } este neregulat
  • Dar L = { w | w are un număr egal de 01 și 10 } este regulat! (*temă* De ce?)

Pentru a facilita depistarea limbajelor neregulate, prezentăm lema de pompare.

Lema de pompare pentru limbaje regulate

Lema de pompare prezintă o proprietate comună tuturor limbajelor regulate. Dacă putem demonstra că un limbaj nu are această proprietate, atunci el nu este regulat.

Lema de pompare: Dacă A este un limbaj regulat, atunci există un număr p (numit lungime de pompare) astfel încât, pentru orice șir sA de lungime cel puțin p, atunci s poate fi împărțit în trei bucăți, s = xyz, care respectă condițiile:

  1. Pentru orice i≥ 0, xyizA
  2. |y| > 0
  3. |xy| ≤ p

Demonstrație (neriguroasă): fie M un DFA care decide limbajul A. Atunci alegem p ca fiind numărul de stări al lui M. Orice șir din A indică o cale de la starea inițială la o stare finală. Pentru șirurile care au lungime cel puțin p, calea trece prin cel puțin p + 1 stări, deci există o stare repetată. Definim x, y și z ca fiind bucata din șir dinaintea stării repetate, dintre prima și ultima apariție a stării repetate, respectiv de după ultima apariție a stării repetate.

Acum putem demonstra că limbajul L = { 0n1n | n ≥ 0 } nu este regulat. Fie p lungimea de pompare. Alegem s = 0p1p. Atunci s nu poate fi pompat, deoarece, oricum am alege s = xyz, șirul s' = xyyz nu va avea un număr egal de 0 și de 1.

*temă* Gândiți-vă cum demonstrați că următoarele limbaje sunt neregulate:

  • L = { w | w are un număr egal de 0 și 1 }. Hint: aici avem nevoie și de condiția 3 a lemei de pompare.
  • L = { w | w palindrom }. Hint: alegem s = 0p10p.
  • L = { ww | w ∈ {0, 1}* }. Hint: alegem s = 0p10p1.
  • L = { 1n2 | n ≥ 0 }. Hint: șirul pătratelor perfecte nu conține progresii aritmetice infinite.
  • L = { 0i1j | i ≥ j }. Hint: aici pompăm în jos (din prima condiție de pompare folosim cazul i = 0).