-
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\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.
-
Udowodnij, że zbiór długości słów języka bezkontekstowego jest semi-liniowy.
-
(*) 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:
-
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.
-
To samo, ale wymagamy dodatkowo, aby \(L\) był bezkontekstowy.