Własności domknięcia języków regularnych

Dowieść, że dla języka regularnego $L\subseteq\Sigma^{*}$ i dowolnego zbioru $X\subseteq\Sigma^{*}$ języki

$\displaystyle X^{{-1}}L = \{ w:\,(\exists v\in X)\, vw\in L\}$

$\displaystyle LX^{{-1}} = \{ w:\,(\exists u\in X)\, wu\in L\}$
są regularne.
Dowieść, że język $L$ jest regularny wtedy i tylko wtedy, gdy język $L^{R}$ słów stanowiących lustrzane odbicia słów z $L$ jest regularny.
Uwaga. Lustrzane odbicie $w^{R}$ słowa $w$ możemy w ścisły sposób zdefiniować rekurencyjnie: $\epsilon^{R}=\epsilon$ i $(w\sigma)^{R}=\sigma w^{R}$ , dla $w\in\Sigma^{*}$ , $\sigma\in\Sigma$ .
Dla danego automatu $A$ rozpoznającego język $L$ , skonstruować automat rozpoznający język
$\mbox{Cycle}(L)=\{ vu\,:\, uv\in L\}$

Czy z faktu, że język $\mbox{ Cycle}(L)=\{ vu\,:\, uv\in L\}$ jest regularny, można wnioskować, że język $L$ jest regularny?
Niech $L$ bedzie językiem regularnym nad alfabetem $\{ 0,1\}$ . Dowieść, że następujący język jest regularny:
$\{ w\,:\, w\in L\wedge\mbox{ spośróod słów o dlugości $|w|$, $w$ jest najmniejsze w porządku leksykograficznym}\}$ $|w|$ , $w$ jest najmniejsze w porządku leksykograficznym
Przyjmujemy, że każde niepuste słowo binarne $w\in\{ 0,1\}^{*}$ , $w=w_{1}\ldots w_{k}$ , reprezentuje pewien ułamek w przedziale $[0,1)$ ,
$\mbox{bin}(w)=w_{1}\frac{1}{2}+w_{2}\frac{1}{2^{{2}}}+\ldots+w_{k}\frac{1}{2^{{k}}}$

Dla liczby rzeczywistej $r\in[0,1]$ , niech

$L_{r}=\{ w\,:\,\mbox{bin}(w)\leq r\}$

Dowieść, że język $L_{r}$ jest regularny wtedy i tylko wtedy, gdy liczba $r$ jest wymierna.
Podać przykład nieskończonego języka zamkniętego na branie podsłów, który nie zawiera nieskończonego języka regularnego.
Niech L będzie językiem regularnym. Dowieść, że następujące języki są również regularne:
1. $\frac{1}{2}L=_{{df}}\{ w\,:\,(\exists u)\,|u|=|w|\wedge wu\in L\}$
2. $\sqrt{L}=_{{df}}\{ w\,:\, ww\in L\}$
Niech L będzie językiem regularnym. Dowieść, że następujące języki są również regularne:
1. $\mbox{Root}(L)=\{ w\,:\,(\exists n\in N)\, w^{n}\in L\}$
2. $\mbox{Sqrt}(L)=\{ w\,:\,(\exists u)|u|=|w|^{2}\wedge wu\in L\}$
  Wskazówka. $n^{2}=1+3+\ldots(2n-1)$ .
3. $\mbox{Log}(L)=\{ w\,:\,(\exists u)|u|=2^{{|w|}}\wedge wu\in L\}$
  Wskazówka. $2^{n}=1+2+2^{2}+2^{{n-1}}+1$ .
4. $\mbox{Fibb}(L)=\{ w\,:\,(\exists u)|u|=F_{{|w|}}\wedge wu\in L\}$
  gdzie $F_{n}$ jest $n$ -tą liczbą Fibonacciego tzn.
  
  $F_{1}=F_{2}=1$
  
  $F_{{n+2}}=F_{n}+F_{{n+1}}$
