Processing math: 100%
Strona główna › Języki, automaty i obliczenia - zbiór zadań

Automaty skończone i wyrażenia regularne

pon., 03/21/2011 - 14:32 — ciebie
  1. Dowieść, że dla dowolnych języków L,M, (L∗M∗)∗=(L∪M)∗.
  2. Dowieść, że wyrażenie regularne (00+11+(01+10)(00+11)∗(10+10))∗ reprezentuje zbiór wszystkich słów nad alfabetem {0,1}, w których zarówno liczba wystąpień 0 jak i liczba wystąpień 1 są parzyste.

    Jak najkrócej reprezentować zbiór słów, w których te liczby są tej samej parzystości?

  3. Zbudować automat nad alfabetem {0,1}, rozpoznający słowa, w których liczba jedynek na pozycjach parzystych jest parzysta, a liczba jedynek na pozycjach nieparzystych jest nieparzysta.
  4. Dodawanie. Rozważamy słowa nad alfabetem {0,1}3. Powiemy, że słowo ⟨a1,b1,c1⟩ …⟨an,bn,cn⟩ długości n reprezentuje dodawanie, jeśli liczba reprezentowana binarnie przez słowo c1…cn jest sumą liczb reprezentowanych przez a1…an i b1…bn. Na przykład, ciąg ⟨0,0,1⟩⟨1,1,1⟩⟨0,1,0⟩⟨1,1,0⟩ reprezentuje dodawanie (5+7=12). Podać wyrażenie regularne opisujące zbiór wszystkich słów nad alfabetem {0,1}3 reprezentujących dodawanie w powyższym sensie.
  5. Podzielność.

    1. Skonstruować skończony automat deterministyczny nad alfabetem {0,1,…,8,9} rozpoznający zbiór dziesiętnych reprezentacji wielokrotności liczby 7.
    2. Jak wyżej, ale przy reprezentacji odwrotnej, tj. poczynając od cyfr najmniej znaczących.
    3. Uogólnić niniejsze zadanie.
  6. Alfabet jednoliterowy. Dowieść, że język L⊆{a}∗ jest regularny wtedy i tylko wtedy, gdy zbiór liczb naturalnych {n:an∈L} jest semi–liniowy w sensie rozdziału. Dowieść, że dla dowolnego zbioru
    X⊆{a}∗, język X∗ jest regularny.
  7. Zbiory semi–liniowe (por. zadanie z rozdziału ).

    1. Dowieść, że dla dowolnego języka regularnego L zbiór {|w|:w∈L} jest semi–liniowy.
      W szczególności, języki regularne nad jednoliterowym alfabetem mogą być utożsamiane ze zbiorami semi–liniowymi poprzez bijekcję w↦|w|.
    2. Dowieść, że jeśli M⊆N jest zbiorem semi–liniowym, to język {bin(m): m∈M} jest regularny, gdzie bin(m) oznacza binarną reprezentację liczby m.

    Uwaga. Fakt analogiczny do ?? można udowodnić dla dowolnej reprezentacji, a zatem zbiór semi–liniowy jest regularny w reprezentacji o podstawie k, dla k≥1. W przeciwnym kierunku wiadomo, że jeśli zbiór jest regularny w reprezentacjach o względnie pierwszych podstawach p i q, to jest semi–liniowy — jest to wniosek z głębokiego Twierdzenia Cobhama.

  8. Dowieść, że dla danych liczb a,b,p,r∈N, następujący język jest regularny
    L={bin(x)$bin(y):(a⋅x+b⋅y)≡r(modp)}