Bezkontekstowy czy nie? | Informatyka MIMUW

Udowodnić, że żaden nieskończony podzbiór języka $L\ =\ \{ a^{n}b^{n}c^{n}\ :\ n\ge 1\}$ nie jest językiem bezkontekstowym.
Udowodnić, że dopełnienie języka z poprzedniego zadania jest językiem bezkontekstowym.
Udowodnić, że jeśli alfabet $\Sigma$ ma co najmniej dwie litery, to język $L=\{ ww:w\in\Sigma^{*}\}$ nie jest bezkontekstowy, natomiast jego dopełnienie $\Sigma^{*}-L$ jest językiem bezkontekstowym.
Dowieść, że dla każdego ustalonego $k$ dopełnienie języka $\{ w^{k}:w\in\Sigma^{*}\}$ jest językiem bezkontekstowym.
Udowodnić, że język $L\ =\ \{ xcx\ :\ x\in(a+b)^{*}\ \}$ nie jest językiem bezkontekstowym.
Udowodnić, że dopełnienie języka z poprzedniego zadania jest językiem bezkontekstowym.
Niech Subwords\/(x) oznacza zbiór wszystkich podsłów słowa x, \em Subwords\/(L)=⋃x∈L\em Subwords\/(x).
1. Udowodnić, że dla języka bezkontekstowego $L$ , $\mbox{\em Subwords\/}(L)$ jest językiem bezkontekstowym.
2. Podać przykład języka bezkontekstowego nieregularnego $L$ , dla którego $\mbox{\em Subwords\/}(L)$ jest językiem regularnym.
3. Podać przykład języka bezkontekstowego $L$ , dla którego $\mbox{\em Subwords\/}(L)$ nie jest językiem regularnym.
Pokazać, że język dopasowywania wzorca $L\ =\ \{ xcy\ :\ x,y\in(a+b)^{*},\ y\in\mbox{\em Subwords\/}(x)\}$ nie jest bezkontekstowy. Czy dopelnienie tego języka jest bezkontekstowe ?
Pokazać, że język $L\ =\ \{ xcy^{R}\ :\ x,y\in(a+b)^{*},\ y\in\mbox{\em Subwords\/}(x)\}$ jest bezkontekstowy.
(*) Pokazać, że dopełnienie języka z poprzedniego zadania nie jest językiem bezkontekstowym.
Rozstrzygnać, czy następujący język jest bezkontekstowy:

$L\ =\ \{ u\$ w^{R}\ :\ u,w\in\{ a,b\}^{+},\ w\textrm{ jest prefiksem i sufiksem }u\ \}$

To samo pytanie dla dopełnienia tego jezyka.
Udowodnić, że język $L\ =\ \{ a^{i}b^{j}c^{k}\ :i\ne j,\ i\ne k,\ j\ne k\ \}$ nie jest bezkontekstowy.

Czy jego dopełnienie jest bezkontekstowe ?
Czy język $L\ =\ \{ a^{i}b^{j}a^{i}b^{j}\ :i,j\ge 1\ \}$ jest bezkontekstowy ?
Czy jego dopełnienie jest językiem bezkontekstowym ?
Udowodnić, że język $L\ =\ \{ ww^{R}w:w\in(a+b)^{*}\}$ nie jest bezkontekstowy.

