¿Expresión regular para cadena de dígitos sin dígitos repetidos?

Question

estoy leyendo a través de la dragon book y tratando de resolver un ejercicio que se expresan como sigue

Escribir las definiciones regulares para los siguientes idiomas:

• Todas las cadenas de dígitos sin dígitos repetidos. Sugerencia: Primero pruebe este problema con algunos dígitos, como {0, 1, 2}.

A pesar de haber intentado resolver durante horas, no puedo imaginar una solución, al lado de la muy prolijo

d0 -> 0? 
d1 -> 1? 
d2 -> 2? 
d3 -> 3? 
d4 -> 4? 
d5 -> 5? 
d6 -> 6? 
d7 -> 7? 
d8 -> 8? 
d9 -> 9? 
d10 -> d0d1d2d3d4d5d6d7d8d9 | d0d1d2d3d4d5d6d7d9d8 | ... 

lo tanto tener que escribir 10! alternativas en d10. Dado que vamos a escribir esta definición regular, dudo que esta es una solución adecuada. ¿Puedes ayudarme por favor?

Answer 1

Así que la pregunta no necesariamente pedirle que escriba una expresión regular , le pedirá que proporcione una definición regulares, que interpreto incluir NFA de. Resulta que no importa cuál sea tu uso, ya que se puede demostrar que todas las NFA son matemáticamente equivalentes a las expresiones regulares.

Uso de los dígitos 0, 1, y 2, un NFA válido sería el siguiente (lo siento por el diagrama de mala muerte):

Cada estado representa el último dígito escaneada en la entrada, y no hay bucles en ninguno de los nodos, por lo tanto, esta es una representación precisa de una cadena sin dígitos repetidos del conjunto {0,1,2}. Extender esto es trivial (aunque requiere una pizarra grande :)).

NOTA: Estoy suponiendo que la cadena "0102" ES válida, pero la cadena "0012" no.

Esto se puede convertir a una expresión regular (aunque será doloroso) utilizando el algoritmo descrito here.

Answer 2

(no sé qué variante de expresiones regulares que usted se refiere, en su caso, por lo tanto voy a dar consejos para la forma más general de las expresiones regulares.)

Me parece una aplicación bastante extraño de expresiones regulares ya que este es exactamente uno de los casos en los que realmente no proporcionan un gran beneficio sobre otras soluciones (más triviales de entender).

Sin embargo, si a pesar de todo desea utilizar expresiones regulares, aquí va una pista (sin solución ya que es un ejercicio, que me haga saber si necesita más pistas):

expresiones regulares le permite reconocer regular languages, que son generalmente aceptado por deterministic finite state machines. Intenta encontrar una máquina de estado que acepte exactamente las palabras en el patrón especificado. Exigirá 2^10 = 1024 estados pero no 10! = 3628800.

Answer 3

Recuerdo de mi curso de informática teórica: Si un idioma L es regular, también lo es (no L), es decir, el idioma que contiene todas las palabras que no están en L. - ¿Esto encaja en el contexto del ¿ejercicio?

Answer 4

En lugar de tratar de escribir una definición que sólo define lo que quiere, lo que si le dice que para generar una lista de todos cuerdas encima de dígitos hasta 10 dígitos de longitud, incluyendo los duplicados, y luego restar la unos que contienen dos ceros, dos unos ... etc.? Funcionaría eso?

Answer 5

He aquí una posible construcción:

• una expresión regular para una cadena que contiene como máximo un solo dígito '0' se parece a (1-9) * (0 | épsilon) (1-9) * - por lo que cualquier número de 1 a 9 dígitos, seguido de cero o 1 '0 seguido de cualquier número de 1 a 9 dígitos.
• Ahora podemos avanzar notando que si hay un solo dígito '1', estará a la izquierda oa la derecha del dígito '0' (o el épsilon que representa el dígito cero faltante). Entonces, podemos construir una expresión regular teniendo estos dos casos or'ed (|) juntos.
• Ahora podemos profundizar más diciendo que si hay un solo dígito '2' puede estar a la derecha oa la izquierda del dígito en sus dos posibles ubicaciones relativas al dígito '0'.
• Así que estamos construyendo un árbol binario y el número de regex ORed es del orden de 2^10, que es el mismo orden en que el FSM acepta este idioma. Un FSM para aceptar el idioma debería tener (2^10 + 1) estados con cada estado n se puede ver como su representación binaria n0n1n2n3n4n5n6n7n8n9 que significa n0 = dígito visto '0', n1 = dígito visto '1'. y un dígito repetido que pasa al estado único que no acepta. El estado inicial es cero.

