سوال ۹۰ کنکور ارشد علوم کامپیوتر ۱۴۰۴

فرض کنید زبان L، زبان dfa زیر باشد:

(در نمودار: حالت آغازین $q_1$ است؛ گذارها: $q_1\xrightarrow{a}q_2$، $q_1\xrightarrow{b}q_3$، $q_2\xrightarrow{a}q_2$، $q_2\xrightarrow{b}q_3$، $q_3\xrightarrow{a}q_4$، $q_3\xrightarrow{b}q_3$، $q_4\xrightarrow{a}q_2$، $q_4\xrightarrow{b}q_3$؛ یعنی با هر $b$ به $q_3$ می‌رویم. تنها حالت پذیرنده $q_3$ است.)

فرض کنیم $w \in L$ رشته‌ای از زبان L با طول حداقل ۱۴۰۳ باشد. کدام مورد، همواره درست است؟

الف ـ اگر w با a شروع شود رشته $w\,a^{۱۴۰۳}$ حتماً در L خواهد بود.

ب ـ اگر w با b شروع شود رشته $w\,b^{۱۴۰۳}$ حتماً در L خواهد بود.