Refrescar para arriba en matemáticas discretas (expresiones regulares)

Question

Estoy tratando de refrescar a mí mismo en la matemática discreta( se me olvidó un montón). Sé que este es un trivial de preguntas y no vale la pena su tiempo. Pero me olvidé de cómo resolver problemas que involucran el lenguaje formal de la teoría.

Por ejemplo, digamos que estás tratando de

(a) escriba una expresión regular para el lenguaje de Una de las cadenas binarias cuya longitud es divisible por tres

(b) la lengua B de todas las cadenas binarias que no contienen dos días consecutivos de 1.

Dónde debo empezar? Editado para hacer la pregunta más clara.

Answer 1

Uno muy sencillo método de (a) es comenzar haciendo una lista de las $8$ cadenas binarias de longitud $3$. Cada cadena cuya longitud es un múltiplo de a $3$ debe estar formado por la concatenación de las cadenas. Voy a ilustrar con cadenas de longitud: cualquier cadena de caracteres de longitud se puede dividir en dos caracteres trozos, cada uno de los cuales debe ser $00,01,10$ o $11$, por lo que las cadenas binarias de longitud son descritos por la expresión regular $(00+01+10+11)^*$. (Usted puede utilizar algún otro símbolo de $+$ a indicar alternativas; las alternativas comunes son $\mid$, $\lor$, y $\cup$.)

Problema (b) es un poco más difícil. La condición dice que si una cadena contiene un $1$, $1$ debe ser el último símbolo en la cadena o ser seguido inmediatamente por una $0$. Ignorar por un momento el caso excepcional de un final $1$; si sólo se requiere que todos los $1$ ser seguida inmediatamente por una $0$, estamos permitiendo que precisamente esas cadenas que pueden ser construidos por la concatenación de $0$'s y $10$'s, es decir, las cadenas descrito por la expresión regular $(0+10)^*$. Nos gustaría tener todas esas cadenas, sino también todas las cadenas que constan de uno de esos seguido por un solo $1$; ¿cómo se puede modificar o ampliar la expresión regular para incluir el último tipo, así como el ex?