Final del 13/06/23 (Teoría de Lenguajes)

Tomo Verónica escrito, eran dos ejercicios:

Ej 1

Un autómata es co-determinístico si no ocurre que $\exists q_{1},q_{2},q_{3}\in Q,a\in \Sigma \ \backslash \ q_{1}\in \delta (q_{2},a)\land q_{1}\in \delta (q_{3},a)$. Dar un algoritmo que dado un autómata M, construya un autómata co-determinístico N tal que L(M)=L(N) y dar su complejidad.

Ej 2

Dada G una GLC sin producciones lambda y no recursiva a izquierda, dar una cota ajustada $c$ tal que para todo $A,B\in V_{N},\alpha \in (V_{N}\cup V_{T})^{*}$ si $A\rightarrow ^{*}B\alpha$ entonces $A\rightarrow ^{i}B\alpha$ (la derivación tiene $i$ pasos) con $i\leq c$ y $c$ constante.

La cota tiene que ser ajustada, no alcanza con dar la cota teórica vista en clase.