Unidad 6: ALA Flashcards
Un ALA es un AFDB que puede grabar en su cinta,
Qué memoria tienen los ALA?
Memoria lineal finita de acceso aleatorio
(por el movimiento del cabezal)
Cual es el tipo de gramática reconocido por el ALA?
Tipo 1: gramáticas dependientes de contexto
Definición formal del ALA
ALA = ( Σ, Γ, Q, q0 , A, f )
cuyos componentes son:
- Σ = alfabeto de símbolos de entrada
- Γ = Σ ∪ {├, ┤} ∪ Ω = alfabeto de símbolos de cinta
- Q = conjunto finito y no vacío de estados posibles
- q0∈Q = estado inicial de funcionamiento
- A⊆Q = conjunto de estados de aceptación
- f : Q x Γ → Q x Γ x {I, D, N, P} = función de transición
Funcionamiento del ALA
- Lee un símbolo de entrada
- Graba un símbolo de salida
- Transita a un estado
- Mueve el cabezal (I, D, N, P)
- Repite 1,2,3,4 hasta ejecutar una instrucción de parada
- Decide si acepta o no una cadena
Consideraciones del funcionamiento del ALA
- No se puede mover el cabezal a la izquierda si se está leyendo el BOT o a la derecha si se está leyendo el EOT
- Puede quedar en un ciclo infinito y no terminar
- Para aceptar una cadena de entrada (asegurar al menos una lectura de la cadena), se detiene en el EOT
Cuando acepta cadenas el ALA reconocedora de lenguajes?
(Aplica para ALA y MT)
Una cadena de símbolos de entrada ( α∈Σ*) es reconocida por el ALA si pudo detenerse en un estado de aceptación con su cabezal de lectura ubicado en el EOT
Cuál es el lenguaje reconocidos por los ALA reconocedores de lenguajes?
El L(ALA) reconocido es
L = {α / (q0, α, 1) ├─* (qA, β, k), q0 ∈ Q, qA ∈ A, α ∈ ΣE*, β ∈ Γ+}
Cuál es la configuración instantánea del ALA?
Kt = (qt, ├ αt┤, n)
qt ∈ Q : estado actual en el instante t
αt∈Γ* : contenido de la cinta en el instante t
n ∈ N : posición del cabezal sobre la cinta, 0 ≤ n ≤ |αt|+1
Configuración inicial y final del ALA?
Configuración Inicial: K0 = (q0, ├ α0┤, 0)
*Configuración Final..: Kn = (qn, ├ αn┤, m) con ALA detenido
Si qn∈A y m=|αn |+1, ésta ES una configuración de aceptación.
Movimiento del ALA
(qt ,├ αt┤, nt) Ͱ (qt +1 ,├ αt +1 ┤, nt+1)
Movimiento desde la configuración inicial a la final
(qt ,├ αt┤, nt) Ͱ* (qt +k ,├ αt +k ┤, nt+k)
Cuando aceptan cadenas los ALA ejecutoras de procedimiento?
Una ALA acepta o reconoce una cadena de símbolos de entrada ( α∈Σ*) si puede moverse desde una configuración inicial a una final de aceptación y detenerse
(q0 ,├ α ┤, 0) Ͱ* (qf ,├ β ┤, |β|+1) con qf∈A
