Własności języków bezkontekstowych

Podaj przykład języka bezkontekstowego $L$ t.że język $L\ =\ \{ x\ :\ (\exists y)\,|x|=|y|\,\wedge\, xy\in L\}$ nie jest bezkontekstowy.
Udowodnić, że przecięcie języka (deterministycznego) bezkontekstowego z regularnym jest też językiem (deterministycznym) bezkontekstowym.
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.
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.
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.
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)\}$
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.
Wskaż język bezkontekstowy $L$ , dla którego $\sqrt{L}=\{ w:ww\in L\}$ nie jest językiem bezkontekstowym.
Podaj przykład języka bezkontekstowego takiego. że $\{ x\ :\ x^{k}\in L$ dla pewnego $k\}$ nie jest bezkontekstowy.
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.
Udowodnij, że jeśli $U$ jest regularny to następujący język jest bezkontekstowy
$\{ xy^{R}\ :\ x\ne y,\ xy\in U\}$
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.
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\}$
Udowodnij, że przecięcie liniowego języka bezkontekstowego z regularnym jest językiem liniowym.
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.
Niech $L\ =\ \{ a^{i}b^{j}c^{k}\ :\ k\ge i\ lub\ k\ge j\}$ . Pokaż, że $Min(L)$ nie jest językiem bezkontekstowym.
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.
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.
Podzbiór M⊆Nk nazywamy liniowym jeśli można go przedstawić M={→a+n⋅→b:n∈N}, dla pewnych wektorów →a,→b∈Nk, 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.
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 ?
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.

Informatyka MIMUW

Własności języków bezkontekstowych