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
