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

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

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

  3. 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?

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

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

  6. Podać przykład nieskończonego języka zamkniętego na branie podsłów, który nie zawiera nieskończonego języka regularnego.
  7. 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\}\)
  8. 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}}\)

  9. Dowieść, że dla dowolnego języka regularnego \(L\), regularny jest również język

    \(\{ w\,:\, w^{{|w|}}\in L\}.\)

  10. 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\}\)

  11. 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?

  12. 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.
  13. 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)\}\)
  14. 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.

  15. 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}}\) ?
  16. Podać przykład języka nieregularnego \(L\), takiego że \(L^{2}\) jest językiem regularnym.
  17. 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\ \}\)

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

  19. 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.
  20. 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.
  21. 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 ?
  22. 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.

  23. 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 ?
  24. Czy istnaieje automat deterministyczny wielomianowego rozmiaru dla nieskończoengo języka \(\{ 1,2..n\}^{*}-Per_{n}\) ?
  25. 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\)).
  26. 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\).
  27. 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.
  28. 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.
  29. Jako wniosek z dwu poprzednich zadań podaj efektywny algorytm sprawdzający czy język regularny jest palindromiczny.