Strona główna › Języki, automaty i obliczenia - zbiór zadań

Automaty związane z rozpoznawaniem wzorca

pon., 03/21/2011 - 14:34 — ciebie
  1. 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\).

  2. 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.