ROUGH DRAFT authorea.com/102821
Main Data History
Export
Show Index Toggle 0 comments
  •  Quick Edit
  • Lista 1

    Lista 1

    Zadanie 1

    \(L\) to język tych słów nad alfabetem \(\{0, 1\}\), które na dziesiątej pozycji od końca ma 0.

    Dowód nie wprost.
    Załóżmy, że istnieje automat \(A\), który rozpoznaje \(L\) a liczba jego stanów jest mniejsza od 1024.
    Weźmy wszystkie słowa postaci \(\{0,1\}^{10}\) – jest ich dokładnie 1024. Wiemy, że przynajmniej dwa słowa, \(w\) i \(v\) kończą się w tym samym stanie \(q\), z zasady szufladkowej. Istnieje takie \(k\), że \(w[k] \neq v[k]\). Teraz dopisujemy do każdego spośród \(w\), \(v\) słowo \(u = 1^{10-k}\). Ponieważ \(A\) jest deterministyczny, a \(w\) i \(v\) kończą się w identycznym stanie \(q\) to \(\hat{\delta}(q_0, wu) = \hat{\delta}(q_0, vu)\), ale \(wu\) i \(vu\) różnią się na dziesiątej pozycji od końca, więc \(\hat{\delta}(q_0, wu) \neq \hat{\delta}(q_0, vu)\). \(\Box\)

    Część z was pewnie po przeczytaniu następnego zadania zacznie sie zastanawiać, czy to faktycznie 1024, jak coś zapraszam po wyjaśnienia na priv. Zarówno 1,2 zadanie dobrze rozważać łącznie z zadaniem 9 (twierdzeniem o indeksie).

    Zadanie 2

    Odpowiedź: 16. Zbudowanie automatu nie jest trudne. Wystarczy się zastanowić, co tak naprawdę musimy pamiętać. Mogę podpowiedzieć, że będzie 15 stanów, w których faktycznie “kręci się” automat i jeden stan startowy (stan dla słowa pustego). Pokazanie automatu, to wykazanie, że 16 stanów wystarczy.
    By pokazać, że potrzeba 16 stanów wykonujemy podobne rozumowanie, co zadanie wcześniej. Oczywiście nie bierzemy wszystkich trzyliterowych słów. Wybieramy tylko pewien podzbiór. Patrząc na automat powinno to być dość proste.