Własności języków bezkontekstowych

  1. Podaj przykład języka bezkontekstowego \(L\) t.że język \(L\ =\ \{ x\ :\ (\exists y)\,|x|=|y|\,\wedge\, xy\in L\}\) nie jest bezkontekstowy.
  2. Udowodnić, że przecięcie języka (deterministycznego) bezkontekstowego z regularnym jest też językiem (deterministycznym) bezkontekstowym.
  3. 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\). \(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\). Udowodnij, ze przeplot języka bezkontekstowego i regularnego jest językiem bezkontekstowym. Podaj przykład języków bezkontekstowych \(L\) i \(M\), dla których \(L\parallel M\) nie jest językiem bezkontekstowym.
  4. Domknięcie przeplotne języka \(L\) określamy przez \(L^{{\sharp}}=L\,\cup\,(L\parallel L)\,\cup\,(L\parallel L\parallel L)\,\cup\ldots\). Wykazać, że operacja domknięcia przeplotnego języka skończonego może dać w wyniku język który nie jest bezkontekstowy.
  5. Udowodnić, że jeśli \(X\), \(Y\) są językami regularnymi to język
    \(L\ =\ \sum _{{n\ge 1}}X^{n}\cap Y^{n}\)
    jest bezkontekstowy.
  6. Podać przykład języków regularnych \(X,\ Y\) t.że
    \(\sum _{{n\ge 1}}(X^{n}\cap Y^{n})\ =\ \{ w\in(a^{+}b^{+})^{+}:\# _{a}(w)=\# _{b}(w)\}\)
  7. Podaj języki regularne \(X,\ Y,Z\) t.że język
    \(\sum _{{n\ge 1}}(X^{n}\cap Y^{n}\cap Z^{n})\)
    nie jest bezkontekstowy.
  8. Wskaż język bezkontekstowy \(L\), dla którego \(\sqrt{L}=\{ w:ww\in L\}\) nie jest językiem bezkontekstowym.
  9. Podaj przykład języka bezkontekstowego takiego. że \(\{ x\ :\ x^{k}\in L\) dla pewnego \(k\}\) nie jest bezkontekstowy.
  10. Rozważmy następujący morfizm:

    \(h(a)=a,\ h(b)=b,\ h(a^{{\prime}})=a,\ h(b^{{\prime}})=b\)

    oraz \(h(x)=\epsilon\) dla symboli \(x\in\{ a,b,a^{{\prime}},b^{{\prime}}\}\) dla których morfizm nie został zdefiniowany powyżej. Wykazać, że język \(EQ(h,g)=\{ w:h(w)=g(w)\}\) nie jest bezkontekstowy.

  11. Udowodnij, że jeśli \(U\) jest regularny to następujący język jest bezkontekstowy
    \(\{ xy^{R}\ :\ x\ne y,\ xy\in U\}\)
  12. Język ma własność prefiksową, gdy dla każdych dwóch słow z tego języka jedno z nich jest prefiksem drugiego. Wykaż, że jeśli język bezkontekstowy ma własność prefiksową to jest on regularny.

  13. Niech \(L\subseteq\{ a,b\}^{*}\) będzie językiem regularnym oraz \(h,g\) będą morfizmami. Udowodnić, że następujący język jest liniowym językiem bezkontekstowym

    \(\{ h(u)c(g(u))^{R}\ :\ u\in L\}\)

  14. Udowodnij, że przecięcie liniowego języka bezkontekstowego z regularnym jest językiem liniowym.

  15. Dla języka \(L\) określamy \(\mbox{Min}(L)\) jako zbiór słów w \(L\) minimalnych ze względu na porządek bycia prefiksem. (Zatem \(u\in\mbox{Min}(L)\) \(\Leftrightarrow\) nie istnieją \(v\in L\) oraz \(w\neq\epsilon\) takie, że \(v w\in L\).) Udowodnij, że dla deterministycznego języka bezkontekstowego \(L\) język \(\mbox{Min}(L)\) jest również deterministycznym językiem bezkontekstowym.
  16. Niech \(L\ =\ \{ a^{i}b^{j}c^{k}\ :\ k\ge i\ lub\ k\ge j\}\). Pokaż, że \(Min(L)\) nie jest językiem bezkontekstowym.
  17. Zbiór \(\mbox{Max}(L)\) określamy analogicznie jak zbiór \(\mbox{Min}(L)\) w zadaniu ??. Podaj przykład języka bezkontekstowego \(L\), dla którego \(\mbox{Max}(L)\) nie jest językiem bezkontekstowym.

  18. Niech \(h_{1},h_{2}\) będą morfizmami takimi, że alfabet wyjściowy nie zawiera $. Wykaż, że języki \(\{ x\$ y^{R}\ :\ h_{1}(x)=h_{2}(x)\}\) i \(\{ x\$ y^{R}\ :\ h_{1}(x)\ne h_{2}(x)\}\) są liniowymi językami bezkontekstowymi.
  19. Podzbiór \(M\subseteq{\bf N}^{k}\) nazywamy liniowym jeśli można go przedstawić \(M=\{\vec{a}+n\cdot\vec{b}:n\in{\bf N}\}\), dla pewnych wektorów \(\vec{a},\vec{b}\in{\bf N}^{k}\), a semi-liniowym, jeśli jest sumą skończenie wielu zbiorów semi-lniowych.

    1. Udowodnij, że zbiór długości słów języka bezkontekstowego jest semi-liniowy.

    2. (*) Udowodnij twierdzenie Parikha głoszące, że dla języka bezkontekstowego \(L\subseteq\Sigma^{*}\) zbiór (\(\subseteq{\bf N}^{{|\Sigma|}}\)) wektorów liczby wystąpień liter z \(\Sigma\) w słowach z \(L\) jest semiliniowy.
  20. Przypomnijmy pojęcie odległości Hamminga, określonej dla słów tej samej długości (zadanie ??.??)

    \(d(u,w)=|\{ i:w_{i}\neq v_{i}\}|.\)

    Udowodnić, że dla języka regularnego \(L\), język

    \(\{\ w\ :\ (\exists\ u\in L)\ |u|=|w|\ \textrm{oraz}\ d(u,w)\le\frac{|u|}{2}\ \}\)

    jest bezkontekstowy. Czy język ten jest zawsze regularny ?

  21. Czy następujące stwierdzenia są prawdziwe:

    1. Istnieje nieskończony zbiór słów \(L\) nad skończonym alfabetem taki, że ani \(L\) ani dopełnienie \(L\) nie zawierają nieskończonego języka regularnego.
    2. To samo, ale wymagamy dodatkowo, aby \(L\) był bezkontekstowy.