Autor Tema: Sobre autómata determinístico sobre un alfabeto de una letra.

0 Usuarios y 1 Visitante están viendo este tema.

07 Septiembre, 2018, 05:51 pm
Leído 2127 veces

lindtaylor

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,371
  • País: cl
  • Karma: +0/-2
  • Sexo: Masculino
 
El libro es: Word processing in groups del autor Epstein


¿Por qué si \( n \) es el período, el lenguaje \( L \) aceptado por el autómata es \(  L_1\cup (x^n)^{\ast}L_2 \)?
¿Cómo deducen que \(  L_1=\left\{\epsilon,x^2,x^4\right\} \) y \( L_2=\left\{x^6,x^9,x^{10}\right\} \)?
....

08 Septiembre, 2018, 11:34 pm
Respuesta #1

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,447
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
¿Por qué si \( n \) es el período, el lenguaje \( L \) aceptado por el autómata es \(  L_1\cup (x^n)^{\ast}L_2 \)?

¿Cómo puede ser un AFD en el que el alfabeto de entrada \( \Sigma \) tiene un símbolo solo (o sea, \( \Sigma=\{x\} \))? Bueno, si hay un símbolo solo, de cada estado puede salir una flecha sola. Intentemos dibujar un autómata con esta característica.

  • Imagina que dibujas el estado inicial, \( q_0 \), y ahora te toca dibujar las transiciones. Como no hay otro estado, \( q_0 \) ha de ser también final y la única alternativa es hacer un loop en él (esto es, \( \delta(q_0,x)=q_0 \)). El lenguaje aceptado por este autómata sería \( \{\epsilon,x,x^1,x^2,\dots\}=\Sigma^* \).

  • Ahora imagina que agregas otro estado, \( q_1 \), y haces que \( \delta(q_0,x)=q_1 \). Como quieres evitar los loops, sigues agregando estados \( q_i \) y dibujando flechas de forma que \( \delta(q_i,x)=q_{i+1} \). Pero como la cantidad de estados es finita, no puedes agregar estados infinitamente. Quiere decir que en algún momento, la única flecha saliente de alguno de estos nuevos estados que agregues apuntará a algún estado ya existente en la secuencia. Y ahí se formará el loop. En el libro llama \( n \) a la longitud (o sea, número de aristas o transiciones o flechas —como quieras llamarlas—) del ciclo que se forma en el grafo.

Este sencillo argumento muestra que un AFD con un símbolo solo tendrá forzosamente la forma de la figura que el autor muestra en su libro.

¿Cómo deducen que \(  L_1=\left\{\epsilon,x^2,x^4\right\} \) y \( L_2=\left\{x^6,x^9,x^{10}\right\} \)?

Mirando el grafo. ¿Cuáles son las cadenas que acepta el autómata de la figura?

  • Primero que nada, acepta a la cadena vacía porque el estado inicial es final. También acepta a la cadena \( x^2 \) (no acepta a \( x \) porque el segundo estado no es final) y a la cadena \( x^4 \).

  • Luego observa que empieza el loop. El autómata acepta a \( x^6 \), a \( x^9 \) y \( x^{10} \). Como el loop continúa, también acepta a \( x^{12} \), \( x^{15} \) y \( x^{16} \). Así sucesivamente... Estaría aceptando al siguiente conjunto:

    \( \begin{align*}
    \{x^6, x^9,x^{10},x^{12},x^{15},x^{16},\dots\}&=\{\epsilon\}\{x^6, x^9,x^{10}\}\cup \{x^6\}\{x^6, x^9,x^{10}\}\cup \{x^6\}^2\{x^6, x^9,x^{10}\}\cup \dots\\
    &=(\{\epsilon\}\cup \{x^6\}\cup \{x^6\}^2\cup \dots)\{x^6, x^9,x^{10}\}\\
    &=\{x^6\}^*\{x^6, x^9,x^{10}\}
    \end{align*} \)

En consecuencia, el lenguaje aceptado por el autómata del ejemplo es: \( \{\epsilon, x^2,x^4\}\cup \{x^6\}^*\{x^6, x^9,x^{10}\} \). Como ves, tiene la forma \( L_1\cup \{x^n\}^*L_2 \). Añado: Es simplemente estrellado porque el operador estrella de Kleene se aplica a un lenguaje con una cadena sola, que es \( x^n \).

Saludos.
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print