Scribd
Cargar
201 vistas5 páginas

Automatas de Pila

Este documento presenta 5 ejemplos de autómatas de pila. Cada ejemplo incluye la descripción del autómata mediante su quintupla (conjuntos de estados, alfabeto de entrada, alfabeto de pila, estado inicial, estados finales) y su función de transición. Los autómatas reconocen lenguajes de la forma anbn, anban+1, anbncn+m+1 y variaciones de estos. Se muestran las transiciones entre los estados y los cambios en la pila para cada entrada procesada.

Cargado por

Danny Tapias Duque
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOCX, PDF, TXT o lee en línea desde Scribd
201 vistas5 páginas

Automatas de Pila

Este documento presenta 5 ejemplos de autómatas de pila. Cada ejemplo incluye la descripción del autómata mediante su quintupla (conjuntos de estados, alfabeto de entrada, alfabeto de pila, estado inicial, estados finales) y su función de transición. Los autómatas reconocen lenguajes de la forma anbn, anban+1, anbncn+m+1 y variaciones de estos. Se muestran las transiciones entre los estados y los cambios en la pila para cada entrada procesada.

Cargado por

Danny Tapias Duque
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOCX, PDF, TXT o lee en línea desde Scribd

Taller 2: Autómatas de Pila

Danny Tapias Duque

Institución Universitaria Digital de Antioquia

Desarrollo de Software

PREPROF2102TC 20200003: Autómatas, Gramáticas y Lenguajes

Docente. Joaquín Fernando Aguilar Camacho

Noviembre 2021
1. a b n c n +1 para n>0

Estado Pila x Pila Estado Pila x Pila


actual leer actual leer
q0 abcc Z q0 abbccc Z
q1 bcc AZ q1 bbccc AZ
q2 cc AAZ q1 bccc AAZ
q2 c AZ q2 ccc AAAZ
q3 λ Z q2 cc AAZ
q2 c AZ
q3 λ Z

K= { q 0 , q 1 , q 2 ,q 3 } , Σ= { a ,b , c } , Γ= { λ , A , Z } , Z , S=q 0 , F= { q 3 } ,
δ ={q 0 ( a , λ ; A )=q 1, q 1 ( b , λ ; A ) =q 1 , q 1 ( b , λ ; A ) =q 2 , q 2 ( c , A ; λ ) =q 2 , q 2 ( c , A ; λ )=q 3 , q 3 ( λ , Z , λ )=q 3}

2. a a b n aa cn +2 a para n> 0
Estado Pila x leer Pila Estado Pila x leer Pila
actual actual
q0 aabaaccca Z q0 aabbbaaccccc Z
a
q1 abaaccca AZ q1 abbbaaccccca AZ
q2 baaccca AAZ q2 bbbaaccccca AAZ
q2 aaccca AAAZ q2 bbaaccccca AAAZ
q0 accca AAAAZ q2 baaccccca AAAAZ
q3 ccca AAAZ q2 aaccccca AAAAAZ
q3 cca AAZ q0 accccca AAAAAAZ
q4 ca AZ q3 ccccca AAAAAZ
q1 a Z q3 cccca AAAAZ
q5 λ λ q3 ccca AAAZ
q3 cca AAZ
q4 ca AZ
q1 a Z
q5 λ λ

K= { q 0 , q 1 , q 2 ,q 3 ,q 4 , q 5 } , Σ= {a , b , c } , Γ = { λ , A , Z } , Z , S=q 0 , F= {q 5 } ,

δ = { q 0 ( a , λ ; A )=q 1 , q 0 ( a , A ; λ )=q 3 , q 1 ( a , λ ; A )=q 2, q 1 ( a , Z ; λ ) =q 5 , q 2 ( b , λ ; A )=q 2 , q 2 ( a , λ ; A )=q 0 , q

3. a 3n b n para n>0
Estado Pila x leer Pila Estado Pila x leer Pila
actual actual
q0 aaab Z q0 aaaaaabb Z
q1 aab AZ q1 aaaaabb AZ
q0 ab AAZ q0 aaaabb AAZ
q2 b AZ q2 aaabb AZ
q2 λ Z q1 aabb AAZ
q3 λ λ q0 abb AAAZ
q2 bb AAZ
q2 b AZ
q2 λ Z
q3 λ λ

K= { q 0 , q 1 , q 2 ,q 3 } , Σ= { a ,b } , Γ ={ λ , A , Z } , Z , S=q 0 , F={ q 3 } ,

δ = { q 0 ( a , λ ; A )=q 1 , q 0 ( a , A ; λ )=q 2 , q 1 ( a , λ ; A )=q 0 ,q 2 ( a , λ ; A ) =q 1 , q 2 ( b , A ; λ )=q 2 , q 2 ( λ , Z ; λ )=q 3 }

4. a n b m c p para n , m, p>0 ; p=n+ m+1

Estado Pila x leer Pila Estado Pila x leer Pila


actual actual
q0 abccc Z q0 aabbccccc Z
q1 bccc AZ q0 abbccccc AZ
q2 ccc AAZ q1 bbccccc AAZ
q2 cc AZ q1 bccccc AAAZ
q2 c Z q2 ccccc AAAAZ
q3 λ λ q2 cccc AAAZ
q2 ccc AAZ
q2 cc AZ
q2 c Z
q3 λ λ
K= { q 0 , q 1 , q 2 ,q 3 } , Σ= { a ,b , c } , Γ= { λ , A , Z } , Z , S=q 0 , F= { q 3 } ,

δ = { q 0 ( a , λ ; A )=q 0 , q 0 ( a , λ ; A )=q 1 , q 1 ( b , λ ; A )=q 1, q 1 ( b , λ ; A ) =q 2 , q 2 ( c , A ; λ )=q 2 ,q 2 ( c , Z ; λ )=q 3 }

5. a n b n+1 para n> 0

Estado Pila x leer Pila Estado Pila x leer Pila


actual actual
q0 abb Z q0 aabbb Z
q0 bb AZ q0 abbb AZ
q1 b Z q0 bbb AAZ
q2 λ λ q1 bb AZ
q1 b Z
q2 λ λ

K= { q 0 , q 1 , q 2 } , Σ= { a , b } , Γ ={ λ , A , Z } , Z , S=q 0 , F={ q 2 } ,

δ = { q 0 ( a , λ ; A )=q 0 , q 0 ( b , A ; λ )=q 1 , q 1 ( b , A ; λ )=q 1, q 1 ( b , Z ; λ ) =q 2 }

También podría gustarte