Que faisons-nous d'un NFA avec transition lambda?

Question

J'ai l'automate suivant. Je suis censé comprendre l'utilisation de la transition vide à travers elle.

Je pense que l'expression régulière de cet automate est la suivante: 0 * 1 * 2 *

Je veux juste savoir ce que cet automate nous permet de faire? en d'autres termes, quelle est l'utilisation de la transition vide dans ce cas?

Answer 1

Je pense que tu veux savoir sur la différence entre ce ..

et ce

différence est d'abord la première chaîne acceptent automate de 0,1 et 2 quoi que ce soit ... alors que le second automate accepte la chaîne de 0,1 et 2 de ... 0 suivi de 1,1 suivi de 2 .... ex. il accepte 012,001122,0012,0112 etc. il n'acceptera pas 102,201,0121,0120,0011221.

transitions si vide rendent agréable et facile ...

Answer 2

Vous avez raison, votre automate décrit 0 * 1 * 2 *. q est où il gère une série (éventuellement vide) de 0s. q est l'endroit où il gère une série (éventuellement vide) de 1s. En ayant une transition de vide q -q , aucun caractère est nécessaire entre les 0 et les 1.

La transition vide ne vous permet pas de décrire une langue qui ne pourrait pas être décrite sans elle. Cependant, essayez simplement de retravailler votre automate pour ne pas utiliser de transitions vides. C'est possible, mais cela nécessite plus de transitions, cela nécessite de faire de chaque état un état final, et quand vous avez terminé, vous verrez qu'il est plus difficile de dire quelle langue est décrite. Par conséquent, l'utilisation de transitions vides rend leur automate plus facile à comprendre.