Modified PCP problems

The following is a grammar that will generate all strings of the form a^{n}b^{n}.

`S → aSb | ε`

Here is a string belonging to the language generated by the above grammar:` aabb`

Here are the "dominos" representing this grammar:

Use MPCP to demonstrate that the string `aabb`

belongs to the language generated by the above grammar.

Write a context-free grammar to generate/recognize strings over the alphabet `{a, b}`

, where the string contains an equal number of `a`

s and `b`

s. Give an informal proof that your grammar is correct. Then use MPCP to show that the string `baaabb`

belongs to the language generated by the grammar.

Write a context-free grammar to generate/recognize all palindromes over the alphabet `{a, b}`

. Give an informal proof that your grammar is correct. Then use MPCP to show that the string `baaabb`

belongs to the language generated by the grammar.