[Sintaxis & Semantica de L.] Dudas triviales

Discusión cerrada
Ir a 12 ÚltimaÚltima
  1. #1
    AsD
    Life goals status ... Avatar de AsD
    Registración
    Dec 2002
    Mensajes
    3,193

    [Sintaxis & Semantica de L.] Dudas triviales

    Buenas, taba preparando el final y me surgieron un par de dudas...

    Primero que nada para ahorrar flechas se puede hacer esto en un automata:
    Si tenemos el estado 0 y el estado 1, y del 0 vamos al 1 con los caracteres A y B, entonces pongo una flecha que vaya al caracter 1 y la etiqueto asi: a,b

    Segundo, si hago la interseccion de 2 AFDs y me da un automata sin estados finales, significa que dicho AF no reconoce a ninguna palabra, pero si reconoce al lenguaje vacio (|L| = 0) V o F. Justificar

    Tercero, ¿como represento al lenguaje vacio con una expresion regular?

    Desde ya muchas gracias,

    Salu2!
    • Me gusta
    Me gusta
    The time has come to show off what you are made of... Are you ready?
     

  2. Compartí este Tema:
    • Vistas: 1730
    • Mensajes: 23
    Seguí este Tema: Suscribite
  3. #2
    <> Avatar de Vismund C.
    Registración
    Feb 2003
    Mensajes
    6,376
    Ubicación
    Argentina
    Primero que nada para ahorrar flechas se puede hacer esto en un automata:
    Si tenemos el estado 0 y el estado 1, y del 0 vamos al 1 con los caracteres A y B, entonces pongo una flecha que vaya al caracter 1 y la etiqueto asi: a,b
    Si se puede.

    Tercero, ¿como represento al lenguaje vacio con una expresion regular?
    ¿El lenguaje vacio es regular?
    • Me gusta
    Me gusta
     

  4. #3
    AsD
    Life goals status ... Avatar de AsD
    Registración
    Dec 2002
    Mensajes
    3,193
    Citar Mensaje original enviado por Dem0 Ver Mensaje
    Si se puede.



    ¿El lenguaje vacio es regular?
    Un lenguaje es regular si existe una ER que lo represente, existe un automata que lo reconozca o existe una GR que lo genere.

    El tema es que la ER () representa al lenguaje vacio, y un automata finito sin estados finales tambien lo reconoce (todabia no llegue a estudiar Gramaticas como para decir si lo genera o no)

    Por otro lado no vi el impedimento que un AF deba tener un estado final, yo se que es obligatorio tener un inicial.

    "Un AF reconoce a un LR cuando ACEPTA cada palaba del lenguaje y RECHAZA toda cadena que no es una palabra del lenguaje" Muchnik pag 35 parrafo 3
    Como vemos un AF sin estados finales no reconoceria palabras, y en tal caso reconoceria el lenguaje vacio.

    Igual la duda me surgio al interceptar 2 AFDs y que me diera un AF sin estados finales, entonces empece a relacionar por que no tiene estados finales y es por que la interseccion de 2 lenguajes me puede dar VACIO puesto que son conjuntos, sin embargo queria saber si un AF sin estados finales puede existir, y si este reconoce al lenguaje vacio.

    Gracias por las respuesta, ahora faltaria saber si relamente el lenguaje vacio es regular o no, puesto que no puedo aseverar al 100% que un AF sin estados finales es un AF.

    Salu2!
    • Me gusta
    Me gusta
    The time has come to show off what you are made of... Are you ready?
     

  5. #4
    <> Avatar de Vismund C.
    Registración
    Feb 2003
    Mensajes
    6,376
    Ubicación
    Argentina
    Encontré esta definición de "Acceptor Finite State Machine" (o Automata Finito Reconocedor) en wiki, por ahí te sirve:

    Depending on the type there are several definitions. An acceptor finite-state machine is a quintuple (Σ,S,s0,δ,F), where:

    * Σ is the input alphabet (a finite, non-empty set of symbols).
    * S is a finite, non-empty set of states.
    * s0 is an initial state, an element of S. In a Nondeterministic finite state machine, s0 is a set of initial states.
    * δ is the state-transition function.
    * F is the set of final states, a (possibly empty) subset of S.
    O sea que, según esto, un AF sin estados finales es un AF, y se puede aplicar la definición de Muchnik.
    • Me gusta
    Me gusta
     

  6. #5
    AsD
    Life goals status ... Avatar de AsD
    Registración
    Dec 2002
    Mensajes
    3,193
    Citar Mensaje original enviado por Dem0 Ver Mensaje
    Encontré esta definición de "Acceptor Finite State Machine" (o Automata Finito Reconocedor) en wiki, por ahí te sirve:



    O sea que, según esto, un AF sin estados finales es un AF, y se puede aplicar la definición de Muchnik.
    Oh bendita wiki, gracias!!!
    • Me gusta
    Me gusta
    The time has come to show off what you are made of... Are you ready?
     

  7. #6
    Avatar de 01010
    Registración
    May 2006
    Mensajes
    275
    un AF acepta una palabra si procesas todos los caracteres y el automata termina en un estado final, en este caso no tenes estados finales asique siempre vas a rechazar todas las palabras y no va a reconocer ninguna. para mi es Verdadera
    • Me gusta
    Me gusta
     

  8. #7
    algo sobre vos Avatar de BroS
    Registración
    May 2000
    Mensajes
    7,667
    Ubicación
    Argentina
    Citar Mensaje original enviado por AsD Ver Mensaje
    Buenas, taba preparando el final y me surgieron un par de dudas...

    Primero que nada para ahorrar flechas se puede hacer esto en un automata:
    Si tenemos el estado 0 y el estado 1, y del 0 vamos al 1 con los caracteres A y B, entonces pongo una flecha que vaya al caracter 1 y la etiqueto asi: a,b

    Segundo, si hago la interseccion de 2 AFDs y me da un automata sin estados finales, significa que dicho AF no reconoce a ninguna palabra, pero si reconoce al lenguaje vacio (|L| = 0) V o F. Justificar

    Tercero, ¿como represento al lenguaje vacio con una expresion regular?

    Desde ya muchas gracias,

    Salu2!
    la primera si, generalmente se suele abreviar así
    segunda supongo que si, si tenes un AFD 'M' sin estados finales entonces L(M) es el lenguaje vacío
    la tercera, en mi curso (yo hago computación en exactas) por definición de expresiones regulares se dice que "la expresión regular Ø (como el vacío de conjuntos) define el lenguaje vacío" , tendrias que ver q convención usan en tu caso, pero existir existe por el vacio es regular asiq de alguna forma lo tenes que representar mediante una expresion regular
    • Me gusta
    Me gusta
     

  9. #8
    AsD
    Life goals status ... Avatar de AsD
    Registración
    Dec 2002
    Mensajes
    3,193
    Citar Mensaje original enviado por 01010 Ver Mensaje
    un AF acepta una palabra si procesas todos los caracteres y el automata termina en un estado final, en este caso no tenes estados finales asique siempre vas a rechazar todas las palabras y no va a reconocer ninguna. para mi es Verdadera
    Hay un tema, si el AF no tiene estados finales, entonces no reconoce, no acepta ni rechaza nada. Entonces ¿como seria posible que reconozca al lenguaje vacio, si justamente no reconoce? ¿o si?


    Salu2!
    • Me gusta
    Me gusta
    The time has come to show off what you are made of... Are you ready?
     

  10. #9
    algo sobre vos Avatar de BroS
    Registración
    May 2000
    Mensajes
    7,667
    Ubicación
    Argentina
    Citar Mensaje original enviado por AsD Ver Mensaje
    Hay un tema, si el AF no tiene estados finales, entonces no reconoce, no acepta ni rechaza nada. Entonces ¿como seria posible que reconozca al lenguaje vacio, si justamente no reconoce? ¿o si?


    Salu2!
    como no rechaza? jaja, si rechaza cualquier entrada porq no tiene estados finales
    • Me gusta
    Me gusta
     

  11. #10
    Avatar de 01010
    Registración
    May 2006
    Mensajes
    275
    pensalo asi, si procesaste la palabra y terminaste en un estado no final significa q la rechaza, y si termina en un estado final la acepta, entonces de hecho te rechaza cualquier palabra que le mandes porque no tiene estados finales y siempre vas a terminar en estados no finales y entonces no te acepta nada y justamente no te tiene que aceptar nada porque el leguaje esta vacio no hay ninguna palabra que deba aceptar
    pd: fijate q si tenes un automata en el que los estados finales estan aislados o desconectados de alguna manera con el automata principal, no se si se entiende lo que digo, pero ahi te va a pasar lo mismo, vas a reconocer el leguaje vacio
    • Me gusta
    Me gusta
    Última edición por 01010 : 05-02-08 el 06:54 PM
     

  12. #11
    AsD
    Life goals status ... Avatar de AsD
    Registración
    Dec 2002
    Mensajes
    3,193
    Citar Mensaje original enviado por BroS Ver Mensaje
    como no rechaza? jaja, si rechaza cualquier entrada porq no tiene estados finales
    "La Maquina de Mealy es un AF que no tiene estados finales, porque no es un reconocedor; en cambio, tiene la capacidad de leer una caracter por vez, y de producir o 'emitir' un caracter como respuesta al caracter leido"
    [...]
    "Si bien las Maquinas de Mealy no pueden aceptar (ni rechazar) cadenas de entrada porque no tienen estados finales, si pueden generar eventos que posibiliten el reconocimiento o el rechazo de cadenas, a quienes analizan los resultados de estas maquinas."

    Es por eso que decia que no rechazaba, por que tome como ejemplo la maquina de Mealy que no tiene estados finales.

    Citar Mensaje original enviado por 01010 Ver Mensaje
    pensalo asi, si procesaste la palabra y terminaste en un estado no final significa q la rechaza, y si termina en un estado final la acepta, entonces de hecho te rechaza cualquier palabra que le mandes porque no tiene estados finales y siempre vas a terminar en estados no finales y entonces no te acepta nada y justamente no te tiene que aceptar nada porque el leguaje esta vacio no hay ninguna palabra que deba aceptar
    pd: fijate q si tenes un automata en el que los estados finales estan aislados o desconectados de alguna manera con el automata principal, no se si se entiende lo que digo, pero ahi te va a pasar lo mismo, vas a reconocer el leguaje vacio
    Es como que si no tomamos el ejemplo que da Muchnik de la maquina de Mealy, lo ideal seria decir que el AF sin estados finales reconoce al lenguaje vacio, dado que acepta cada cadena del lenguaje y rechaza a las que no lo son (todas).

    -----------*-----------

    Agrego una mas,

    Sea L el lenguaje vacio, dicho lenguaje es finito dado que | L | = 0. V o F
    • Me gusta
    Me gusta
    The time has come to show off what you are made of... Are you ready?
     

  13. #12
    Avatar de 01010
    Registración
    May 2006
    Mensajes
    275
    nah eso de mealy y moore es otra cosa tiene que ver con la forma de accionar si es por el estado en que esta o por la transicion

    la otra: un conjunto vacio es un conjunto finito
    • Me gusta
    Me gusta
     

  14. #13
    <> Avatar de Vismund C.
    Registración
    Feb 2003
    Mensajes
    6,376
    Ubicación
    Argentina
    "La Maquina de Mealy es un AF que no tiene estados finales, porque no es un reconocedor; en cambio, tiene la capacidad de leer una caracter por vez, y de producir o 'emitir' un caracter como respuesta al caracter leido"
    [...]
    "Si bien las Maquinas de Mealy no pueden aceptar (ni rechazar) cadenas de entrada porque no tienen estados finales, si pueden generar eventos que posibiliten el reconocimiento o el rechazo de cadenas, a quienes analizan los resultados de estas maquinas."

    Es por eso que decia que no rechazaba, por que tome como ejemplo la maquina de Mealy que no tiene estados finales.
    Pero la Maquina de Mealy no es Reconocedor, entonces el concepto de "aceptar" o "rechazar" no se aplica.
    • Me gusta
    Me gusta
     

  15. #14
    AsD
    Life goals status ... Avatar de AsD
    Registración
    Dec 2002
    Mensajes
    3,193
    Citar Mensaje original enviado por Dem0 Ver Mensaje
    Pero la Maquina de Mealy no es Reconocedor, entonces el concepto de "aceptar" o "rechazar" no se aplica.
    ¿Que significa Reconocedor? Por que en el libro que tengo no ta

    Gracias!

    PD:¿Estas en la UBA o UTN?
    • Me gusta
    Me gusta
    The time has come to show off what you are made of... Are you ready?
     

  16. #15
    <> Avatar de Vismund C.
    Registración
    Feb 2003
    Mensajes
    6,376
    Ubicación
    Argentina
    Citar Mensaje original enviado por AsD Ver Mensaje
    ¿Que significa Reconocedor? Por que en el libro que tengo no ta

    Gracias!

    PD:¿Estas en la UBA o UTN?
    UTN.

    Reconocedor son todos los Automatas que vemos en clase, fijate que hay un capítulo (cerca de los capitulos con la implementación en C) que habla de Automatas como Reconocedores y como Reconocedores/Accionadores.

    La maquina de Mealy, la de Turing (creo que entra en la categoría) y la de Moore no entran en la categoría porque cumplen otros objetivos y para eso no necesitan estados finales.
    • Me gusta
    Me gusta
    Última edición por Vismund C. : 06-02-08 el 01:33 AM
     

  17. Compartí este Tema:
    • Vistas: 1730
    • Mensajes: 23
    Seguí este Tema: Suscribite
Discusión cerrada
Ir a 12 ÚltimaÚltima

Temas Similares

  1. Sintaxis y Semantica del Lenguaje
    By hernang_87 in forum Estudios, Carreras y Universidades
    Mensajes: 195
    Último Mensaje: 28-05-10, 09:16 AM
  2. Sintaxis, problema al compilar
    By yomariano in forum Estudios, Carreras y Universidades
    Mensajes: 4
    Último Mensaje: 09-07-08, 04:59 PM