Cómo diseñar un autómata de estado finito que reconozca los lenguajes como $1^n 0^n$

Question

La pregunta es la siguiente Diseñar un autómata de estado finito que acepte cadenas binarias con al menos dos $0$ s y como máximo dos $1$ s.

Puedo diseñar fácilmente un NFA que acepte al menos dos $0$ O como máximo dos.

Pregunta adicional, ¿cómo se escriben expresiones regulares para autómatas como estos?

No puedo conseguir este método para generar expresiones regulares.

EDIT: Aquí hay una foto de la solución. http://i.stack.imgur.com/CxLDU.jpg

EDIT 2: En la foto S5 tendrá un 0 a sí mismo y S8 es el estado de aceptación.

Answer 1

Utilice un autómata con los siguientes estados

• Han visto ningún 0 y ningún 1
• He visto un 0 y ningún 1
• Han visto al menos dos 0 y ningún 1
• No han visto ningún 0 y un 1
• Han visto un 0 y un 1
• Han visto al menos dos 0 y un 1
• No han visto ningún 0 y dos 1
• Han visto un 0 y dos 1
• Han visto al menos dos 0 y dos 1
• Han visto al menos tres 1

con las obvias transiciones y estados de aceptación entre estos.

Answer 2

La idea general de simular dos autómatas finitos que se ejecutan a la vez, aquí procesos de conteo independientes con

• $Q_1$ : $3$ estados para contar dígitos $0$ : contado $0$ , $1$ , $2$ o más dígitos
• $Q_2$ : $4$ estados para contar dígitos $1$ : contado $0$ , $1$ , $2$ , $3$ o más dígitos

es construir el producto estados $Q_1 \times Q_2$ y el autómata del producto, como lo demuestra la solución de Hagen.