Autómatas Finitos y Lenguajes Regulares: Conceptos Clave y Propiedades

• Para q ∈ Q y se define: D(q) = {p / hay un dqap de transición marcado} • d(Q) es la colección de estados q "continuar" aq directamente a través de la transición marcada con • ejemplo

Transiciones Épsilon en Autómatas Finitos No Deterministas (AFN)

AFN con transiciones Épsilon:

1. Calcular el cierre Épsilon de todos los estados.
2. Dibujar el autómata sin transiciones iniciales.
3. Poner las transiciones: (q) = - C [D (- C (q))] = (p₁, p₂,..., p_n). Flechas de Dibujo con el símbolo en q hasta que todos los p_i (i = 1, ..., n) -> Esto se hace para todos los estados (y en cada estado se hace con todos los símbolos).

Expresiones Regulares y Autómatas Finitos

ER > AF:

Caso base:

1. a ∈:

Casos recursivos: Tener la rys ER -> L(r) = L(M1), donde M1 = (Q₁, Σ₁, δ₁, q₀₁, F₁), L(s) = L(m2) donde m2 = (Q₂, Σ₂, δ₂, q₀₂, H₂)

Conversión de Autómatas Finitos a Expresiones Regulares

AF -> ER:

Todos los idiomas aceptados por un AF en el alfabeto y la unidad contiene los idiomas (a) para todo a ∈. Este conjunto se cierra en relación con el matrimonio, reunión y estrellas.

Teorema de Kleene: Cada lenguaje regular es aceptado por un FA y del lenguaje aceptado por un AF es también otro idioma.

Considere la posibilidad de regular el año fiscal M = (Q, P, K) y QS supongas q = q₀ es el estado inicial. Para cualquier estado q_i, es: a_i = {w ∈ Σ* / (q_i, w) ∈ f} // Este es el a_i es lo q se acepta en q_i // Tenga en cuenta que q₀ = L(M) // Si la TB advierto que es posible q = q_i // Si qi ∈ F, entonces se cultiva q ∈ q_i

El lema de las Ardenas: X = A • X ∪ B donde A tiene una solución única, X = A^*B

Propiedades de los Lenguajes Regulares

¿Cuándo una lengua L es regular?

1. Si L es finito, L es regular.
2. Cuando hay una ER tal que R L(r) = L.
3. Si existe un AF M tal que L(M) = L.

NOTA: Para probar el idioma q es regular -> construir el robot para dar con la expresión regular // Para demostrar que una lengua no es regular el uso del lema de bombeo.

Supongamos q con un lenguaje ordinario: AFD M = (Q, q₀, F) // L(M) es infinito (q nos dijo que no habrá retroalimentación d Cierro el bloqueo + *) // w = a₁ a₂ .... a_n+1 // w ∈ L(m) // |w| = n +1> n / q₀, q₁, ....., q_n+1 d camino de aceptación, los Estados n +1, luego se repite en algunos estados de Q n / w = a₁, a₂ .... a_n+1 ∈ L(m) / W^'= a₁ a₂ .... a_k a_j a₁ a_k+2 ...... a_n a_n+1 ∈ L(m)

Teorema del Bombeo: Sea L un lenguaje regular infinito, entonces existe una constante k asociadas con la lengua, de modo que, si w es una cadena de L cuya longitud es mayor o igual a W (|w| >= k), w puede ser descompuesto la Forma W = UVX donde: |v| >= 1, |uv| <= k, y todas las Cadenas d la forma uvⁱx ∈ L, para todo i >= 0 // El lema de la bomba tiene una propiedad q debe tener todo el lenguaje ordinario y nos da una forma d determinar si una lengua no es regular. Para demostrarlo demostrado para cualquier valor q n lo suficientemente grande, si se, a lo menos una longitud de cadena en la mayoría d q deja de ser bombeado • El lema de la bomba no dice si una lengua es regular, nos dice que si no es encontrar un contraejemplo .

Teorema: M es un AF con los Estados k:

1. L(M) <=> M acepta una cadena de longitud menor que d QK
2. L(m) infinito <=> M acepta una longitud de cadena d n, donde k <= n <2k // En la práctica es más fácil dado un autómata M:

1. Se puede eliminar todos los estados en el q hay un paso a un estado final. Si elimina el estado inicial, entonces L (M) =
2. Sumideros abolido. No. Sin embargo, hay ciclos (bucles), entonces L(M) es infinito

Para hallar el complemento de un lenguaje regular (tb q es normal), la AFD puede construir el idioma original y luego hallar el de otros estados su final, cambiando el final y viceversa.