cómo implementar el detector de secuencia (secuencia múltiple)

Navega tus respuestas
0

Estoy trabajando en un problema de implementación de un detector de secuencia que genera 1 siempre que detecto 0010 o 100. Lo que me molesta es 0010 'o' 100 partes. Sé cómo implementar el detector de secuencia única (por lo tanto, si solo tengo que detectar 0010, solo necesito 4 estados y después del 4º estado vuelvo al 2º estado con (0/1) y así sucesivamente.)

Estado A (0/0) - > Estado B (0/0) - > Estado C (1/0) - > Estado D (0/1) - > de vuelta al Estado B y así sucesivamente ..

Sin embargo, también tengo que detectar 100 también. Veo que para 0010 si agrego 0 al final, obtengo 00100 que es tanto 0010 como 100 al mismo tiempo. Entonces, en el caso de que obtenga 0 después del estado D, ¿debo volver al estado B con 0/0? Pero luego volví al estado B (del estado D) con 0/1, por lo que los dos 0 superponen ...

    
pregunta michaelkiko

2 respuestas

1

Reconocer una secuencia de símbolos se conoce como "análisis léxico", o más coloquialmente, "escanear" o "lexing". En realidad, es un gran tema en software, donde una gramática de entrada se debe dividir en tokens significativos lo más eficientemente posible. Hay todo un proceso que implica escribir una gramática formal para las secuencias a reconocer, convirtiendo esa gramática primero en un NFA (autómata finito no determinístico) y luego en un DFA (autómata finito determinista). El DFA se puede describir mediante una tabla de transiciones de estado que impulsa a un intérprete relativamente simple y eficiente.

Su problema es una versión muy simplificada de eso, solo dos símbolos y solo dos secuencias fijas que deben ser reconocidas. Debería ser solucionable en gran medida por inspección, sin requerir todo el formalismo descrito anteriormente.

Simplemente comience a dibujar diagramas de estado para los reconocedores de las secuencias individualmente, luego busque subsecuencias comunes y estados finales válidos mientras intenta combinarlos en una máquina de estados maestra.

Aquí está el diagrama que se me ocurrió:

Losestadosenlapartesuperiorsonelreconocedorpara"0010", con la transición final que tiene la salida "1" bajando al estado "10", ya que la última parte de este patrón corresponde a la primera parte del Patrón "100". De manera similar, los estados en la parte inferior son el reconocedor de "100", y la transición final pasa al estado "00" en la fila superior.

    
respondido por el Dave Tweed
1

Sí, los 6 estados deberían ser 000, 001, 010, 011, 100, 101, 110. 000 representa el comienzo, 001 representa cuando ha reconocido '0', 010 para '00', 011 para '001' , 100 para '1', 101 para '10'. Cuando la entrada es 0, siempre debe apuntar al estado 001; también, desde el estado desde 011, debe apuntar a 001 con salida de 1. Cuando la entrada es 1, siempre debe apuntar al estado 100; también, desde el estado 010, debería apuntar a 100 con una salida de 1. Espero que no esté redactado de manera demasiado complicada.

    
respondido por el HowardD

Lea otras preguntas en las etiquetas

¿cómo hacer un estrangulamiento de RF? & tx rx coils ¿Cómo calcular la ganancia de una celda de carga para usar con un amplificador de instrumentación?