¿Es decidible si un lenguaje descrito por número de ocurrencias es regular?

Dadas dos palabras , , ¿es decidible si el lenguaje de las palabras que contienen el mismo número de y es regular? $w_1$ $w_2$ $L$ $w_1$ $w_2$

Primero algunas definiciones:
podrían hacerse más concisas, y las anotaciones podrían mejorarse si se van a usar en pruebas. Este es solo un primer borrador.

Dados dos palabras y , se dice que: $w_1$ $w_2$

siempre ocurrecon , anotado , iff $w_1$ $w_2$ $w_1\triangleleft w_2$
1. para cualquier cadena tal que con $s$ $s=xw_2y$ y hay otra descomposición . Nota: La condición de que e $\mid x\mid,\, \mid y\mid\ \geq \mid w_1\mid +\mid w_2\mid$ $|x|_0,|x|_1|,|y|_0,|y|_1| \geq 1$ $s=x'w_1y'$
  $x$ $y$ cada uno contiene al menos un 0 y un 1 es requerido por un caso patológico (encontrado por @sdcvvc): , e , y sus variantes simétricas. $w_1=1^i0$ $w_2=v1^{i+j}$ $y\in1^*$
2. hay una cadena con $s=xw_2y$ modo que haya como máximo una descomposición $\mid x\mid,\, \mid y\mid\ \geq \mid w_1\mid +\mid w_2\mid$ $s=x'w_1y'$
siempre coincidecon , anotado $w_1$ $w_2$ , si cada uno siempre ocurre con el otro, $w_1\triangleleft \triangleright\,w_2$
y ocurren independientemente, anotado $w_1$ $w_2$ , si ninguno de los dos ocurre siempre con el otro, $w_1\triangleright \triangleleft\,w_2$
siempre ocurre veces o másque , anotado , iff para cualquier cadena tal que con hayotras descomposiciones $w_1$ $m$ $w_2$ $w_1\triangleleft_m w_2$ $s$ $s=xw_2y$ $\mid x\mid,\ \mid y\mid|\ \geq \mid w_1\mid +\mid w_2\mid$ $m$ $s=x_iw_1y_i$ para tal que implica . $i\in[1,m]$ $i\neq j$ $x_i\neq x_j$

Estas definiciones se construyen de modo que podamos ignorar lo que sucede en los extremos de la cadena donde se supone que y ocurren. Los efectos de límite al final de la cadena deben analizarse por separado, pero representan un número finito de casos (en realidad creo que olvidé uno o dos de estos sub-casos de límite en mi primer análisis a continuación, pero en realidad no importa). Las definiciones son compatibles con la superposición de ocurrencias. $w_1$ $w_2$

Hay 4 casos principales a considerar (ignorando la simetría entre y ): $w_1$ $w_2$

Ambas palabras se unen necesariamente, excepto posiblemente en los extremos de la cadena. Esto se refiere solo a pares de la forma y , o y . Esto es fácilmente reconocido por unautómata finitoque solo comprueba si hay eventos solitarios en ambos extremos de la cadena que se reconocerán, para asegurarse de que haya un evento solitario en ambos extremos o en ninguno de los extremos. También existe el caso degenerado cuando : entonces el lenguaje L es obviamente regular. $w_1\triangleleft \triangleright\,w_2$
$1^i0$ $01^i$ $0^i1$ $10^i$ $w_1=w_2$
, pero no Una de las 2 palabras no puede aparecer sin la otra, pero lo contrario no es cierto (excepto posiblemente en los extremos de la cadena). Esto sucede cuando: $w_1\triangleleft w_2$ $w_2\triangleleft w_1$
- es una subcadena de : entonces un autómata finito puede simplemente verificar que no ocurra fuera de una instancia de . $w_1$ $w_2$ $w_1$ $w_2$
- y para alguna palabra , : luego una comprobación de autómata finita como en el caso anterior de que no ocurre separado de . Sin embargo, el autómata permite contar una instancia adicional de que permitirá la aceptación si $w_1=1^i0$ $w_2=v1^j$ $v\in\{0,1\}^*$ $v\neq01^i$ $w_1$ $w_2$ $w_1$ $w_2$ es un sufijo de la cadena. Hay otros tres casos simétricos (simetría 1-0 y simetría izquierda-derecha).
Una de las 2 palabras aparece dos veces en la otra. Eso puede ser reconocido por una automatización finita que verifica que la palabra más pequeña nunca aparece en la cadena. También es una variante un poco más compleja que combina las dos variaciones del caso 2. En este caso, el autómata verifica que la cadena más pequeña nunca ocurra, excepto posiblemente como parte de en la más grande viene como sufijo de la cadena (y otros 3 casos por simetría). $w_1\triangleleft_2 w_2$
$1^i0$ $v$ $v1^j$
Las 2 palabras pueden aparecer independientemente una de la otra. Construimos una máquina secuencial-generalizada (GSM) que la producción de cuando se reconoce una aparición de y al reconocer una aparición de , y se olvida de todo lo demás. El idioma es regular solo si el idioma es regular. Pero $w_1\triangleright \triangleleft\,w_2$
$G$ $a$ $w_1$ $b$ $w_2$ $L$ $G(L)$ que está claramente libre de contexto y no es regular. Por lo tanto, no es regular. En realidad tenemos . Dado que los lenguajes regulares y los lenguajes libres de contexto están cerrados bajo mapeo gsm y mapeo gsm inverso, también sabemos que está libre de contexto. $G(L)=\{w\in\{a,b\}^*\mid\ \mid w\mid_a=\mid w\mid_b\}$ $L$
$L=G^{-1}(G(L))$ $L$

