سلام
هب این بخش اول داره می گه آیا راس ۱ به راس ۱ یال داره؟ راس ۱ آیا بهراس ۲ یال داره؟ راس یک آیا به راس ۳ یال داره ؟ و....
تا برسه به #
بعد همین سوالارو واسه راس ۲ می پرسه
و...
و تا این که همین سوالارو واسه راس n ام می پرسه

سنجش زده گزینه دو
و احتمالا اینجوری فرض کرده که وقتی درجه ی هر راس کمتر مساوی ۳ است ممن تو بخش اول باید ۰ تا یا یه دونه یا دوتا یا سه تا یک ببینم و همین طور تو بخش دوم و همین طور تو همه ی بخش ها
پس اگه بخواهیم راجع به dfa زبان صحبت کنم حالت شروع خودش یه حالت پایانیه از بیت اول شروع می کنم تا زمانی که صفر می بینم رشته قبوله اگه یه دونه ۱ یا دوتا یا سه تا ۱ دیدم قبوله اما اگهخ بیشتر شد می رم به حالت تله. بعد ادامه می دم تا به # برسم از اونجا دوباره تعداد ۱ ها رو حساب می کنم اگه ۰تا یا یه دونه یا ۲ تا یا ۳ تا ۱ بود قبوله در غیر اینصورت می رم به تله و ادامه می دم تا به # برسم و...

پس تو هر بخش یه حافظه ی محدود می خوام واسه شمردن ۱ ها.

اما از نظر خودم این جواب یه اشکال کوچیک داره اونم این که گراف رو حتما جهت دار فرض کرده که زبانش منظم شده
اگه گراف غیرجهتدار باشه اون وقت اگه مثلا راس ۱ به راس ۲ یال داره از اون طرف هم حتما باید راس ۲ به راس ۱ یال داشته باشه که یه حافظه ی پیچیده ای می خواد و در اون صورت زبان حساس به متن میشه اما اگه گراف و جهت دار فرض کنیم منظمه