Fermeture sur les langues ordinaires

Question

a) laissez $ l $ être une langue régulière.Selon le théorème, il y a une DFA qui accepte la langue.

décrire brièvement comment changer la DFA en NFA qui accepte $ l ^ r $ , où r est inverse.

Il n'est pas nécessaire d'écrire comment construire formellement ou preuve ou correction.

b) true ou faux: si $ l $ n'est pas régulier, alors $ l ^ r $ n'est pas régulier

Ma solution:

a) Tout d'abord parce que nous voulons inverser l'État d'acceptation deviendrait le début et que les États rejetants deviendront accepter, modifient également la direction des bords au côté opposé. Mais quand il s'agit de le changer en NFA im un peu coincé.

B) Je pense que c'est vrai depuis que cela n'a pas d'importance s'il est inversé si son courant normal alors bien sûr $ l ^ r $ sera aussi régulier.

Est-ce la voie à suivre pour A et B?

Answer 1

a)

Tout d'abord parce que nous voulons inverser l'état d'acceptation deviendrait le début et que les États rejetants deviendront accepter, modifient également la direction des bords au côté opposé.

Vous êtes presque là. Que se passe-t-il si vous avez plusieurs états acceptés dans le DFA d'origine? C'est là que vous avez besoin de capacités NFA pour les convertir.

Voici un spoiler au cas où vous voudriez vérifier votre réponse: Conception d'une DFA et l'inverse de celui-ci sur Computerscience.se .

b)

Votre réponse est vraie, bien que vous souhaitiez la former un peu plus attentivement. Nous voulons prouver "si $ l $ n'est pas régulier, $ l ^ r $ n'est pas régulier" . Alors laissez $ l $ ne peut pas être régulier. Si $ l ^ r $ était régulier, de même que $ (l ^ r) ^ r= l $ , qui est une contradiction. Par conséquent, $ l ^ r $ n'est pas régulier.