[Math] Freshening up on discrete math (regular expressions)

discrete mathematicsformal-languagesregular expressions

I'm trying to freshen myself up on discrete math( I forgot a lot). I know this is a trivial question and not worth your time. But I forgot how to solve problems involving formal language theory.

For example lets say you were trying to

(a) write a regular expression for the language A of binary strings whose length is divisible by three

(b) the language B of all binary strings that do not contain two consecutive 1's.

Where would I start? Edited to make question clearer.

Best Answer

One very straightforward approach to (a) is to begin by listing the $8$ binary strings of length $3$. Every string whose length is a multiple of $3$ must be formed by concatenating those strings. I’ll illustrate with strings of even length: any string of even length can be segmented into two-character chunks, each of which must be $00,01,10$, or $11$, so the binary strings of even length are described by the regular expression $(00+01+10+11)^*$. (You may use some other symbol than $+$ to indicate alternatives; common alternatives are $\mid$, $\lor$, and $\cup$.)

Problem (b) is a little harder. The condition says that if a string contains a $1$ at all, that $1$ must either be the last symbol in the string or be followed immediately by a $0$. Ignore for a moment the exceptional case of a final $1$; if we just require that every $1$ be followed immediately by a $0$, we’re allowing precisely those strings that can be built by concatenating $0$’s and $10$’s, i.e., the strings described by the regular expression $(0+10)^*$. We’d like to have all of those strings, but also all strings that consist of one of those followed by a single $1$; how can you modify or extend the regular expression to include the latter type as well as the former?

Related Question