Autor Tema: Regularidad

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

22 Diciembre, 2019, 02:55 am
Leído 551 veces

Julio_fmat

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 2,398
  • País: cl
  • Karma: +0/-0
  • Sexo: Masculino
    • Fmat
Pruebe que si \( L \) es regular, entonces \( \text{Pref}(L)=\{x, \exists y, xy\in L\} \) es regular.

Hola, como puedo atacar este problema? Gracias
"Haz de las Matemáticas tu pasión".

22 Diciembre, 2019, 03:14 am
Respuesta #1

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,395
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Hola, como puedo atacar este problema? Gracias

Hay varias formas. Quizá la más sencilla es construir un AFD que acepte \( \text{Pref}(L) \) usando el AFD que acepta \( L \).
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

23 Diciembre, 2019, 06:07 am
Respuesta #2

Julio_fmat

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 2,398
  • País: cl
  • Karma: +0/-0
  • Sexo: Masculino
    • Fmat
Hola, como puedo atacar este problema? Gracias

Hay varias formas. Quizá la más sencilla es construir un AFD que acepte \( \text{Pref}(L) \) usando el AFD que acepta \( L \).

Muchas Gracias, pero no me queda muy claro. Por definicion sabemos que el lenguaje aceptado por un AFD es \( \mathcal{L}(M)=\{x\in \Sigma^{*}, \exists f\in F, (s,x) \, \vdash^{*}_M\, (f,\varepsilon) \} \).

Nos sirve saber esta informacion?

"Haz de las Matemáticas tu pasión".

23 Diciembre, 2019, 07:27 am
Respuesta #3

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,395
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Muchas Gracias, pero no me queda muy claro. Por definicion sabemos que el lenguaje aceptado por un AFD es \( \mathcal{L}(M)=\{x\in \Sigma^{*}, \exists f\in F, (s,x) \, \vdash^{*}_M\, (f,\varepsilon) \} \).

Nos sirve saber esta informacion?

Sin duda que sí. Ésa que escribiste es la definición del lenguaje reconocido (o aceptado) por un AFD \( M \). Sin ese concepto, imposible avanzar.

Piensa en lo siguiente: disponemos de un AFD que acepta \( L \). Llama \( M=(Q,\Sigma,\delta,q_0,F) \) a dicho autómata. ¿Cómo sería un AFD \( M^\prime \) que aceptara \( \text{Pref}(L) \)? ¿Dónde quedaría parado \( M \) al procesar una cadena \( x\in \text{Pref}(L) \)? Supón que queda parado en el estado \( q_j \). En símbolos, ¿cómo sería eso? Usando tu notación, \( (s,x) \vdash^{|x|}_M (q_j,\epsilon) \), ¿no? ¿Qué tendría que pasar (a nivel del diagrama de transición del autómata) para que \( x \) realmente pertenezca a \( \text{Pref}(L) \)? Si puedes contestar esa pregunta, ya lo tienes al ejercicio...
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print