Can You Define the Recursive Equation for Strings of 1s and 2s with 3 Mod 4 1s?

  • Topic:
  • Thread starter Thread starter Amad27
  • Start date Start date
  • Tags Tags
    String
Join the discussion
Registration is free. Start your own thread to ask a follow-up.
Sign up Log in
1 reply · 2K views
Amad27
Messages
409
Reaction score
1
If $K$ is the set of strings of 1s and 2s with the number of 1s $\equiv3\bmod4$ and with any amount of $2$s, find a recursive definition of $K$. For example, $1112112121$.

I'm in need of some hints.

The string can be empty, have no 1's or have 1's equivalent to 3 mod 4.
$$K=\{\varepsilon,2\}\cup\{2,111,x\}K$$
I'm unable to figure out how to have the number of 1s exactly $\equiv3\bmod4$.
 
Physics news on Phys.org

Discussion

Hi Olok,

The strings of the form 12*12*12* are in K, aren't they?
That is, the strings that begin with 1 and that have exactly three 1's.

If s is in K, then 2s is also in K.

If s is in K, then 12*12*12*1s is also in K.
That is, we can add a string with exactly four 1's.