Un NFA accepte-t-il une chaîne vide si et seulement si son état de départ est un état final? Est-ce vrai?
S'il vous plaît expliquer pourquoi.
Cette question est liée à Automates et NFA et DFAS.
3 Réponses :
Ceci est faux. Considérons une NFA à deux états avec un état initial non acceptant conduisant à un état d'acceptation au moyen d'une transition lambda- (ou epsilon- ou vide). La chaîne vide est acceptée par cette NFA en parcourant la transition, mais l'état initial est non-acceptant.
Si la réclamation était à propos de DFAS, il serait vrai que les transitions Lambda- (ou EPSilon ou vide) ne seraient pas disponibles.
Oui, c'est vrai. Lorsque l'état de démarrage devient l'état final, alors sans lire une chaîne, vous avez atteint l'état final. La chaîne acceptée est donc vide. Reportez-vous à https://www.udemy.com/course/introduction- to-théorie-des-calculations /
oui c'est vrai. Par défaut, NFA signifie NFA sans transition EPSILON. S'il s'agit d'un Epsilon NFA (NFA qui peut changer d'état sans consommer le symbole d'entrée), la réponse est fausse.
Cela semble être un meilleur ajustement pour cs.stackexchange.com.