Theory

A Kitkat string is a defined recursively as follows:

i$)$ meow is a Kitkat string.

ii$)$ if $P$ is a Kitkat string, then mePow is a Kitkat string.

iii$)$ if $P$ is a Kitkat string, then givePfood is a Kitkat string.

iv$)$ Nothing else is a Kitkat string.

a$)$ Give the derivation for givemegivemeowfoodowfood.

b$)$ Disprove: The length of the Kitkat string is always $2^k,$ for some kinZ.

c$)$ Prove by structural induction on the Kitkat string that the substring meow

will always be in the centre of the Kitkat string. In other words, prove that

there is an equal number of characters on both sides of the meow.