Dowieść, że dla dowolnego języka regularnego $L$ , regularny jest również język

$\{ w\,:\, w^{{|w|}}\in L\}.$
Niech będzie dany język regularny $L$ i dowolne, niekoniecznie regularne, języki $L_{1}$ , …, $L_{m}$ . Skonstruować skończony automat deterministyczny rozpoznający język nad alfabetem $\{ 1,\ldots,m\}$
$L\,=\,\{ i_{1}i_{2}\ldots i_{k}:L_{{i_{1}}}L_{{i_{2}}}\ldots L_{{i_{k}}}\subseteq L\}$
Nietrywialnym palindromem nazwiemy każdy palindrom o długości co najmniej 2. Niech $\mbox{Pal\,}^{{>1}}_{{\Sigma}}$ oznacza zbiór nietrywialnych palindromów nad alfabetem $\Sigma$ . Dowieść, że język $(\mbox{Pal\,}^{{>1}}_{{\Sigma}})^{*}$ jest regularny wtedy i tylko wtedy, gdy $|\Sigma|=1$ .
Czy język $(\{ ww^{R}:w\in(0+1)^{*}\})^{*}$ jest regularny?
Które z następujących języków nad alfabetem {0,1} są regularne?
1. Zbiór słów posiadających nietrywialny palindrom jako prefiks.
2. Zbiór słów posiadających palindrom długości parzystej jako prefiks.
3. Zbiór słów posiadających nietrywialny palindrom długości nieparzystej jako prefiks.
Oznaczmy przez $\mathit{Ile}(w,x)$ liczbę wystąpień słowa $w$ jako podsłowo $x$ (wystąpienia nie muszą być rozłączne). Czy następujący język nad alfabetem $\{ a,b\}$ jest regularny? Jeśli tak, to podać wyrażenie regularne. Jeśli nie, to udowodnić, że nie jest.
1. $L_{1}=\{ x\ :\ \mathit{Ile}(ab,x)=\mathit{Ile}(ba,x)+1\}$
2. $L_{2}=\{ x\ :\ \mathit{Ile}(aba,x)=\mathit{Ile}(bab,x)\}$
Niech L będzie językiem regularnym. Dowieść, że języki:
1. $L_{{+--}}=\{ w\,:\,(\exists u)\,|u|=2|w|\wedge wu\in L\}$
2. $L_{{++-}}=\{ w\,:(\exists u)\, 2|u|=|w|\wedge wu\in L\}$
3. $L_{{-+-}}=\{ w\,:(\exists u,v)\,|u|=|v|=|w|\wedge uwv\in L\}$
są językami regularnymi, a język
1. $L_{{+-+}}=\{ uv\,:(\exists w)\,|u|=|v|=|w|\wedge uwv\in L\}$
może nie być regularny.
Czy zachodzi fakt: jeśli $L$ jest regularny to istnieja dwa niepuste słowa $u,v$ takie, że zachodzi równość ilorazów $L\{ uv\}^{{-1}}=L\{ vu\}^{{-1}}$ ?
Podać przykład języka nieregularnego $L$ , takiego że $L^{2}$ jest językiem regularnym.
Dla słów $u,v$ o tej samej długości, określamy odległość Hamminga
$d(u,w)=|\{ i:w_{i}\neq v_{i}\}|.$

Udowodnić, że dla dowolnego języka regularnego $L$ i stałej $K$ , następujący język jest również regularny:

$\{\ w\ :\ (\exists\ u\in L)\ |u|=|w|\ \textrm{oraz}\ d(u,w)\le K\ \}$
Przeplotem słów $w$ i $v$ nazwiemy dowolne słowo długości $|w|+|v|$ , które można rozbić na rozłączne podciągi $w$ i $v$ . Na przykład, przeplotami słów $ab$ i $acb$ są słowa $abacb$ , $aabcb$ , $acabb$ , $acbab$ , $aacbb$ . Przeplotem języków $L$ i $M$ jest zbiór wszystkich możliwych przeplotów słów $w\in L$ , $v\in M$ . Język ten oznaczamy $L\parallel M$ .

