Final del 20/12/23 (Teoría de Lenguajes)

Ej 1

Demostrar Verdadero o Falso

a) Si $M=(Q,\Sigma ,\delta ,q_{0},F)$ es AFD completo y mínimo entonces ${\overline {M}}=(Q,\Sigma ,\delta ,q_{0},Q\backslash F)$ es AFD completo y mínimo también.

b) Sea $\Sigma ={0,1}$.

Para cada AFD $M=(Q,\Sigma ,\delta ,q_{0},F)$ con un estado trampa $q_{t}\in Q$ y completo sea AFD $M'=(Q',\Sigma ,\delta ',q_{0}',F)$ tal que

• $Q'=Q\cup \{q_{0}'\}$,

• $\delta '(q,\sigma )=\delta (q,\sigma )$, para todo $q\in Q$ y $\sigma \in \Sigma$,

• $\delta '(q_{0}',0)=q_{0}$,

• $\delta '(q_{0}',1)=q_{t}$.

Si $M$ es mínimo entonces $M'$ también.

Ej 2

Un autómata contador es un autómata de pila con un alfabeto de pila de solamente dos símbolos, el inicial (que representa el cero), y el que se usa para contar en un unario. Cada transición incrementa el contador en uno, o lo decrementa en uno, o lo deja igual. En cada transición se puede consultar si el contador es cero o no (tope de la pila).

Demostrar Verdadero o Falso

a) Si un lenguaje es reconodible por un autómata contador entonces el lenguaje complemento también.

b) Si dos lenguajes $L_{A}$ y $L_{B}$ reconocibles por autómatas contadores entonces el lenguaje de su unión $L_{A}\cup L_{B}$ también.

c) Si dos lenguajes $L_{A}$ y $L_{B}$ reconocibles por autómatas contadores entonces el lenguaje de su intersección $L_{A}\cap L_{B}$ también.