\(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 jego dopełnienie jest bezkontekstowe ?
\(\{\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?
\(\ L_{4}\ =\ \{\ [n]_{2}\;[2n]_{2}\ :\ n\ge 1\ \}\)
\(\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..
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}\).
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.
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\).