Cierre en idiomas regulares

Question

a) Deje que $ l $ sea un idioma regular.Según el teorema hay un DFA que acepta el idioma.

Describe en breve cómo cambiar el DFA a NFA que acepta $ l ^ r $ , donde r está invertido.

No hay necesidad de escribir cómo construir formal o prueba o corrección.

b) Verdadero o Falso: Si $ l $ no es regular entonces $ l ^ r $ no es regular

Mi solución:

a) En primer lugar, debido a que queremos revertir el estado de aceptación se convertiría en el inicio y los estados de rechazo se volverán a aceptar, también cambiar la dirección de los bordes al lado opositor. Pero cuando se trata de cambiarlo a NFA, estoy un poco atascado.

b) Creo que es cierto, ya que no importa si se invierte si es habitual, por supuesto, $ l ^ r $ será regular también.

¿Es este el camino para A y B?

Answer 1

a)

En primer lugar, debido a que queremos revertir el estado de aceptación se convertiría en el inicio y los estados rechazadores se volverán a aceptar, también cambiará la dirección de los bordes al lado opositor.

ya estás allí. ¿Qué sucede si tiene varios estados de aceptación en el DFA original? Ahí es donde necesitas capacidades de NFA para convertirlas.

Aquí hay un spoiler en caso de que desee verificar su respuesta: Diseñar un DFA y el reverso en Computerscience.se .

b)

Su respuesta es cierta, aunque es posible que desee expresarlo un poco más detenidamente. Queremos probar "Si $ l $ no es regular, $ l ^ r $ no es regular" . Así que permita que $ l $ no sea regular. Si $ l ^ r $ fue regular, también lo fueron $ (l ^ r) ^ r= l $ , que es una contradicción. Por lo tanto, $ l ^ r $ no es regular.