Czy jego dopełnienie jest bezkontekstowe ?
Pokaż, że język $\{ x\# y^{R}\ :\ x,y\in\{ 0,1\}^{+},\ [x]_{2}+1=[y]_{2}\}$ jest bezkontekstowy.
Pokaż, że język $\{ x\# y\ :\ x,y\in\{ 0,1\}^{+},\ [x]_{2}+1=[y]_{2}\}$ nie jest bezkontekstowy.
Które z następujących języków są bezkontekstowe ?
1. $\{ a^{m}b^{n}:m< n< 2m\}$
2. $(a+b)^{*}-\{(a^{n}b^{n})^{n}:n\geq 1\}$
3. $\{ ww^{R}w:w\in(a+b)^{*}\}$
4. $\{ a^{x}ba^{y}ba^{z}:x+y=z\}$
5. $\{ a^{x}ba^{y}ba^{z}:x\cdot y=z\}$
Dowiedź, że następujące języki nie są bezkontekstowe:
1. $\{ a^{i}b^{j}a^{k}:j=\mbox{ max }\{ i,k\}\}$
2. $\{ a^{i}b^{i}c^{k}:k\neq i\}$ .
Czy jest bezkontekstowy język $\{ a^{i}b^{j}c^{p}d^{q}:\ i,j,p,q>0,\ i*j=p+q\ \}$ ?
Czy język

$\{\mbox{bin}(n)\,\$\,\mbox{bin}(n^{2})^{R}\,:\, n\in N\},$

gdzie $\mbox{bin}(n)\in\{ 0,1\}^{*}$ jest binarnym przedstawieniem liczby $n$ , jest bezkontekstowy?
Niech $[n]_{2}$ oznacza zapis binarny liczby naturalnej $n\ge 1$ , pierwszą cyfrą jest jedynka (najbardziej znacząca). Czy następujący język jest bezkontekstowy:

$\ L_{4}\ =\ \{\ [n]_{2}\;[2n]_{2}\ :\ n\ge 1\ \}$
1. Udowodnij, że zbiór tautologii nad ustalonym skończonym zbiorem zmiennych jest bezkontekstowy (stanowi to uogólnienie zadania (??) z sekcji ??).
2. Formuły nad przeliczalnym zbiorem zmiennych można przedstawić jako język nad skończonym alfabetem, przyjmując indeksowanie zmiennych. Dokładniej, przyjmijmy, że zbiór wszystkich formuł jest generowany przez gramatykę
  
  $\displaystyle F \to \mbox{\bf true}\,|\,\mbox{\bf false}\,|\, V\,|\,(F\vee F)\,|\,(F\wedge F)\,|\,(\neg F)$
  
  $\displaystyle V \to xI$
  
  $\displaystyle I \to 0\,|\, 1J$
  
  $\displaystyle J \to J0\,|\, J1\,|\,\epsilon$
  
  Np. $((x101\vee(\neg x0))\wedge(\neg(\mbox{\bf false}\vee x101)))$ jest formułą.
  
  Udowodnij, że zbiór wszystkich tautologii nie jest bezkontekstowy. Stwierdzenie to wynika łatwo z hipotezy P $\neq$ NP, ale należy je dowieść bez tej hipotezy..
Niech alfabetem będzie $\{ 0,1\}$ . Słowo Lyndona to słowo pierwotne (nie będące potęgą mniejszego słowa, por. rozdz. , zad. ), które jest leksykograficznie najmniesze spośród swoich przesunięć cyklicznych.

Czy zbiór słów Lyndona jest bezkontekstowy ?

Wskazówka: we”zmy $a^{{n+1}}ba^{n}ba^{n}$ i zastosujmy lemat Ogdena, ,,markując” środkową grupę $a^{n}$ .
Niech $PAL$ onacza zbiór palindromów. Czy zachodzi implikacja:

L bezkontekstowy $\Longrightarrow$ $L\cap PAL$ bezkontekstowy ?
Sformuluj $uvwxy$ -lemat o pompowaniu dla języków liniowych w którym $|uvxy|=O(1)$ .

Dowied”z, że język $\{ a^{i}b^{i}c^{j}d^{j}:i,j\in{\bf N}\}$ nie jest liniowy.
Dowied”z, że $L\ =\ \{ x\in(a+b)^{*},\# _{a}(x)=\# _{b}(x)\}$ nie jest liniowym językiem bezkontekstowym.
Udowodnij, że zbiór słów $w$ nad alfabetem $\{ a,b\}$ mających tę samą liczbę liter $a$ co $b$ nie jest liniowym językiem bezkontekstowym.
Który z następujących języków jest bezkontekstowy. W przypadku gdy język jest bezkontekstowy wypisać gramatykę bezkontekstową. W zadaniu $[x]_{2}$ oznacza binarny zapis liczby $x$ , oraz $w^{R}$ oznacza odwrócenie słowa $w$ .
1. $L_{1}\ =\ \{[x]_{2}\ \&\ [y]_{2}\ :\ 1\le x\le y\ \}$ .
2. $L_{2}\ =\ \{[x]_{2}\ \&\ [y]_{2}^{R}\ :\ 1\le x\le y\ \}$ .
Niech D1,D2 oznacza zbiór poprawnych ciągów nawiasowych jednego typu (okrągłe ) i dwóch typów nawiasów (okrągłe i kwadratowe), odpowiednio, włącznie ze słowem pustym. Czy następujące języki są bezkontekstowe
1. $\{\ u\# v^{R}\ :\ uv\in\mathbf{D_{1}}\ \}$ ,
2. $\{\ u\# v^{R}\ :\ uv\in\mathbf{D_{2}}\ \}$ ?
Niech $L$ będzie zbiorem słów w alfabecie trzyelementowym, które nie zawierają słowa postaci $xx$ , dla $x\ne\epsilon$ . Udowodnić, że $L$ nie jest bezkontekstowy.
Podać przykład języka bezkontekstowego nad alfabetem trzyelemnentowym, którego dopełnienie jest nieskończone i nie zawiera słów postaci $xx$ , dla $x\ne\epsilon$ .