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
 
(No se muestra una edición intermedia de otro usuario)
Línea 1: Línea 1:
Tomo Verónica escrito, eran dos ejercicios:
Tomo Verónica escrito a libro abierto, eran dos ejercicios:


==== Ej 1 ====
==== Ej 1 ====
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\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.
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 actual - 23:56 16 jun 2023

Tomo Verónica escrito a libro abierto, 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.
Obtenido de «https://www.cubawiki.com.ar/index.php?title=Final_del_13/06/23_(Teoría_de_Lenguajes)&oldid=15110»