# Tag Info

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.
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 ...