Es el idioma

Es el idioma $L = \{0^n 1^m \mid n \text{ and } m \text{ are co-prime}\}$ sin contexto?

Supongo que no está libre de contexto porque parece demasiado complicado para que un PDA decida si 2 números son primos o no.

Traté de usar el lema de bombeo en vano.

Cualquier ayuda será agradecida.

Editar:

Aquí está uno de mis intentos fallidos con el lema de bombeo:

Dejar $N$ ser una constante Toma un primer $p$ tal que $p > N!$ y luego toma la palabra $z = 0^p 1^{p+N!} \in L$ . Dejar $z = uvwxy$ ser una descomposición de $z$ satisfaciendo las condiciones en el lema de bombeo.

Si $vx$ contiene solo ceros entonces $|vx| = k$ es un entero entre $1$ y $N$ . Definir $m$ como $m = N!/k$ . por $i = m+1$ la palabra $uv^iwx^iy = 0^{p+N!}1^{p+N!} \not\in L$

Sin embargo, no he podido encontrar tal número entero $i$ para los otros casos de descomposición.

formal-languages context-free pumping-lemma pushdown-automata Robert777
fuente

Bienvenido a la informática ! Permítame dirigirlo hacia nuestras preguntas de referencia que pueden cubrir su problema. Revise las preguntas relacionadas enumeradas allí, intente resolver su problema nuevamente y edite para incluir sus intentos junto con los problemas específicos que encontró. Creo que el teorema de Parikh podría funcionar para ti.

Raphael

Parikh debería funcionar, pero también bombeo estándar / Ogden, ¿verdad?

Ran G.

En realidad es una pregunta de prueba. Como no hemos aprendido el teorema de Parikh, probablemente haya una manera de demostrar que no está libre de contexto con el lema de bombeo o con las propiedades de cierre.

Robert777

@Raphael, en este caso el teorema de Parikh realmente no agrega nada más allá del lema de bombeo directo (es decir, de

0^{n} 1^{m}

$0^n 1^m$ puede obtener todo

0^{n + k a} 1^{m + k b}

$0^{n + k a} 1^{m + k b}$ para algunos

a

$a$ ,

b

$b$ no tanto cero como

k \geq - 1

$k \ge -1$ ) Pero no veo ninguna forma de forzar

gcd (n + k a, m + k b) \neq 1

$\gcd(n + k a, m + k b) \ne 1$ .

vonbrand

@vonbrand Podemos trabajar en

\bar{L} \cap L (0^{*} 1^{*})

$\overline{L} \cap \mathcal{L}(0^*1^*)$ en lugar; ver aquí .

Raphael

Respuestas:

Ridículo que no vi esto antes ...

La prueba de que el idioma (llámalo $\mathcal{L}$ ) no está libre de contexto es por contradicción. Asumir $\mathcal{L}$ no tiene contexto, por el lema de bombeo para CFGs hay una constante $N$ tal que cada cuerda $\sigma \in \mathcal{L}$ tal que $\lvert \sigma \rvert \ge N$ puede ser escrito $\sigma = u v x y z$ con $v y \ne \epsilon$ tal que para todos $k \ge 0$ la cuerda $u v^k x y^k z \in \mathcal{L}$ . Tomar $m, n$ diferentes números primos (de modo que $\gcd(m, n) = 1$ ) y $m, n > 2N$ , y tomar $\sigma = 0^m 1^n$ . La cadena bombeada será $0^{m + k a} 1^{n + k b}$ para algunas constantes $a$ , $b$ , no ambos cero, y tal que $a < m$ y $b < n$ (tenemos $a, b \le N < m / 2, n / 2$ por cierto $m$ , $n$ fueron seleccionados). El caso de uno de ellos cero fue cubierto por OP, así que considere $a, b \ne 0$ . Ahora:

\begin{aligned} m + k a & \equiv 0 (\mod n) \\ n + k b & \equiv 0 (\mod m) \end{aligned}

$\begin{align*} m + k a &\equiv 0 \pmod{n} \\ n + k b &\equiv 0 \pmod{m} \end{align*}$

Esto tiene una solución única. $k^*$ módulo $m n$ por el teorema del resto chino (tenemos $a < n$ , y como $n$ es primo $\gcd(a, n) = 1$ ; similar $b$ y $m$ ), y así podemos escribir:

\begin{aligned} m + k^{*} a & \equiv 0 (\mod m n) \\ n + k^{*} b & \equiv 0 (\mod m n) \end{aligned}

$\begin{align*} m + k^* a &\equiv 0 \pmod{mn} \\ n + k^* b &\equiv 0 \pmod{mn} \end{align*}$ es decir,

m n ∣ gcd (m + k^{*} a, n + k^{*} b)

$m n \mid \gcd(m + k^* a, n + k^* b)$ . Contradicción.

vonbrand
fuente

Gracias por su respuesta. Me gustó la forma en que abordaste esto. Sin embargo, no entiendo cómo usó el teorema del resto chino si esto solo se puede aplicar en un sistema de congruencias lineales de la forma:

\begin{aligned} x & \equiv b 1 (\mod m 1) \\ x & \equiv b 2 (\mod m 2) \end{aligned}

$\begin{align*} x &\equiv b1 \pmod{m1} \\ x &\equiv b2 \pmod{m2} \end{align*}$

Robert777

@ Robert777, solo escribe

k a \equiv - m (\mod n)

$k a \equiv -m \pmod{n}$ y así.

vonbrand

pero obtienes una congruencia de la forma:

\begin{aligned} a x & \equiv b (\mod m) \end{aligned}

$\begin{align*} a x &\equiv b \pmod{m} \\ \end{align*}$ Y no es lo mismo. Por ejemplo si

g c d (a, m) ⧸ | b

$gcd(a,m) \not | b$ entonces la congruencia no tiene soluciones.

Robert777

@ Robert777, tienes toda la razón. Cambiado para seleccionar

m

$m$ ,

n

$n$ principal. ¡Gracias!

vonbrand

Bien, después de haber usado el teorema del resto chino, ¿por qué podemos escribir estas congruencias?

\begin{aligned} m + k^{*} a & \equiv 0 (\mod m n) \\ n + k^{*} b & \equiv 0 (\mod m n) \end{aligned}

$\begin{align*} m + k^* a &\equiv 0 \pmod{mn} \\ n + k^* b &\equiv 0 \pmod{mn} \end{align*}$

Robert777