Un AFDM... ...tiene menos estados que cualquier AFND equivalente. ...no puede tener estados inaccesibles. ...puede tener configuraciones de bloqueo. En un AFND una configuración... ...es una terna perteneciente a K x Σ* x K ...es un par perteneciente a K x Σ+ ...es un par perteneciente a K x Σ*. En un diagrama de estados de un AFND... ...los estados se representan mediante doble círculo. ...una etiqueta representa la subcadena consumida. ...puede haber más de un estado inicial. Un AFND transita en función de... ...un estado y un prefijo de una cadena. ...el próximo estado. ...el estado actual y el primer símbolo de la cadena. Si una GCL es recursiva por la izquierda, entonces... ...exista una GCL equivalente que no lo es. ...genera un lenguaje infinito. ...existe una gramática regular equivalente. Si M es un AFDM, entonces... ...todos los AFD equivalentes tienen menos estados que M. ...todos los AFD equivalentes tienen mayor o igual número de estados que M. ...existe un AFD equivalente con menos estados que M. Dado un lenguaje L ⊆ Σ* donde todas las cadenas de L son indistinguibles entre sí, entonces... L = Σ* o L = Ø L = Ø L = Σ*. El conjunto de configuraciones terminales de M = (K, Σ, δ, s, F) es: Infinito. ||F|| ||K||. Myhill - Nerode se utiliza para demostrar que un lenguaje: Es de tipo 2 y no 3. No es regular. Es de tipo 0. En un AFD... ...puede haber menos computaciones completas que cadenas aceptadas. ...tiene que haber tantas computaciones completas como cadenas aceptadas. ...puede haber más computaciones completas que cadenas aceptadas. L(AFD) = L(AFND) L.2 L(APND). Una gramática es propia si: No es recursiva y no tiene símbolos inútiles. No es recursiva ni ambigua ni tiene símbolos inútiles. No es recursiva izquierda y no tiene símbolos inútiles. Los APND... ...no pueden alcanzar estados de bloqueo. ...generan lenguajes de tipo 1. ...representan lenguajes de tipo 1. Si un AFD acepta un lenguaje finito L: ||L|| < ||K|| El estado inicial no es final. El AFD no tiene estados inaccesibles. El conjunto de configuraciones iniciales de un AFD = ||F|| ||K|| Es infinito. Una GCL es ambigua si: Existe una cadena del lenguaje que genera que es producto de más de un árbol de derivación. Todas las cadenas del lenguaje que genera son producto de más de un árbol de derivación. Todas las cadenas del lenguaje que genera son producto de infinitos árboles de derivación. Marca la afirmación falsa. Si L es regular entonces cumple CBR. Si L cumple CBCL entonces es de tipo 2. Si L es un lenguaje regular entonces cumple CBCL. Sea M un APND. Una computación terminada puede estar bloqueada. Si ninguna computación altera el contenido de la pila, el lenguaje que reconoce será regular. Si acepta la cadena vacía, el estado inicial también será final. .
