Find a CFG for all the binary strings in which the characters in $i$ and $i + 2$ positions are same, and the length of the string is at least 2.

Question

I have homework which is about CFGs, their simplification, and their normalized forms. I have also seen some examples on the internet, but unfortunately, I could not solve the below question.

All the binary numbers, in which the $i$th character is equal to the character which is located in $i + 2$ th position, and the length of these strings is at least $2$.

My problem is with positions, and how to show them using our grammar. My idea was to have $S$ as our initial state, and then have a production like this:

$S\Rightarrow A|B$

And then $A$ be for all the strings which start by $0$, and $B$ be for all the strings which start by $1$. But I will be really grateful for your help.

Answer 1

We can divide this language into 4 groups, and then use a union between them. The first 2 bits can be 00, 01, 10, or 11. So we need 4 states besides the initial state.

$S \Rightarrow 00A|01B|10C|11D$

And then we add 4 productions:

$A \Rightarrow 0A|ɛ$

$B \Rightarrow 01B|0|ɛ$

$C \Rightarrow 10C|1|ɛ$

$D \Rightarrow 1D|ɛ$

Answer 2

These are strings like 01, 010, 0101, 01010, .. and 10, 101, ... .

Consider a grammar like S-> abS | ab, which produces even length strings of the form ab, abab, ababab, ... . Consider how you'd modify the grammar to (1) produce odd length strings, (2) start with b instead.

For example, S-> abA. A-> e|a|abA is a grammar that can produce odd length strings.