Automaty związane z rozpoznawaniem wzorca

Deterministyczny automat z zadania ?? z punktu ?? rozpoznający język $\Sigma^{*}w$ można skonstruować biorąc za stany wszystkie prefiksy słowa $w$ (a zatem $|w|+1$ stanów) oraz przejścia $v\stackrel{a}{\rightarrow}u$ , gdzie $u$ jest maksymalnym sufiksem słowa $va$ będącym jednocześnie prefiksem $w$ . (Efektywna konstrukcja tegoż automatu, patrz zadanie w punkcie .) Dowieść, że liczba nietrywialnych przejść ,,wstecznych”, tj. przejść postaci $v\stackrel{a}{\rightarrow}u$ , gdzie $|v|>|u|>0$ , jest nie większa niż $|w|$ . Zauważmy, że daje to możliwość reprezentacji automatu o rozmiarze proporcjonalnym do $|w|$ (przejścia postaci $v\stackrel{a}{\rightarrow}\epsilon$ możemy
pominąć).

Wskazówka. Wykazać, że dla każdej liczby $k$ istnieje co najwyżej jedno nietrywialne przejście wsteczne, takie, że $|va|-|u|=k$ .
Rozpoznawanie podsłów.
1. Dla danego słowa $w$ o długości $|w|=n$ skonstruować automat deterministyczny o $\leq 2n+1$ stanach rozpoznający dokładnie zbiór sufiksów słowa $w$ .
  
  Wskazówka. Jako stany automatu można wziąć zbiory pozycji $S_{x}$ ( $S_{x}\subseteq\{ 0,1,\ldots,n\}$ ) kończących wystąpienie $x$ jako podsłowa słowa $w$ . Oszacowanie na liczbę stanów wynika ze spostrzeżenia, że różne zbiory $S_{x}$ , $S_{y}$ są albo w relacji inkluzji albo rozłączne, a zatem, ze względu na inkluzję, tworzą drzewo o nie więcej niż $n$ liściach.
2. Powyższy automat zawiera stan typu ,,czarna dziura”, mianowicie stan $\emptyset=S_{x}$ , gdzie $x$ nie jest podsłowem $w$ . Dowieść, że liczbę przejść nie prowadzących do stanu $\emptyset$ można oszacować z góry przez $3n$ .
  
  Wskazówka. Wziąć drzewo rozpinające grafu automatu i oszacować liczbę pozostałych krawędzi przez liczbę sufiksów $w$ .
3. Opisany wyżej automat jest minimalny dla zbioru sufiksów. Tę samą konstrukcję można zastosować również do rozpoznawania zbioru wszystkich podsłów słowa $w$ , ale otrzymany automat nie musi być minimalny. Podać przykład.

Informatyka MIMUW

Automaty związane z rozpoznawaniem wzorca