Aplicando operaciones de Lenguajes regulares a AFND-ε #

Si tengo dos AFND-ε:

• \((Q^A,\Sigma,q^A_0,A^A,\delta^A)\) asociado al lenguaje \(L^A\)
• \((Q^B,\Sigma,q^B_0,A^B,\delta^B)\) asociado al lenguaje \(L^B\)

Entonces es posible construir los siguientes AFND-ε basados en la operaciones de los Lenguajes Regulares

• \(L^A+L^B\)
  \[ \left( Q^A \bigcup Q^B \bigcup \{q^{union}_0\}),\Sigma,q^{union}_0,A^A \bigcup A^B, \delta^A \bigcup \delta^B \bigcup \{(q^{union}_0,\varepsilon) \rightarrow \{q^A_0, q^B_0\}\} \right) \]
• \(L^AL^B\)
  \[ \left( Q^A \bigcup Q^B),\Sigma,q^A_0,A^A \bigcup A^B, \delta^A \bigcup \delta^B \bigcup \{(q,\varepsilon) \rightarrow \{q^B_0\} | q \in A^A\} \right) \]
• \(L^*\)
  \[ \left(Q,\Sigma,q^{cerradura}_0,A\bigcup \{q^{cerradura}_f\}, \delta \bigcup \{ (q^{cerradura}_0,\varepsilon) \rightarrow \{q_0\}, (q^{cerradura}_0,\varepsilon) \rightarrow \{q^{cerradura}_f\}, (q^{cerradura}_f,\varepsilon) \rightarrow \{q^{cerradura}_0\}\} \bigcup \{(q,\varepsilon) \rightarrow \{q^{cerradura}_f \} | q \in A\} \right) \]

Ejemplo #

Supongamos los lenguajes \(L_1: 0^*1 \) y \(L_2: 10^* \)

Con sus autómatas gráficos

Si aplicamos cada una de las operaciones obtenemos:

• Unión \(L_1 \bigcup L_2 \)

• Concatenación \(L_1 L_2 \)

• Cerradura \(L_1^* \)

Ejemplo de AFND-ε a ER #

Dado a que tenemos una forma de hacer las operaciones de lenguajes regulares con AFND-ε, podemos pensar en transformar un ER a un AFND, partiendo de AF básicos e ir aplicando las operaciones

• \((a^*ba^*ba^*)+a^*\)