Autor Tema: Autómatas de estado finito

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

09 Diciembre, 2014, 06:33 pm
Leído 3718 veces

Cabudare

  • $$\Large \color{red}\pi\,\pi$$
  • Mensajes: 33
  • Karma: +0/-0
  • Sexo: Masculino
Tengo dificultades para comprender el tema de autómatas de estados finitos, por lo que, por favor, necesito su ayuda, en la medida de lo posible. El ejercicio es el siguiente (mi traducción no es muy buena):

Sea \( G=(V,T,S,P) \) la estructura de frase de la gramática con \( V=\left\{{A,S}\right\} \) y \( T\left\{{a,b}\right\} \) y el conjunto de producción P consintiendo en:

\( S\to aSa|aBa \)
\( B\to bB|b \)(Modificado)


i. Demuestre que aaaabbbbaaaa pertence al lenguaje generado por G.

ii. Demuestre que aaaabbabaaaa no pertenece al lenguaje generado por G.

iii. ¿Cuál es el lenguaje generado por G?

09 Diciembre, 2014, 09:42 pm
Respuesta #1

luis

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 304
  • Karma: +1/-0
  • Sexo: Masculino
\( S\to aSa|aBa \)
\( B\to bBb \)

supongo que debe ser

\( B\to bBb|\epsilon \)

¿cómo intentaste hacer la primera parte?

09 Diciembre, 2014, 10:22 pm
Respuesta #2

Cabudare

  • $$\Large \color{red}\pi\,\pi$$
  • Mensajes: 33
  • Karma: +0/-0
  • Sexo: Masculino
En realidad es \( B\to bB|b \)

09 Diciembre, 2014, 10:24 pm
Respuesta #3

Cabudare

  • $$\Large \color{red}\pi\,\pi$$
  • Mensajes: 33
  • Karma: +0/-0
  • Sexo: Masculino
Parte i

\( S\Rightarrow aSa  \)
\( \Rightarrow aaSaa  \)
\( \Rightarrow aaaSaaa  \)
\( \Rightarrow aaaaBaaaa  \)
\( \Rightarrow aaaabBaaaa  \)
\( \Rightarrow aaaabbBaaaa  \)
\( \Rightarrow aaaabbbBaaaa  \)
\( \Rightarrow aaaabbbbaaaa  \)

¿Está bien?

09 Diciembre, 2014, 10:25 pm
Respuesta #4

Cabudare

  • $$\Large \color{red}\pi\,\pi$$
  • Mensajes: 33
  • Karma: +0/-0
  • Sexo: Masculino
Las partes ii y iii no se cómo hacerlas.

09 Diciembre, 2014, 11:38 pm
Respuesta #5

luis

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 304
  • Karma: +1/-0
  • Sexo: Masculino

la derivación que escribiste para la parte uno está bien.

Las partes ii y iii no se cómo hacerlas.

desconozco el grado de rigor que esperas desarrollar. pero puedo comentarte algunas cosas...

1. observa que las reglas asociadas a \( S \) preservan una única ocurrencia del no terminal \( S \), o hacen aparecer un noterminal \( B \)
2. observa que las reglas asociadas a \( B \) preservan una única ocurrencia del no terminal \( B \), o permiten concluír la derivación de una palabra.

luego, si una palabra se deriva con \( k \) aplicaciones de reglas, deben usarse \( m \) aplicaciones de las reglas para \( S \) y \( n \) aplicaciones de las reglas para \( B \), de forma que \( k = m+n \).

las \( m \) aplicaciones de las reglas para \( S \) corresponden a \( m-1 \) aplicaciones de la primera, y una de la segunda. es decir, se escriben \( 2m \) aes y una B.

las \( n \) aplicaciones de las reglas para \( B \) corresponden a \( n-1 \) aplicaciones de la primera, y una de la segunda. es decir, se escriben \( n \) bes y se termina la derivación.

en breve, las palabras tienen el aspecto \( a^mb^na^m \), con \( n, m \geq 1 \).

una justificación adecuada, para mi gusto, exige un argumento inductivo en la cantidad de aplicaciones de reglas y otra en los naturales.

saludos

luis

09 Diciembre, 2014, 11:42 pm
Respuesta #6

Cabudare

  • $$\Large \color{red}\pi\,\pi$$
  • Mensajes: 33
  • Karma: +0/-0
  • Sexo: Masculino
Gracias. La parte iii tampoco la tengo muy clara.