Una forma de organizar una prueba formal podría ser la siguiente. Primero construya un PDA que reconozca el lenguaje. En realidad, se puede hacer con una máquina de 1 contador, pero es más fácil tener dos símbolos de pila para evitar duplicar el control finito. Luego, para los casos en que debería ser un FA, demuestre que el contador puede estar limitado por una constante que depende solo de las dos palabras. Para los otros casos, demuestre que el contador puede alcanzar cualquier valor arbitrario. Por supuesto, el PDA debe organizarse de modo que las pruebas sean lo suficientemente fáciles de llevar.

Representar al FA como un PDA de 2 símbolos de pila es probablemente la representación más simple para él. En el caso no regular, la parte de control finito del PDA es la misma que la del GSM en el bosquejo de prueba anterior. En lugar de generar 's y ' s como el GSM, el PDA cuenta la diferencia en número con la pila. $a$ $b$

babou
fuente

Tenía una pregunta sobre la libertad de contexto en el caso de tres palabras. Lo eliminé cuando me di cuenta de que podía analizarse de manera similar. Primero pensé que probar que no era CFness sería un ejercicio original, pero el GSM lo arruina.

babou

No está claro qué quiere decir con "ocurrir independientemente el uno del otro", "unirse necesariamente", etc. En su lugar, escriba definiciones formales y demuestre que cubren todos los casos.

sdcvvc

No estoy seguro de lo que está preguntando, y qué nivel de formalización necesita, con qué propósito. Me di cuenta de que analizar a mano las posibles relaciones de las dos palabras no está garantizado para ser correcto, y de todos modos no importa. Lo que importa es si puede existir una ocurrencia de una palabra sin crear al mismo tiempo una ocurrencia (o varias) de la otra palabra. Los detalles no importan, ya que siempre estarán localizados y, por lo tanto, serán manejables de manera finita. Los dos extremos tampoco importan, ya que también están localizados. Incluso las superposiciones de sucesos no importan ya que solo pueden ser finitamente muchas en 1 lugar

babou

Le pregunté sobre definiciones precisas de los términos mencionados en el comentario. Gracias por escribirlos. ¿Se suponía que debía adivinarlos previamente? De todos modos, parece afirmar que

. Esto no satisface la condición 1. de la definición de "

siempre ocurre con

", ya que no hay aparición de

0^{i} 1 ◃ ▹ 1 0^{i}

$0^i 1 \triangleleft \triangleright 1 0^i$

w_{1}

$w_1$

w_{2}

$w_2$

1 0^{i}

$1 0^i$

s = 0^{M} 0^{i} 1 1^{M}

$s=0^M 0^i 1 1^M$

sdcvvc

Lo siento, no quise hacerte adivinar. Solo me llevó tiempo entender exactamente lo que querías. Solo mi falla. Con respecto a su contraejemplo, está en lo correcto. Pero para mí solo significa que tengo que tener un poco más de cuidado con los telómeros, en la definición de las relaciones. Los definí demasiado rápido, pero

no transmiten mucha información en este contexto. Este es realmente un ejemplo patológico límite dentro de un caso patológico, que en realidad no puede ocurrir cuando se usan más de 2 símbolos. Simplemente no creo que cambie nada.

0^{M}

$0^M$

1^{M}

$1^M$

babou

¿Es decidible si un lenguaje descrito por número de ocurrencias es regular?

Respuestas: