Autor Tema: Regularidad 2

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

22 Diciembre, 2019, 03:06 am
Leído 490 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 si los siguientes conjuntos son o no regulares:

\( A=\left\{a^{10^n}, n\ge 0 \right\} \) y \( B=\{w\in \{0..9\}^{*}, w \text{ representa } 10^n \text{ para algun } n\ge 0\} \)
"Haz de las Matemáticas tu pasión".

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

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,395
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Para demostrar que \( A \) es no regular aplica el lema de bombeo.
En cuanto a \( B \), es regular puesto que \( B=\textbf{1}\textbf{0}^* \).

Spoiler
Supón por absurdo que \( A \) es regular, y llama \( n_0 \) a la constante del lema de bombeo.

Toma \( w=a^{10^{n_0}} \). Esta cadena pertenece a \( A \) y además \( |w|=10^{n_0}\geq n_0 \). Por el lema de bombeo, \( w=xyz \) con
  • \( |xy|\leq n_0 \)
  • \( y\ne \epsilon \)
  • \( xy^mz\in A,\forall m\in \mathbb{N} \)
Como \( |xy|\leq n_0 \), entonces \( x=a^p,y=a^q \) con \( p+q\leq n_0 \) luego \( z=a^{10^{n_0}-(p+q)} \). El punto 3 del pumping lemma nos dice que \( a^{p}a^{mq}a^{10^{n_0}-(p+q)}=a^{10^{n_0}+(m-1)q}\in A \) para todo \( m \). Elige un \( m \) conveniente para que \( 10^{n_0}+(m-1)q \) no pueda ser nunca de la forma \( 10^k \).
[cerrar]
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print