Autoatas de pila obj.5.3 y5.4

Solo disponible en BuenasTareas
  • Páginas : 2 (280 palabras )
  • Descarga(s) : 0
  • Publicado : 26 de mayo de 2011
Leer documento completo
Vista previa del texto
5. 3. Formalización de los AP

1.-Se define como un séxtuplo (K, (, (, Δ, s, F), donde:
K es un conjunto de estados
( es el alfabeto de entrada
( esel alfabeto de la pila
s ( K es el estado inicial
F ( K es un conjunto de estados finales,
Δ( (K × (( × (( ) × (K × (() es la relación de transición.
R=Autómata de pila

2- En ingles cuales son las operaciones típicas en las pilas
R= El “push” y el “pop”

3.- Menciona los casos particulares en quepueden ser vistas las transiciones del AP.
R=Meter la cadena a la pila (push) y Sacar los caracteres de la pila (pop)

4.- Si el AP realiza a siguientetransición ((p, u, β), (q, ( )) ( Δ, donde:
Estando en el estado p, consume u de la entrada;
Saca β de la pila;
Llega a un estado q;
Mete ( en la pila;¿Que es lo que describe?
R= El funcionamiento de los AP

5.- Es el método que reposa completamente en la noción de configuración
R= Lenguaje aceptadopor los AP.

6.- Las transiciones se definen como una relación o como una función.
R= Como una relación

7.- A las transiciones por ser una relación seles denomina
R= Autómatas no deterministas.

8.- Cuales son las propiedades que se cumplen en los autómatas de pila.
R= La cerradura reflexiva ytransitiva.

5.4. Relación entre AF y AP

9.- Nos dice que todo lenguaje aceptado por un AF es también aceptado por un AP.
R= Teorema Relación entre AF y AP10.- Los AP son una extensión de los AF
R= Verdadero

11.- Los autómatas finitos y los autómatas de pila aceptan el mismo lenguaje
R= Verdadero
tracking img