فرض کنید یک مجموعه متناهی مانند ∅ ≠ B که شامل اعداد صحیح است داده شده. حال هدف طراحی یک DFA روی الفبای ۰,۱ است بهطوری که هر رشته مانند x = x_۱,…,x_n که به این DFA داده میشود در صورتی پذیرش میگیرد که: ∀ i ∈ B x = x_۱,…,x_n x_i = ۰ تعداد stateهای این ماشین در حالت مینیمال کدام است؟ ( Max(B) به مفهوم ماکزیممترین عضو مجموعه B است.)

سوال ۸۷ کنکور ارشد علوم کامپیوتر ۱۳۹۷

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

اهمیت

۰/۵

فرض کنید یک مجموعه متناهی مانند $\varnothing \neq B$ که شامل اعداد صحیح است داده شده. حال هدف طراحی یک DFA روی الفبای ۰,۱ است به‌طوری که هر رشته مانند $x = x_۱,\ldots,x_n$ که به این DFA داده می‌شود در صورتی پذیرش می‌گیرد که:

$\forall\, i \in B \quad x = x_۱,\ldots,x_n \quad x_i = ۰$

تعداد state‌های این ماشین در حالت مینیمال کدام است؟ ( $\mathrm{Max}(B)$ به مفهوم ماکزیمم‌ترین عضو مجموعه $B$ است.)

#minimal-dfa#state-count#myhill-nerode#dfa#positional-constraint#finite-automata