2

Suppose $$\ell=\{(abc)^p\mid p\text{ is prime}\}$$ According to Parikh's theorem, both $\ell$ and its complement $\ell^c$ aren't Context-free.


1

Let $L = \{a^n b^n c^n \mid n \ge 0\}$. Define $L' = \{aw \mid w \in L \} \cup \{ bw \mid w \in \overline{L}\} \cup \{\varepsilon\}$. Notice that $L'$ is not context free by an application of the pumping lemma on $a^{p+1}b^pc^p$ for sufficiently large $p$. The complement of $L'$ is $$ \overline{L}' = \{xw \mid x\in \{b,c\} \mbox{ or } w\not\in L \} \cap \{...


1

Your problem is finding a CFG grammar $G$ for the language $L$ that contains equal number of $a's$ and $b's$ with extra number of $a's$ . $$L=\{\omega\in \Sigma^*\mid n_a(\omega)>n_b(\omega)\}$$ Let $A$ is a variable that derive only $a's$. Let $E$ is a variable that derive equal number of $a's$ and $b's$. Let $S$ be start symbol. As a result we have the ...


1

If $n \neq 2m$ then either $n < 2m$ or $n > 2m$. A grammar for the former case is: $$ S_1 \to XY \mid aXY \mid Y \mid aY\\ X \to aaXb \mid aab \\ Y \to bY \mid b; $$ where $X$ generates all words of the form $a^{2k} b^k$ for some positive $k$. A grammar for the latter case is: $$ S_2 \to ZX \mid Z\\ X \to aaXb \mid aab \\ Z \to aZ \mid a; $$ A ...


1

There is no discrepancy in the two methods. The first method shows that $L := \overline{\overline{L_1} \cup \overline{L_2}}$ is context-sensitive. The second method shows the stronger result that $L$ is context-free. Both of these are consistent. Compare the following: $$ 1 + 1 \leq 1 + 2 = 3 \Longrightarrow 1 \leq 3 \\ 1 + 1 \leq 2 $$ The first inequality ...


Only top voted, non community-wiki answers of a minimum length are eligible