Sipser 2.28 c. {w | the number of a's is at least the number of b's}

2.28 c. {w | the number of a's is at least the number of b's}

Solution:

S → aSbS | bSaS | aS | ε

aSbS | bSaS generates equal number of a and b. Then aS will help you to generate as many a you want. But it is ambiguous.

2.28 b. { w | the number of a's and b's in w are equal}

2.28 b. { w | the number of a's and b's in w are equal}

Solution:

S → aSbS | bSaS | ε

Don't ask me why? Work it out.

Sipser 2.28 a. { w | in every prefix of w the number of a's is at least the number of b's }

2.28 a. { w | in every prefix of w the number of a's is at least the number of b's }

Hint:
Replace a with open bracket ( and b with closing  bracket ). You will get the big picture that he is talking about set of prefixes of balanced paranthesis language.

Solution:
Finding ambiguity free context free grammer is not that trivial.
Very first step to find an unambiguous grammar is finding a grammar, unambiguous or ambiguous.
Secondly, If you see the ambiguity in it then explore it to know it deeper. And set a priority rules set which will tell you which of the parse tree (derivation) you have to pick. And now set production rules.

Initially what clicked me is:
S → SS | (S) | ε
but it is ambiguous. Think !!

After trying a day or a couple, I figured out the grammar should be
S → (S)S | ε

But this is not what we were looking for but grammar in which every string's prefix have more ( than number of  ).
S → (S)S | (S | ε

Please correct me if I am wrong.

Sipser 2.25: CFLs are closed under SUFFIX(A).

2.25 For any language (A), let SUFFIX(A) = { v | uv ∈ A for some string u }. Show that the class of CFLs is closed under the SUFFIX operation.

Hint: Add epsilon transitions to skip symbols.

Solution: For every state A, add a state A′. And new start  state will be S′. For every transition δ(A,0,a) → (B,b) add a transition δ(A′,ε,a) → (B′,b). And δ(A′,ε,ε) → (A,ε).

2.24 Sipser: Let E = { aibj i ≠ j and 2i ≠ j } Show that D is context-free language.

2.24 Let E = { aⁱb^j  | i ≠ j and 2i ≠ j } Show that D is context-free language.

solution:

Split it as unions of  3 languages.

{ aⁱb^j | i > j } ∪ { aⁱb^j | i < j and 2i > j } ∪ { aⁱb^j | 2i < j }

G¹ = { aⁱb^j | i > j }

G² = { aⁱb^j | i < j and 2i > j }

G³ = { aⁱb^j | 2i < j }

G¹ and G³ are quite easy to figure out.
for G¹

S →   aSb | aS¹
S¹ → aS¹ |ε

for G³

S → aSbb | S¹b
S¹ → S¹b | ε

Now tricky part is G2.

S → aSb | aS¹b
S¹ → aS¹bb | aS²bb
S² → ε

Very clearly, S will generate aⁿa^mb^2mbⁿ that is equivalent to a^n+mb^n+2m where m,n must be greater than 0.

Feel free to comment and correct me if I am wrong. :)

2.23 Let D = {xy | x,y ∈ {0,1}* |x| = |y| but x ≠ y} Show that D is context-free language.

2.23 Let D = {xy | x,y ∈ {0,1}^* |x| = |y| but x ≠ y} Show that D is context-free language.

Solution:

It is a bit tricky. 
Strategy is, x and will be first and second half respectively of a string w ∈ D. If we are able to show that after skipping some n position from start in x and y, we get different symbols, consider the problem done. 

<n symbols>0<m symbols>    <n symbols>1<m symbols>

or 

<n symbols>1<m symbols>    <n symbols>0<m symbols>

where m,n ∈ non negative intezers. 


Grammar : 

S →  AB | BA
A → 0A0 | 0A1 | 1A0 | 1A1 | 0
B → 0B0 | 0B1 | 1B0 | 1B1 | 1 

this grammar will generate strings of type 

<n symbols>0<n symbols> <m symbols>1<m symbols>

which is actually equivalent to 

<n symbols>0<m symbols>  <n symbols>1<m symbols>


Feel free to comment to clear doubt. :)

Sipser Second Edition 2.19

2.19
Let CFG G be
S → aSb | bY | Ya
Y → bY | aY | ε
Give a simple description of L(G) in English. Use that description to give a CFG for L(G)^c, the complement of L(G).

Solution.
I don't know the exact solution. Here I am discussing what I am thinking.
Clearly, Y generates all strings over a,b. So if we consider only last two rules for S those are bY| Ya, then they will generate all strings { w | w has length at least 1 and w either starts with a 'b' or ends with
a 'a' }. That means these two rule will not generate a string starting with a and ending with b. Now consider S → aSb. This rule generates string starting with a, ending with b and middle will not contain a string ba.
Hence L(G) have every string over a,b but not the strings of even length whose middle(center) have 'ab'. Like it will never generate <substring of length k>ab<substring of length k>.

So its complement will have all strings which look like <substring of length k>ab<substring of length k>.

S → aSb | bSa | aSa | bSb | ba



I expect it to be right, but in case I am not then please comment.

Sipser 2.2 b. CFLs are not closed under Intersection.

2.2 b. Use part (a) and DeMorgan's law to show that the class of CFLs is not closed under complementation.

Sol.

A = {a^mbⁿcⁿ | m,n ≥ 0}

B = {aⁿbⁿc^m | m,n ≥ 0}

A ∩ B = {aⁿbⁿcⁿ | n ≥ 0}
Clearly, A ∩ B is not CFL(pumping lemma). Demorgans' law :

(A ∩ B)^c = A^c ∪ B^c

A^c  = {a^mbⁱc^j | m, i, j ≥ 0 & i ≠ j} = {a^mbⁱc^j | m, i, j ≥ 0 & i > j} ∪ {a^mbⁱc^j | m, i, j ≥ 0 & i < j}

now prove that {a^mbⁱc^j | m, i, j ≥ 0 & i > j} is CFL.
{a^mbⁱc^j | m, i, j ≥ 0 & i  <  j} :
S → S₁S₂
S₁ → aS₁
S₂ → bS₂c | S₂c | c

Similarly {a^mbⁱc^j | m, i, j ≥ 0 & i < j} is CFL and so is A^c. Similar argument holds for B^c. So A^c ∪ B^c is also CFL(Union of CFL is CFL) . Hence proved complement of CFL is not closed.