Máquina de Estado de Finito-idt (1) (1)

download Máquina de Estado de Finito-idt (1) (1)

of 27

Transcript of Máquina de Estado de Finito-idt (1) (1)

  • 7/25/2019 Mquina de Estado de Finito-idt (1) (1)

    1/27

    MQUINA DE ESTADO DE

    FINITO

  • 7/25/2019 Mquina de Estado de Finito-idt (1) (1)

    2/27

    Mquina de estado fnito: Se defnecomo la 6-tupla

  • 7/25/2019 Mquina de Estado de Finito-idt (1) (1)

    3/27

    Encuentre el diarama de tran!ici"n deuna m#$uina de e!tado fnito

  • 7/25/2019 Mquina de Estado de Finito-idt (1) (1)

    4/27

    iarama de tran!ici"n

  • 7/25/2019 Mquina de Estado de Finito-idt (1) (1)

    5/27

    Encuentre el diarama de tran!ici"n deuna m#$uina de e!tado fnito

  • 7/25/2019 Mquina de Estado de Finito-idt (1) (1)

    6/27

  • 7/25/2019 Mquina de Estado de Finito-idt (1) (1)

    7/27

    Encuentre el diarama de tran!ici"n dela m#$uina de e!tado fnito!

  • 7/25/2019 Mquina de Estado de Finito-idt (1) (1)

    8/27

    Encuentre el diarama de e!tado! de la m#$uina dee!tado fnito!

  • 7/25/2019 Mquina de Estado de Finito-idt (1) (1)

    9/27

    Encuentre lo! con%unto! ele!tado inicial & la ta'la $ue defne el

    !iuiente e!tado & la! (uncione! de!alida para la m#$uina de e!tado fnito

  • 7/25/2019 Mquina de Estado de Finito-idt (1) (1)

    10/27

  • 7/25/2019 Mquina de Estado de Finito-idt (1) (1)

    11/27

    Determine el e!tado inicial & la ta'la $ue

    defne la! (uncione! de e!tado !iuiente& de !alida para cada ma$uina de e!tadofnito

    De!de $ue e!tado de'emo! comen)ar para $ue

    la cadena de entrada a''aaa' produ)ca la !alida

  • 7/25/2019 Mquina de Estado de Finito-idt (1) (1)

    12/27

    De!de $ue e!tado de'emo! comen)ar para $uela cadena de entrada a''aaa' produ)ca la !alida

    *+*+++*,

  • 7/25/2019 Mquina de Estado de Finito-idt (1) (1)

    13/27

    Encuentre el diarama de tran!ici"n de la m#$uina dee!tado fnito!

  • 7/25/2019 Mquina de Estado de Finito-idt (1) (1)

    14/27

    Aceptoras

    (tambin llamadas reconocedoraso discriminadoras): Son

    aquellas en donde la salida es binaria (s/no), depende

    nicamente del estado y existe un estado inicial. Puede

    decirse, entonces, que cuando la mquina produce una

    salida !positi"a! (es decir, un !si!), es porque #a !reconocido!

    o !aceptado! la secuencia de entrada. $n las mquinas de

    estados aceptoras, los estados con salida !positi"a! sedenominan estados finales.

    Transductoras: Son las ms %enerales, que con"ierten una

    secuencia de se&ales de entrada en una secuencia desalida, pudiendo sta ser binaria o ms comple'a, dependen

    de la entrada actual (no slo del estado) y pudiendo tambin

    prescindirse de un estado inicial.

  • 7/25/2019 Mquina de Estado de Finito-idt (1) (1)

    15/27

    AUTMATAS DE ESTADOFINITO

    E!te un tipo e!pecial de m#$uina dee!tado fnito !on de ran inter.! por!u relaci"n con lo! lenua%e!

    A$uello! e!tado! para lo! $ue laultima !alida (ue * !e llama / ESTADODE A0E1TA0IN 2

    .

  • 7/25/2019 Mquina de Estado de Finito-idt (1) (1)

    16/27

    Mue!tre !i cada m#$uina de e!tado fnitoe! un aut"mata de e!tado fnito & tracenue4amente el diarama de tran!ici"n

  • 7/25/2019 Mquina de Estado de Finito-idt (1) (1)

    17/27

  • 7/25/2019 Mquina de Estado de Finito-idt (1) (1)

    18/27

    Mue!tre $ue cada ma$uina de e!tadofnito e! una aut"mata de e!tado fnitotrace nue4amente el diarama

  • 7/25/2019 Mquina de Estado de Finito-idt (1) (1)

    19/27

    Trace de nue4o el diarama detran!ici"n del aut"mata de e!tado fnito

    como el diarama de tran!ici"n de unam#$uina de e!tado fnito

  • 7/25/2019 Mquina de Estado de Finito-idt (1) (1)

    20/27

    T d l di d i i"

  • 7/25/2019 Mquina de Estado de Finito-idt (1) (1)

    21/27

    Trace de nue4o el diarama de tran!ici"ndel aut"mata de e!tado fnito comodiarama de tran!ici"n de una m#$uina

    de e!tado fnito

  • 7/25/2019 Mquina de Estado de Finito-idt (1) (1)

    22/27

    dibu'e el dia%rama de transicin del autmata de estado

    inito .

    5alle la cadena de !alida para la cadena deentrada a''aaa''Indi$ue !i la cadena e! aceptada

    *ib ' l di d t i i d l t t d t d i it

  • 7/25/2019 Mquina de Estado de Finito-idt (1) (1)

    23/27

    *ibu'e el dia%rama de transicin del autmata de estado inito .

    5alle la cadena de !alida para la cadena de entradac'a'aacc'Indi ue !i la cadena e! ace tada

    d l di d i i" d l

  • 7/25/2019 Mquina de Estado de Finito-idt (1) (1)

    24/27

    Trace de nue4o el diarama de tran!ici"n delaut"mata de e!tado fnito como diarama detran!ici"n de una m#$uina de e!tado fnito

  • 7/25/2019 Mquina de Estado de Finito-idt (1) (1)

    25/27

    Di'u%e el diarama de tran!ici"n delautomata de e!tado fnito

    demuestre que cada mquina de estado inito es un

  • 7/25/2019 Mquina de Estado de Finito-idt (1) (1)

    26/27

    demuestre que cada mquina de estado inito es un

    autmata de estado inito y dibu'e de nue"o el dia%rama

    como corresponde.

  • 7/25/2019 Mquina de Estado de Finito-idt (1) (1)

    27/27

    aTrace el diarama de e!tado! para e!tama$uina de e!tado fnito

    'Si partimo! de 70u#l e! la cadena de !alida

    para la cadena de entrada a''ccc,