Im having trouble doing the following context free grammer questions, the book im using doesnt cover this in the same way so im having trouble just understanding the questions, let alone doing them.
Can anyone clarify the meanings and maybe hint to the working out also. I have attempted the first two but wasnt even really able to attempt the others.
any help would be much appreciated.
Your answer to the first part of the question is correct.
Your answer to the second seems to reflect some fundamental misunderstanding. $L(G(a^2))$ is the set of all words generated by the grammar $G(a^2)$, which has the two productions $S\to aSb$ and $S\to a^3b$. Every derivation must consist in applying the first of these productions some number of times and then applying the second one once: after each application of $S\to aSb$ we still have the non-terminal symbol $S$, so we need to apply another production, and after one application of $S\to a^3b$ we no longer have any non-terminal symbol. Suppose that we apply the first production $n$ times, where $n$ can be any non-negative integer; at that point we’ll have generated $a^nSb^n$. If we then apply the second production, the $S$ will be replaced by $a^3b$, and we’ll have $a^{n+3}b^{n+1}$. Every word of this form can be generated by $G(a^2)$, and these are the only words that can be so generated. Thus,
$$L(G(a^2))=\{a^{n+3}b^{n+1}:n\ge 0\}=\{a^{n+2}b^n:n\ge 1\}\;.$$
In words, the language consists of all words consisting of a string of $a$s followed by a string of $b$s, where there is at least one $b$, and the number of $a$s is $2$ more than the number of $b$s.
We can approach the third part of the question similarly. Whatever $w$ is, if we apply the production $S\to aSb$ $n$ times, we’ll have $a^nSb^n$, and if we then apply the production $S\to awb$, we’ll have $a^{n+1}wb^{n+1}$. Thus,
$$L(G(w))=\{a^{n+1}wb^{n+1}:n\ge 0\}\;.$$
We want to choose $w$ so that this is equal to $L=\{a^nb^{n+k}:n\ge 2\text{ and }k\ge 0\}$. However, this is impossible. Whatever $w$ is, it’s a single word, so it has a definite number of $a$s and a definite number of $b$s. Say that $w$ contains $n_a$ $a$s and $n_b$ $b$s. Then a word $a^{n+1}wb^{n+1}$ of $L(G(w))$ contains $n+1+n_a$ $a$s and $n+1+b_b$ $b$s, and the number of $b$s minus the number of $a$s is
$$(n+1+n_b)-(n+1+n_a)=n_b-n_a\;.$$
This is a constant: it’s the same for every word in the language $L(G(w))$. Now look at an arbitrary word $a^nb^{n+k}\in L$: the number of $b$s minus the number of $a$s is
$$(n+k)-n=k\;,$$
where $k$ can be any non-negative integer. If we choose $k\ne n_b-n_a$, $a^nb^{n+k}$ will be a word in the language $L$ that is not in $L(G(w))$, so $L(G(w))\ne L$. We can make this argument for any $w\in\Sigma^*$, so there is no $w$ such that $L(G(w))=L$.
Now see if you can use the same ideas to solve the fourth part. From what we just did, you know that whatever $w$ may be,
$$L(G(w))=\{a^{n+1}wb^{n+1}:n\ge 0\}\;.$$
For what values of $w$ will this set include the word $a^3b^3$?
as for the third question w can = $e, ab, a^2b^2$ I think ?
In regards to question 2 id just like to clear something up. I understand the steps that are taken clearly but I just wanted to clarify that you just have to replace the w with what is in the brackets (in this case $a^2$) ?
As for question 3 it is somewhat hard to get my head around but after reading it many times i think im getting there.
thanks again for your great responses.
– dmnte Jul 22 '15 at 02:031) $S \rightarrow aSb \rightarrow a^4b^2 $ where we apply the first production rule one time and conclude with the second one (with $w = a^2$)
2)I can't understand your solution. We are asked to find all the words of the language. So, again, starting with $S$ we can apply the first production rule any numer $n$ of times but we are always left with a non-terminal symbol, so the second rule must be applied one time (and only one!) to get a correct word. So the language generated is $a^{n+2}b^n$
3)Here I could be wrong, but it seems that you cannot have the given language for any terminal symbol $w$. If you take $w$ as a non-terminal and take as new production rule $ w \rightarrow Sb \vert \epsilon$ (where $\epsilon$ is the null-word), then it should work.
4) The only ways for $a^3b^3 \in L(G(w))$ are $w= \epsilon, ab,a^2b^2$
