3
Here is an alternative argument. Let $h$ be the homomorphism given by $h(a) = \epsilon$, $h(b) = b$. Then
$$ h(L) = \{ b^{n^2} : n \geq 0 \}. $$
If $L$ were context-free, then $h(L)$ would be unary context-free, and so regular. But $h(L)$ is not eventually periodic.
You can also show that $h(L)$ is not context-free using the pumping lemma. The pumping lemma ...
3
This is not a context-free language, as an immediate consequence of Parikh's theorem.
In terms of pushdown automata, there is no way for a PDA to keep track of the number of $b$'s in the string in a way it can access repeatedly while reading (or popping) the $a$ part of the string. This is an essential feature of context-free languages; it is the same ...
2
As for closure under complementation -- consider the following hint: context-free languages are not closed under complementation.
Regarding concatenation, this is slightly more tricky, but non-context free languages are not closed under complementation.
There are many ways of finding counterexamples for the latter, one is the following "trick":
Let $L$ ...
2
It might be context sensitive as well...
example:-
let
L1= ${\{a^n b^n c^m | n>0, m>0\}}$
and
L2=${\{a^m b^n c^n | m>0, n>0\}}$
Here L1 and L2 are context free but L1-L2 will be
L1-L2 = ${\{a^n b^n c^m | n>0, m>0 \space \& \space n \neq m\}}$
which is NOT context free.
1
For your specific question, you are asking to generate a string in $\bar{L} \cap P$. Note that since $L$ is regular, so is $\bar{L}$; and note that $P$ is context-free. It is known that the intersection of a regular and context-free language is context-free. So, you're asking: given a context-free language, how do we generate a word in that language? ...
1
Your second method to arrive at $\phi$ is bogus - consider the case where $B$ is the empty language. Where you are confused here is you are looking at the difference between the sets of all regular languages and all context free languages, instead of the difference between the two concrete languages.
The correct answer is d. None (you can't say anything)
...
1
$L_1\circ L_2$ can certainly still be non-regular. For example, when $L_1$ contains exactly one word.
However, $L_1\circ L_2$ can be regular, too. Here is an example. Let $L_1=\{\epsilon,0\}$. Let $L_2$ be the complement of $\{ 0^n1^n \mid n \gt 0 \}$.
As the complement of a non-regular language, $L_2$ is not regular while $L_1\circ L_2$, the set of all ...
Only top voted, non community-wiki answers of a minimum length are eligible
