Soit L un langage ordinaire et un ∈ Σ. Comment montrer que la langue L '= {uav | uv ∈ L} est-il aussi régulier? Wikipedia dit qu'une façon de prouver qu'il est de le ramener à un langage régulier, mais je ne comprends pas comment le faire dans ce cas. J'espère que quelqu'un peut aider.Comment montrer que si la langue L est régulière, alors L 'est-il régulier?
Il y a beaucoup de façons de le montrer. Je pense qu'un argument par lequel nous construisons un DFA est particulièrement facile à visualiser. Imaginez un DFA pour votre langue L. Appelons le M. Imaginez-le étendu sur une table sous forme de diagramme. Maintenant, imaginez faire une copie de M et l'étaler à côté de M sur la table. Appelez le M'.
maintenant - de M, ajouter une nouvelle transition de l'état q de M à l'état correspondant q' de M'. La transition est sur le symbole a.
Maintenant, considérons la machine agrégée dont l'état de démarrage est l'état de démarrage M et dont les états d'acceptation sont les états acceptants M'. Cette machine commence à accepter des chaînes dans L, puis accepte un a quelque part au milieu, puis continue d'accepter les chaînes dans L d'où elle s'est arrêtée. C'est le langage que nous visions et nous avons défini une NFA parfaitement raisonnable pour cela. Puisque toute langue acceptée par un NFA est régulière, notre langue est régulière.