Montrer que deux expressions régulières sont équivalentes dans la théorie des automates sans utiliser de DFA

Question

J'ai essayé de prouver que deux regex sont équivalentes. Je sais que deux regex sont équivalentes si elles définissent le même langage. Mais je ne suis pas en mesure de le prouver sans utiliser les DFA.

Par exemple, j'ai le problème de prouver que les éléments suivants sont équivalents. Je connais ces deux définitions du langage ayant au moins un 'a' et un 'b'.

Le même est le cas avec ce qui suit.

(a + b)*ab(a +b)* + b*a* = (a + b)* 

Toute aide sera appréciée.

Merci

Answer 1

Vous devriez être en mesure de les prouver en utilisant les identités sur la diapositive 16 de this regex lecture. En particulier, je recommande l'utilisation intelligente de la dernière égalité de la 9ème identité là, R * = RR * + e. D'ailleurs, la première langue n'est pas précisément "au moins un" a "et un" b "". Par exemple, 'ba' n'est pas dans la langue, mais a au moins un 'a' et un 'b'.