Autor Tema: Lenguajes regulares

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

22 Diciembre, 2019, 02:26 am
Leído 768 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 también lo es \( L'=\left\{uw, u\in \Sigma^*, w\in L\right\}. \) Hallar una expresión regular para \( L' \).
"Haz de las Matemáticas tu pasión".

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

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,395
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Si \( L \) es regular, entonces \( L=\mathbf{r} \) para una cierta expresión regular \( \mathbf{r} \).

Si \( \Sigma=\{a_1,\dots,a_n\} \), entonces \( L'=(a_1|a_2|\cdots|a_n)^*\mathbf{r} \).
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

23 Diciembre, 2019, 05:54 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
Si \( L \) es regular, entonces \( L=\mathbf{r} \) para una cierta expresión regular \( \mathbf{r} \).

Si \( \Sigma=\{a_1,\dots,a_n\} \), entonces \( L'=(a_1|a_2|\cdots|a_n)^*\mathbf{r} \).

Muchas Gracias, pero no me queda claro aun la demostracion de que \( L' \) es regular, podemos usar el Lema del Bombeo?
"Haz de las Matemáticas tu pasión".

23 Diciembre, 2019, 01:36 pm
Respuesta #3

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,395
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Muchas Gracias, pero no me queda claro aun la demostracion de que \( L' \) es regular, podemos usar el Lema del Bombeo?

El lema de bombeo suele emplearse para demostrar que un lenguaje es NO regular. Para demostrar que un lenguaje es regular, basta proporcionar un AFD para él (o alguna de sus variantes equivalentes, como AFND y AFND-\( \epsilon \)) o bien una expresión regular.

En este caso, estoy proporcionando una expresión regular para \( L' \).
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

26 Diciembre, 2019, 03:21 am
Respuesta #4

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,395
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Si \( L \) es regular, entonces \( L=\mathbf{r} \) para una cierta expresión regular \( \mathbf{r} \).

Si \( \Sigma=\{a_1,\dots,a_n\} \), entonces \( L'=(a_1|a_2|\cdots|a_n)^*\mathbf{r} \).

Algunos podrían decir que una expresión regular para \( L' \) es \( \Sigma^*\textbf{r} \), o sea, sustituir \( (a_1|a_2|\cdots|a_n) \) por \( \Sigma \). En mi opnión, sería un abuso de notación pero me consta que tal vez sea la respuesta esperada por algunas personas... (lo digo por si aparece así en algún solucionario).

Digo que es un abuso de notación porque \( \Sigma=\{a_1,\dots,a_n\} \) es un conjunto mientras que \( (a_1|a_2|\cdots|a_n) \) es una expresión regular para \( \Sigma \).

En realidad, es el mismo abuso de notación empleado cuando escribo \( L=\mathbf{r} \) como acá:

Si \( L \) es regular, entonces \( L=\mathbf{r} \) para una cierta expresión regular \( \mathbf{r} \).

Estrictamente hablando, lo que está a la izquierda es el lenguaje \( L \) y a la derecha está la expresión regular \( \textbf{r} \), que son "objetos matemáticos" diferentes. En realidad, uno debería escribir:

\( L=L(\textbf{r}) \)

donde \( L(\textbf{r}) \) es el lenguaje representado por la expresión regular \( \textbf{r} \). Pero es un abuso de notación muy común.
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print