Encerramento em idiomas regulares

Question

a) Deixe $ l $ ser uma linguagem regular.De acordo com o teorema, há um DFA que aceita a linguagem.

Descreva em breve como alterar o DFA para NFA que aceita $ l ^ R $ , onde r é invertido.

Não há necessidade de escrever como construir formalmente ou prova ou correção.

b) true ou falso: se $ l $ não é regular, então $ l ^ r $ não é regular

minha solução:

Em primeiro lugar, porque queremos reverter, o estado de aceitação se tornará o começo e os estados de rejeição se aceitarão, também mudará a direção das bordas para o lado do oposição. mas quando se trata de mudá-lo para NFA im um pouco preso.

B) Eu acho que é verdade, já que não importa se revertiu se é regular, então, é claro, $ l ^ r $ será regular também.

é este o caminho para A e B?

Answer 1

a)

.

Primeiro de tudo, porque queremos inverter o estado de aceitação se tornará o começo e os estados de rejeição se aceitarão, também mudará a direção das bordas para o lado do oposição.

Você está quase lá. O que acontece se você tem vários estados de aceitação no DFA original? É aí que você precisa de recursos do NFA para convertê-los.

Aqui está um spoiler no caso de você querer verificar sua resposta: Projetando um DFA e o reverso do ComputersCience.se .

b)

Sua resposta é verdadeira, embora você possa querer frase um pouco mais com mais cuidado. Queremos provar "se $ l $ não é regular, $ l ^ r $ não é regular" . Então, deixe $ l $ não seja regular. Se $ l ^ R $ eram regulares, assim foram $ (l ^ r) ^ r= l $ , que é uma contradição. Portanto, $ l ^ r $ não é regular.