Dowieść, że jeśli $L$ i $M$ są językami regularnymi, to $L\parallel M$ jest również regularny.
Określamy $L^{{\sharp}}=L\,\cup\,(L\parallel L)\,\cup\,(L\parallel L\parallel L)\,\cup\ldots$ . Podać przykład języka regularnego $L$ nad dwuelementowym alfabetem, dla którego $L^{{\sharp}}$ nie jest językiem regularnym.
Niech $L_{1}\subset L_{2}$ reularne języki, gdzue $L_{2}-L_{1}$ jest nieskończony. Pokazać, że istenieje język regularny $L$ , t.że $L_{1}\subset L\subset L_{2}$ , oraz $L_{2}-L$ , $L-L_{1}$ są nieskończone.
Definiujemy operację, która dla słowa $xyz$ generuje słowo $xyyz$ . Niech $L$ będzie najmniejszym zbiorem zawierającym słowo $abc$ i domkniętym ze względu na wprowadzoną operację. Czy $L$ jest regularny ?
Dla wektora $\alpha\ =\ (i_{1},i_{2},\ldots i_{n})$ definiujmy słowo $w(\alpha)$ z języka $1^{*}2^{*}..n^{*}$ które zawiera dokładnie $i_{k}$ liter $k$ . Niech $X_{n}$ będzie zbiorem ciągów $(i_{1},i_{2},\ldots i_{n})$ o współrzędnych z przedziału $[1..n-2]$ , takich że $i_{n}=i_{k},\ k=i_{{n-1}}$ .
Udowodnić, że skończony język $L_{n}\ =\ \{ w(\alpha)\ :\ \alpha\in X_{n}\}$ jest akceptowany przez dwukierunkowy det. automat skończony mający $O(n)$ stanów, ale jednokierunkowy automat deterministyczny musi mieć wykładniczą liczbę stanów.
Niech $Per_{n}$ będzie zbiorem wszystkich permutacji zbioru $\{ 1,2..n\}$ , permutacje traktujemy tu jako słowa nad alfabetem $\{ 1,2..n\}$ . Czy istnieje niedterministyczny automat skończony mający wielomianową liczbę stanów i akceptujący $Per_{n}$ , ile stanów musi mieć (co najmniej) deterministyczny automat ?
Czy istnaieje automat deterministyczny wielomianowego rozmiaru dla nieskończoengo języka $\{ 1,2..n\}^{*}-Per_{n}$ ?
Niech $w$ będzie słowem długości $n$ , udowodnij, że istnieje wyrażenie regularne rozmiaru $O(n)$ opisujące zbiór wszystkich prefisków $w$ (włącznie z $w$ ).
Niech $w$ będzie słowem długości $n$ , udowodnij, że istnieje wyrażenie regularne rozmiaru $O(n)$ opisujące zbiór $\Sigma^{*}-w$ .
Język jest palindromiczny gdy wszystkie jego słowa są palindromami. Niech $A$ będzie niedet. automatem skończonym o $n$ stanach. Udowodnij, że $L(A)$ jest palindromiczny wtedy i tylko wtedy gdy język $w\in L(A)\ :\ |w|< 3n\}$ jest palindromiczny.
Udowdnij, że istnieje niedet. automat skończony rozmiaru $O(n)$ akceptujący tylko słowa niesymetryczne oraz dla słów $w$ długości mniejszej niż $n$ akceptuje $w$ wtedy i tylko wtedy gdy $w$ nie jest palindromem. Dla słów większej długości automat może nie akceptować pewnych słów niesymetrycznych.
Jako wniosek z dwu poprzednich zadań podaj efektywny algorytm sprawdzający czy język regularny jest palindromiczny.

Informatyka MIMUW

Własności domknięcia języków regularnych