Autor Tema: Definir inductivamente el siguiente lenguaje

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

11 Marzo, 2013, 05:46 pm
Leído 2060 veces

Hernan_ER

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,431
  • Karma: +0/-0
  • Sexo: Masculino
Hola. Dados los lenguajes sobre el alfabeto {a,b} en su definición extensiva tengo que dar las reglas para definirlo inductivamente:

\( {L_1} = \left\{ {\varepsilon ,a,aa,aaaa,aaaaaaaa,...} \right\} \)

\( {L_2} = \left\{ {\varepsilon ,ab,abab,ababab,...,ba,baba,bababa,...} \right\} \)

Para L1 no puedo plantear algo que lo defina ya que lo que yo planteo me añade la palabra aaa que no está.

Para L2 lo que planteo es:

1.\( \varepsilon  \in {L_2} \)

2. Si \( w \in {L_2} \) entonces \( wab \in {L_2} \).

Ahí estaría definiendo la primer "sección" de palabras, pero ¿cómo puedo definirlo a todo en un solo conjunto de reglas? porque también podria escribirlo como una unión de conjuntos definidos inductivamente por separado.

Gracias

11 Marzo, 2013, 06:00 pm
Respuesta #1

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Para el primero:

\( \epsilon, a\in L_1 \)

Si \( w\in L_1 \) entonces \( ww\in L_1 \).

Para el segundo:

\( \epsilon, ab, ba\in L_2 \)

Si \( wb\in L_2 \) entonces \( wbab\in L_2 \)

Si \( wa\in L_2 \) entonces \( waba\in L_2 \).

11 Marzo, 2013, 06:12 pm
Respuesta #2

Hernan_ER

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,431
  • Karma: +0/-0
  • Sexo: Masculino
Entendí. Ahora tengo una duda con el concepto de la palabra vacía. Por ejemplo \( \varepsilon a\varepsilon a\varepsilon a \) ¿es lo mismo que \( aaa \) ?

Y en el caso que tuviera el lenguaje \( A = \left\{ {\varepsilon ,a,aa,aaa,aaaa,aaaaa,...} \right\} \), hay alguna diferencia en decir:
I.\( \varepsilon  \in {A} \)
II. Si \( w  \in {A} \) entonces \( aw  \in {A} \)

y decir:

I.\( \varepsilon  \in {A} \)
II. Si \( w  \in {A} \) entonces \( wa  \in {A} \)

Gracias

11 Marzo, 2013, 06:16 pm
Respuesta #3

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
1) Es lo mismo.

2) No hay diferencia.