Autor Tema: Lenguajes regulares 3

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

23 Diciembre, 2019, 06:39 am
Leído 288 veces

Julio_fmat

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 2,398
  • País: cl
  • Karma: +0/-0
  • Sexo: Masculino
    • Fmat
Demuestre o de un contraejemplo: Todo subconjunto de un lenguaje regular es regular.

Hola, alguna idea para este problema? Gracias.
"Haz de las Matemáticas tu pasión".

23 Diciembre, 2019, 07:10 am
Respuesta #1

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,395
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
¿Cuál es el primer ejemplo de lenguaje NO regular que a uno le suelen mostrar? Intenta responder a esa pregunta antes de ver el spoiler. Ese lenguaje, ¿puede ser visto como un subconjunto de un lenguaje regular?
Spoiler
No me extrañaría que el primero que hayas visto, haya sido \( L=\{0^k1^k:k\geq 0\} \). Éste es un lenguaje de los llamados libres de contexto; no es suficiente el formalismo de los autómatas finitos deterministas para reconocerlo; hace falta lo que quizás ya estudiaste que es un autómata de pila.

Ahora bien, observa que \( L\subseteq \textbf{0}^*\textbf{1}^* \)
[cerrar]
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

03 Enero, 2020, 04:17 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
¿Cuál es el primer ejemplo de lenguaje NO regular que a uno le suelen mostrar? Intenta responder a esa pregunta antes de ver el spoiler. Ese lenguaje, ¿puede ser visto como un subconjunto de un lenguaje regular?
Spoiler
No me extrañaría que el primero que hayas visto, haya sido \( L=\{0^k1^k:k\geq 0\} \). Éste es un lenguaje de los llamados libres de contexto; no es suficiente el formalismo de los autómatas finitos deterministas para reconocerlo; hace falta lo que quizás ya estudiaste que es un autómata de pila.

Ahora bien, observa que \( L\subseteq \textbf{0}^*\textbf{1}^* \)
[cerrar]

Un subconjunto de un lenguaje regular no es necesariamente regular. Por ejemplo, \( L=\{a^nb^n: n\ge 1\} \) es un sublenguaje del lenguaje regular \( a^*b^* \), pero \( L \) mismo no es regular.

¿Esta bien?
"Haz de las Matemáticas tu pasión".

07 Enero, 2020, 04:10 am
Respuesta #3

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,395
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Sí, está bien.
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print