Starting with the "string" $PI$, can I or not transform it into the "string" $PK$ by applying the following rules (each rule can be used any number of times, in any order, and $x$ and $y$ represents a part of a string)?
Rule 1. You can transform the string $xI$, into $xIK$. Example: $PI$ can be transformed into $PIK$.
Rule 2. You can transform the string $Px$ into $Pxx$. Example: $PIIK$ can be transformed into $PIIKIIK$.
Rule 3. You can transform the string $xIIIy$ into $xKy$. Example: $PKIIIK$ can be transformed into $PKKK$.
Rule 4. You can transform the string $xKKy$ into $xy$. Example: $PKKI$ can be transformed into $PI$.
So here's a valid sequence of transformations from $PI$ to $PIK$:
- $PI$ becomes $PII$ using Rule 2.
- $PII$ becomes $PIIII$ using Rule 2.
- $PIIII$ becomes $PIIIIK$ using Rule 1.
- $PIIIIK$ becomes $PIK$ using Rule 3.
HINT: Consider the number of $I$s in a word. Let $n_k$ be the number after $k$ steps, so that $n_0=1$. Rules $1$ and $4$ don’t affect the number of $I$s, so when they’re applied, we have $n_{k+1}=n_k$. Rule $2$ doubles the number, so when it’s applied we have $n_{k+1}=2n_k$. Finally, Rule $3$ reduces the number by $3$, so when it’s applied, we have $n_{k+1}=n_k-3$. Now look at $n_k\bmod 3$; can this ever be $0$?