Diferencia entre revisiones de «Final del 13/06/23 (Teoría de Lenguajes)»
De Cuba-Wiki
(Página creada con «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…») |
Sin resumen de edición |
||
| Línea 5: | Línea 5: | ||
==== Ej 2 ==== | ==== 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\ | 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_L^* B\alpha</math> entonces <math>A\rightarrow_L^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. | : La cota tiene que ser ajustada, no alcanza con dar la cota teórica vista en clase. | ||
Revisión del 00:12 15 jun 2023
Tomo Verónica escrito, eran dos ejercicios:
Ej 1
Un autómata es co-determinístico si no ocurre que . 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 tal que para todo si entonces (la derivación tiene pasos) con y constante.
- La cota tiene que ser ajustada, no alcanza con dar la cota teórica vista en clase.
