Modified PCP problems

The following is a grammar that will generate all strings of the form anbn.

S → aSb | ε

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

Here are the "dominos" representing this grammar:

FS⇒
F
S
S
a
a
b
b
aSb
S
    
S
E
⇒aabbE

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 as and bs. 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.