Automatas

Solo disponible en BuenasTareas
  • Páginas : 9 (2232 palabras )
  • Descarga(s) : 0
  • Publicado : 8 de diciembre de 2010
Leer documento completo
Vista previa del texto
Trabajo Colaborativo No. 2

AUTÓMATAS Y LENGUAJES FORMALES
LENGUAJES INDEPENDIENTES DEL CONTEXTO

INTEGRANTES

MARIA DEL PILAR AMAYA

LEUDER GOMEZ

LUZ AMELFI OSPINA

ERIKA PATRICIA SAMACÁ

Tutor:

ING. JAIRO ARMANDO RIAÑO

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA
ESCUELA DE CIENCIAS BÁSICAS, TECNOLOGÍA E INGENIERÍA
INGENIERIA DE SISTEMAS
2009

1. Dado elsiguiente autómata con pila, indicar:

(a) Qué lenguaje reconoce
(b) Cuáles de las siguientes palabras son aceptadas por el autómata:
aabbc, abbc, bbcc, aabbbcc (mostrando la sucesión de descripciones instantáneas)

AP = ({a, b, c}, {A, B, S}, {q, r, s, t}, q, S, f, Ø)
f(q, a, S) = {(r, S)} f(s, b, S) = {(s, BS)}
f(q, a, A) = {(r, A)} f(s, b, A) ={(s, λ)}
f(q, b, S) = {(s, BS)} f(s, b, B) = {(s, BB)}
f(q, b, A) = {(s, λ)} f(s, c, B) = {(t, λ)}
f(r, a, S) = {(q, AS)} f(t, c, B) = {(t, λ)}
f(r, a, A) = {(q, AA)} f(t, λ, S) = {(t, λ)}

Σ = alfabeto es a b c
A, B, S simulador de la pila
q, r, s, t, son los estados del autómata
φi =q
φf = t
S estado inicial de la pila
Ø estado final de la pila
Q s / s ; Q A / A

Q, s / AS

b, S / BS
b, A/ λ
C , B / λ
b, S /BS c, B/λ
b, A/λλ, S/λ
b, B/BB

a. Método de procesar palabras
t ( q, a a b b c, S)
t ( r, a b b c, S)
t ( q, b b c, AS)
t ( S, b c, S)
t ( S, c, BS)
t ( t, λ, S)
t ( t, λ, ) ACEPTADO

La palabra es aceptada cuando hay una sola S en el tope de la pila
t ( q, a b b c, S) esta transformación no existe.
t ( r, b b c, S) esta transformación no existe porlo tanto la palabra a b b c es restante.

Estado en que Q lee la b y en el tope de la pila hay una S entonces se la agrega B.
t ( q, b b c c, S)
t ( s, b c c, BS)
t ( s, c c, BBS)
t ( t, c, BS)
t ( S, c, BS)
t ( t, λ S)
t ( t, λ, )

Se acepta la palabra b b c c.
t ( q, a a b b b c c, S)
t ( r, a b b b c c, S)
t ( q, b b b c c, AS)
t ( S, b b c c, S)
t ( S, b c c, BS)
t ( S, c c,BBS)
t ( t, c, BS)
t ( t, λ, S)
t ( t, λ, )

a. Reconoce:
• Palabras que empiezan con un número par de as, seguido por b b terminan en c.
• cuando el numero as es cero, se da el mismo número.
• C es igual al número de bs menos el número de pares de as.

b. Conclusión:
• Las palabras a a b b c, b b c c y a a b b b c c son aceptadas.
• La palabra a b b c no es aceptada2. Definir el lenguaje reconocido por el siguiente autómata con pila

A: ([ a,b,c ], [S, A, B], [q, r, s, p ], q, S, f, Ø)
f(q, a, S)= [(r, S) ] f(s,b, A) = [(s, BS)]
f(q,b, S) = [(s, BS)] f(s,b, A) = [(s, λ)]
f(q, a, B) = [(r,A)] f(s,b,B) = [(s,BB)]
f(q, b,A)= [(s, λ)] f(s,c,B) = [(p, λ )]
f(r, a,S)= [(q, AS)] f(p,c,B) = [(p, λ )]
f(r, a,A)= [(q,AA)] f(p, λ,S) =[(p, λ )]

Por ser un Sextuplo, se tiene en cuenta:
∑= Alfabeto, Alfabeto de la Pila, ┌i = Variable inicial de la Pila,
Q= Estados, Qf: Estado Final, Qi: Estado inicial
Ø= Por ser vacio, quiere decir que el ultimo estado de la pila es el estado final de la transición
∑= [ a,b,c ], ┌ = [S, A, B], ┌i = S
Q= [q, r, s, p ], Qi= [q], Qf= p , Ahora miremos las transiciones

[pic]Definición formal:
L: [(aa)ⁿ b™cⁿ-™/n≥0; tm > 0]
L=Lenguaje

• Las palabras aabbc, bbcc y aabbcc son aceptadas
• La palabra abbc no es aceptada
• Reconoce palabras que empiezan con un numero par de a, seguido por bb y termina con c
• Cuando el numero a es cero entonces hay el mismo número de b y que de c
• El número de c es igual al número de bs menos el número de...
tracking img