Edición de «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 <math>\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)</math>. 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 <math>c</math> tal que para todo <math>A,B\in V_N, \alpha\in(V_N\cup V_T)^* </math> si <math>A\rightarrow^* B\alpha</math> entonces <math>A\rightarrow^i B\alpha</math> (la derivación tiene <math>i</math> pasos) con <math>i \leq c</math> y <math>c</math> constante.

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