Por qué no es este un lenguaje regular?

Question

Estoy atascado como para averiguar por qué $L_1$={$n^p$ | $p$ = un número primo} no es un lenguaje regular, pero $L_2$={$n^p$ | $p$ = un número primo delimitada por un número fijo de f} es. Puedo ver que $L_2$ es un lenguaje finito por lo que es un lenguaje regular. Pero me parece que no puede encontrar una manera de construir una máquina de estados finita (es decir, dibujar un diagrama de transición) que el modelo de este.

Gracias a todos.

Answer 1

Sugerencia: Usted ha dado una perfectamente buena prueba de que $L_2$ es regular. Para mostrar que $L_1$ no es regular, el uso del Lema de Bombeo.

Supongamos que al contrario que el lenguaje es regular. Ya que hay arbitrariamente grande de los números primos, existen enteros $a$ $d\gt 0$ de manera tal que todas las cadenas de longitud $a+kd$ están en el idioma. Pero la progresión aritmética $(a+kd)$ contiene compuestos de números. Para elegir un $k_0$ tal que $a+k_0d \gt 1$. Entonces $$a+k_0d + (a+k_0d)d=a+(k_0+a+k_0d)d$$ es en nuestra progresión aritmética. Es divisible por $a+k_0d$ y mayor que $a+k_0d$, por lo que no es primo.

Answer 2

$L_1=\{ n^p\quad |\quad \text{p=prime number} \}$ no es lenguaje regular ,puede ser fácilmente demostrado por el lema de bombeo.
Deje $k$ ser el lema de bombeo constante.
y la cadena de $\alpha \beta \gamma$ $\epsilon$ , $a^p$ y $\epsilon$, respectivamente, tal que $\alpha \beta \gamma \in L_1$$|\beta|\geq k$.
Por lo tanto ,si la descomponemos $\beta$ a $\beta _1(|\beta_1|=r),\beta _2(|\beta_2|=t),\beta _3(|\beta_3|=s)$ tal que $|\beta_2| \neq \phi $,$|\beta_2| \leq k$.
A continuación, elija $i=p+1$ ,obtendremos $|\alpha \beta_1 \beta_2^i\beta_3\gamma|=p(1+t)$ que es un compuesto.

Pero si enlazamos el primer número por $f$, a continuación, enumerar todos los $p<f$ y construir un AFN que primero adivine el primer luego tomar muchas medidas para alcanzar el estado final.

Answer 3

Con el fin de mostrar que el $L_p = \{ a^i : \text{prime}(i) \}$ no es un lenguaje regular utilizando el lema de bombeo, se debe construir una cadena de $w \in L_p$ que no puede ser bombeado en la forma pertinente para regular idiomas. En este caso, el objetivo es mostrar que el bombeo de algunas cadenas de $w \in L_p$ va a generar una cadena cuya longitud es de composite. Aquí es relativamente simple, la prueba utilizando el lema de bombeo.

Supongamos que $L_p$ es regular. Desde $L_p$ es regular, existe un $\text{DFA}$ $M$ con $k$ estados tales que, para cada cadena de $z \in L_p$ tal que $k \leq \text{len}(z)$, $z$ puede ser descompuesto en subcadenas $uvw$ tal que $\text{len}(uv) \leq k$, $0 < \text{len}(v)$, y $uv^iw \in L_p$ todos los $i \geq 0$.

Deje $n$ ser un número primo. Desde $n$ es primo, la cadena de $a^n$ es un miembro de $L_p$. Desde $a^n$ es un miembro de $L_p$, $a^n$ puede ser descompuesto en subcadenas $uvw$ la satisfacción de las condiciones del lema de bombeo. En particular, $uv^{n + 1}w$ debe ser un miembro de $L_p$. Sin embargo, $\text{len}(uv^{n + 1}w)$ no es primo: $$ \begin{align} \text{len}(uv^{n + 1}w) & = \text{len}(uv^nvw) \\ & = \text{len}(uvw) +\text{len}(v^n) \\ & = n + n\cdot\text{len}(v) \\ & = n(1 + \text{len}(v)) \end{align} $$ Desde $n(1 + \text{len}(v))$ es compuesto, su longitud no es primo. Por lo tanto, $uv^{n + 1}w$ no es un miembro de $L_p$, una contradicción. Por lo tanto, $L_p$ no es un lenguaje regular.

Con el fin de mostrar que el lenguaje de los números primos delimitada por un número natural es regular, usted puede usar la construcción, lo que demuestra que cada lenguaje finito es regular. Sin embargo, puesto que usted ya sabe que cada lenguaje finito es regular, no hay necesidad de proporcionar a la construcción.

Answer 4

La construcción de DFA para l2: cada valor de f se traducirá en un nuevo lenguaje. Y cada lengua tiene su propio DFA.

Así, para un determinado valor de f, podemos construir un afd con f de los estados y de la marca de todos los estados correspondientes a los números primos como estado final.

por favor me corrija si estoy equivocado.