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

‏DFA زیر، بر $\Sigma = \{a, b, c\}$ مفروض است. اگر $t$ تعداد رشته‌های به طول ۳ یا کمتر باشد که توسط این DFA پذیرفته می‌شود، کدام مورد درخصوص $t$ درست است؟

خودکار دارای حالت‌های $q_1, q_2, q_3, q_4$ است. حالت شروع $q_1$ است. حالت‌های پذیرنده $q_1$، $q_2$، $q_3$ (دایره دوگانه) هستند؛ $q_4$ پذیرنده نیست (حالت تله). گذارها:

• $q_1 \xrightarrow{a,c} q_1$ (حلقه خودی)
• $q_1 \xrightarrow{b} q_2$
• $q_2 \xrightarrow{a,c} q_1$
• $q_2 \xrightarrow{b} q_3$
• $q_3 \xrightarrow{a,b,c} q_4$
• $q_4 \xrightarrow{a,b,c} q_4$ (حلقه خودی)