Estoy trabajando en un problema (de Introducción a la Teoría de Autómatas, Lenguajes y computación por Hopcroft, Motwani y Ullman) escribir una expresión regular que define un lenguaje que consiste en todas las cadenas de 0s y 1s no contiene la subcadena 011.

Es la respuesta (0+1)* - 011 correcta ? Si no ¿cuál debería ser la respuesta correcta para esto?

Si usted está dando hasta después de una hora, le sugiero que pruebe más y hacer un poco de búsqueda.
No te estoy dando la respuesta, pero prueba esto: Sorteo de una máquina de estados finita (gráfico) que acepta 011 como una entrada y, a continuación, negarlo (la aceptación de todos los estados, ninguno de aceptar y ninguno de aceptar aceptar). Usted debe ser capaz de resolver la expresión regular a partir de allí, ya que también es una máquina de estados finitos.
Yo quería que el anterior.
Así mismo truco funciona para que así, Sorteo de una máquina de estados finitos (gráfico) que acepta cualquier cadena que contiene 011 …

OriginalEl autor Prasoon Saurav | 2010-04-17

2 Comentarios

  1. 9

    Expresión Regular para que coincida con la cadena de 0's y 1's sin '011' subcadena
    Edit: Actualizado para incluir iniciar los estados y correcciones, como por debajo de los comentarios.

    Como usted ha mencionado autómatas, he pensado que me gustaría sacar algunas, como están tan divertido! :). Ambos son deterministas de estado finito. Estaré encantado de responder a preguntas sobre su construcción si no están explicativo suficiente. (O corregir posibles errores). Espero que esto ayude!
    Usted no tiene ninguna flecha que indica el inicio de los estados! (-1 el maestro), Pero vamos a suponer que la izquierda vamos. El segundo es el derecho sobre el dinero, la primera es incorrecta. Si sólo aceptas exactamente 011, todas las flechas hacia la izquierda del estado debe ir hacia el righmost estado en el lugar, ya que en esos casos 011 nunca puede ser alcanzado.
    Sí, estás en lo correcto. He corregido la imagen. Habría rechazado (algunas) de las cuerdas, que finalizó en el 011.
    No creo que su primer gráfico es correcto, cuando llega al último estado, 011 será aceptado.
    tienes razón, esa es la máquina para «todos, excepto exactamente con la cadena 011». La pregunta original era claro que el OP que estaba buscando. La 2ª máquina se asemeja más a la pregunta como está parado.

    OriginalEl autor RJFalconer

  2. 4

    Si usted está buscando para todas las cadenas que no tienen 011 como una subcadena en lugar de simplemente excluyendo la cadena 011:

    Un clásico de la expresión regular que sería:

    1*(0+01)*

    Básicamente, usted puede tener muchos al principio como quieras, pero tan pronto como se golpeó un cero, es cero o cero que seguir (ya que de lo contrario obtendrá un cero-uno-uno).

    Un moderno, no es-en realidad-regular regex sería:

    ^((?!011)[01])*$

    Sin embargo, SI desea cualquier cadena que no es 011, usted puede simplemente enumerar cadena corta y comodín el resto:

    λ+0+1+00+01+10+11+(1+00+010)(0+1)*

    Y en las regex:

    ^(?!011)[01]*$
    λ+0+1+00+01+10+11+(1+00+010)(0+1)* ¿cómo llegar a este RE?
    La primera parte es una enumeración de todas las cadenas que son de menos de 3 caracteres. La segunda parte son las cadenas con las que 011 no se puede iniciar, seguido por datos arbitrarios.
    Su respuesta es incorrecta. 1*(0+01)* no acepta 10, ni se hace 101.

    OriginalEl autor Max Shawabkeh

Dejar respuesta

Please enter your comment!
Please enter your name here