Autómatas Finitos Unidad 3 Ante Chávez Pedro Edwin. No. de control: 10400336 Carrera: "I.S.C."
создатель Edwin Chávez
1. ESTADOS INACCESIBLES
1.1. Sea M=(Q,Σ,δ,q0,F) un AFD. Un estado q∈Q decimos que es inaccesible, si no existe ninguna palabra sobre el alfabeto de entrada que partiendo desde q0 llegue a q. Con símbolos será q inaccesible si δ(q ,ω) q ˆ ω , * ∀ ∈Σ 0 ≠ Los estados que no son inaccesibles decimos que son accesibles. Si eliminamos los estados inaccesibles y todas sus transiciones el AFD obtenido es equivalente al dado. 2. Autómatas Finitos 2.1 Autómatas Finitos Deterministas (AFD) © Inmaculada Luengo 25 Ejemplo: En el AFD M3 de la figura, el estado r es inaccesible por que no se puede alcanzar a partir del estado inicial
2. Ejemplos de un ADF:
2.1. La máquina M1 del ejemplo se representa con una tabla δ a b →p q r q p q *r r r Tabla 2.2. Autómata finito determinista M1.
2.2. DIAGRAMA
3. LENGUAJE ACEPTADO POR UN AFD.
3.1. Es el conjunto de todas las palabras aceptadas, es decir: L( ) M {ω : δ ˆ (q ,ω) F} * = ∈Σ 0 ∈
3.2. Ejemplos: El lenguaje de M2 son todas las cadenas de ceros y unos que empiezan por cero y tiene al menos un uno ( ) { } * L M = x1 y :x,y∈Σ
4. Definición
4.1. Es un modelo computacional que realiza cómputos en forma automática sobre una entrada para producir una salida.
4.2. es la siguiente: Un autómata finito es un vector de tres elementos M = (I,S,δ, F) donde I es el conjunto finito de entradas, S es el conjunto finito de estados (no vacío), δ es la función de transición de estados y F es el conjunto finito de estados finales (incluidos en S).
4.2.1. 1