اگر M یک ماشین متناهی حالت قطعی (DFA) باشد میگوییم دو رشته x و y نسبتبه M با هم معادلاند، هرگاه (s,y)xrightarrow _M q ⇔ (s,x)xrightarrow _M q, که در آن s حالت شروع و q یک حالت دلخواه ماشین است. کلاسهای همارزی رشتهها نسبتبه ماشین روبهرو کدام است؟

[ε] , [a] , [ab] , [aab] , [b]

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

نظریه زبان‌ها و ماشین‌هامتوسطعبارت‌های منظم و زبان‌های منظم

اهمیت

۰/۵

اگر $M$ یک ماشین متناهی حالت قطعی (DFA) باشد می‌گوییم دو رشته $x$ و $y$ نسبت‌به $M$ با هم معادل‌اند، هرگاه $(s,y)\xrightarrow{\;*\;}_{M} q \iff (s,x)\xrightarrow{\;*\;}_{M} q,$ که در آن $s$ حالت شروع و $q$ یک حالت دلخواه ماشین است. کلاس‌های هم‌ارزی رشته‌ها نسبت‌به ماشین روبه‌رو کدام است؟

#dfa#myhill-nerode#string-equivalence#equivalence-classes#state-counting