Si se le permite complementar, entonces una expresión regular que tiene más de un dígito '0' sería (0-9) * 0 (0-9) * 0 (0-9) *, repita para todos los dígitos, complemento.

Definitivamente puede ser mucho más compacto para la interpretación de Peter Taylors de no tener dos dígitos consecutivos iguales. Claramente, el estado para ese problema es mucho más pequeño.

SUCCINCTNESS OF THE COMPLEMENT AND INTERSECTION OF REGULAR EXPRESSIONS

"Un estudio en [2] revela que la mayoría de la sola inequívoca expresión regular se utiliza en la práctica adoptar una forma muy simple:. Cada símbolo del alfabeto se produce como máximo una vez que se refieren a como expresiones únicas de ocurrencia simple (SOREs) y muestran un límite inferior exponencial apretado para la intersección. "

...

"En esta sección, se muestra que en la definición del complemento de una sola expresión regular, un aumento exponencial de doble tamaño no puede ser evitada en general. Por el contrario, cuando la expresión es one-inequívocamente su complemento se puede calcular en tiempo polinomial ".

Answer 6

No estoy seguro de lo que quiere decir con "Regular Expression" en el título de su pregunta. Pero si el motor de expresiones regulares admite un seguimiento negativo, esto se logra fácilmente. (He aquí un fragmento de PHP)

$re = '/# Match string of digits having no repeated digits. 
    ^    # Anchor to start of string. 
    (?![^0]*0[^0]*0) # Assert 0 does not occur twice. 
    (?![^1]*1[^1]*1) # Assert 1 does not occur twice. 
    (?![^2]*2[^2]*2) # Assert 2 does not occur twice. 
    (?![^3]*3[^3]*3) # Assert 3 does not occur twice. 
    (?![^4]*4[^4]*4) # Assert 4 does not occur twice. 
    (?![^5]*5[^5]*5) # Assert 5 does not occur twice. 
    (?![^6]*6[^6]*6) # Assert 6 does not occur twice. 
    (?![^7]*7[^7]*7) # Assert 7 does not occur twice. 
    (?![^8]*8[^8]*8) # Assert 8 does not occur twice. 
    (?![^9]*9[^9]*9) # Assert 9 does not occur twice. 
    [0-9]+   # Match string of only digits. 
    $     # Anchor to end of string. 
    /x'; 

Answer 7

Una definición regular es una secuencia de definiciones en el formulario

d1 -> R1

d2 -> R2

...

dn -> rn

Ahora haga las siguientes definiciones:

Zero -> 0

One -> Zero (1 Zero) * | (Cero 1) + | 1 (cero 1) * | (1 Cero) +

Dos -> Uno (2 Uno) * | (Uno 2) + | 2 (Uno 2) * | (2 Uno) +

Tres -> Dos (3 Dos) * | (Dos 3) + | 3 (dos 3) * | (3 Dos) +

Cuatro -> Tres (4 Tres) * | (Tres 4) + | 4 (Tres 4) * | (4 Tres) +

...

Nueve -> Ocho (9 Ocho) * | (Ocho 9) + | 9 (Ocho 9) * | (9 Ocho) +

Answer 8

No creo que hay una clara forma de escribir una expresión regular para resolver este problema sin enumerar todas las posibilidades. Pero encuentro una manera de reducir la complejidad de O (N!) A O (2^N) definiendo el DFA de la siguiente manera. En el DFA que voy a construir, un estado representa si ha aparecido o no un dígito.

cadenas Tomar consistentes en {0, 1, 2}, por ejemplo, representan 0 '0' se presentó una vez, 0' representan '0' no ha aparecido. Todos los estados se verán así {012, 0'1'2 ', 0'12, 01'2, 012', 012 ', 01'2, 0'12}. Habrá 2^3 = 8 estados en absoluto. Y el aspecto de DFA es el siguiente: DFA for strings with no repeating digits

Puede ampliarlo fácilmente a {0,1,2, ..., 9}. Pero habrá 1024 estados en absoluto. Sin embargo, creo que es el DFA más compacto con una prueba intuitiva. Por la razón de que cada estado tiene un significado único y no puede fusionarse más.