Automaty skończone i wyrażenia regularne

Dowieść, że dla dowolnych języków $L,M$, $(L^{*}M^{*})^{*}=(L\cup M)^{*}$.
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?
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.
Dodawanie. Rozważamy słowa nad alfabetem $\{ 0,1\}^{3}$. Powiemy, że słowo $\langle a_{1},b_{1},c_{1}\rangle$ …$\langle a_{n},b_{n},c_{n}\rangle$ długości $n$ reprezentuje dodawanie, jeśli liczba reprezentowana binarnie przez słowo $c_{1}\ldots c_{n}$ jest sumą liczb reprezentowanych przez $a_{1}\ldots a_{n}$ i $b_{1}\ldots b_{n}$. Na przykład, ciąg $\langle 0,0,1\rangle\langle 1,1,1\rangle\langle 0,1,0\rangle\langle 1,1,0\rangle$ 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.
Podzielność.
1. Skonstruować skończony automat deterministyczny nad alfabetem $\{ 0,1,\ldots,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.
Alfabet jednoliterowy. Dowieść, że język $L\subseteq\{ a\}^{*}$ jest regularny wtedy i tylko wtedy, gdy zbiór liczb naturalnych $\{ n:a^{n}\in L\}$ jest semi–liniowy w sensie rozdziału. Dowieść, że dla dowolnego zbioru
$X\subseteq\{ a\}^{*}$, język $X^{*}$ jest regularny.
Zbiory semi–liniowe (por. zadanie z rozdziału ).
1. Dowieść, że dla dowolnego języka regularnego $L$ zbiór $\{|w|:w\in 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\mapsto|w|$.
2. Dowieść, że jeśli $M\subseteq{\bf N}$ jest zbiorem semi–liniowym, to język $\{\mbox{bin}(m):$ $m\in M\}$ jest regularny, gdzie $\mbox{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\geq 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.
Dowieść, że dla danych liczb $a,b,p,r\in{\bf N}$, następujący język jest regularny
$L\,=\,\{\,\mbox{bin}(x)\,\$\,\mbox{bin}(y)\,:(a\cdot x+b\cdot y)\equiv r\;\;(\textrm{mod} p)\}$

Informatyka MIMUW

Automaty skończone i wyrażenia regularne