Give a recursive definition of a language L_bad that does not contain either three 0s or three 1s in a row.

Question

This assumes that ∑ = {0,1}

For example,

101101 ∈ L_bad

011110∉ L_bad

Answer 1

I think this will do it.

L_bad ⇐ 0 0? ( 1 L_bad )? | 1 1? ( 0 L_bad )? | ε

or with less symbolism:

L_bad ⇐ 0

⇐ 0 0

⇐ 0 0 1 L_bad

⇐ 1

⇐ 1 1

⇐ 1 1 0 L_bad

⇐ ε

For a non-symbolic description:

An L_bad is either:

1. One or two 0's, optionally followed by a 1 and an L_bad, or
2. One or two 1's, optionally followed by a 0 and an L_bad, or
3. the empty string.

-+- Sid