[Teórico] Lenguajes regulares - consultas varias

[Teórico] Lenguajes regulares - consultas varias

de Marianela Gissel Rodriguez Guerra -
Número de respuestas: 4

Buenas noches! 

Vengo con otro combo de preguntas que capaz son básicas pero haciendo ejercicios de parcial me entraron dudas de si son válidas para usar en los mismos:

1) para afirmar que un lenguaje es regular, es válido dar un autómata afd, afnd o afnd-e? O sea, es indistinto para dar la solución al problema? 

2) Si nos pidieran la ER de algún autómata, podría aplicar Kleene directamente? O solo se le puede calcular la ER  si el autómata es un afd?

3) Cualquiera de estos autómatas: afd, afnd o afnd-e puede tener más de un estado final? 

4) Puede un estado final coincidir con un inicial? 

Saludos! 


En respuesta a Marianela Gissel Rodriguez Guerra

Re: [Teórico] Lenguajes regulares - consultas varias

de Diego Garat -

hola:

1 - sí. para afirmar que un lenguaje es regular, con dar cualquiera de los modelos que mencionás, es suficiente (e indistinto). hay más maneras también de probarlo (dar una e.r. y propiedades,  por ejemplo)

2 - se vio la demo para autómatas deterministas, pero se podría aplicar para AFND. con transiciones épsilon, también, aunque ahí ya no valdría el tema de unicidad (aunque si calculás la solución mínima...)

3 - sí, claro. todos los que quieras.

4 - efectivamente. es más, es condición necesaria y suficiente que q0 sea final para aceptar a la tira vacía en un AFND... (fijate, por ejemplo, qué sucede en el algoritmo de AFND-éps -> AFND que quita las transiciones épsilon)

saludos,

d.-



En respuesta a Diego Garat

Re: [Teórico] Lenguajes regulares - consultas varias

de Nicolas Gerardo Perez Alano -
Agrego una consulta mas:
Un lenguaje vació es regular? Porque? Existe una ER para el ?
En respuesta a Nicolas Gerardo Perez Alano

Re: [Teórico] Lenguajes regulares - consultas varias

de Santiago Gongora -

Buen día Nicolás,

sí, efectivamente. En las diapositivas que subió Juanjo al EVA se ve que es uno de los pasos de su definición inductiva:



Cualquier consulta a las órdenes :D

Santi

En respuesta a Diego Garat

Re: [Teórico] Lenguajes regulares - consultas varias

de Marianela Gissel Rodriguez Guerra -
Muchas gracias Diego :)

Quedaron clarisimas todas las respuestas. En la 2 en particular, entonces no queda otra que trabajar sobre un AFD y luego calcular la ER, esa duda estaba atrás de mi pregunta y ahora quedó clarísimo (porque pensé que obtener la ER ya se lograba "leyendo" directo cualquier autómata, pero ya veo que no era tan directo).

Saludos.