(۳۱ فروردین ۱۳۹۶ ۰۲:۱۰ ق.ظ)msour44 نوشته شده توسط:  سلام
در زبان اول که داریم $(0^{\ast}1\: (10)^{\ast}\: (00^{\ast}1\: (10)^{\ast})^{\ast})$ اولین ۰ استار یعنی اینکه می توانیم به جای ان رشته تهی(انتخاب نشدن ۰) یا۰ یا ۰۰ یا ۰۰۰ یا... قرار دهیم و بعد حتما ۱ داریم و بعد(۱۰) استار داریم باز یعنی رشته تهی (انتخاب نشدن) یا ۱۰ یا۱۰۱۰ یا...در واقع در این مرحله یا ۱۰ انتخاب نمی شود یا با هم به صورت ۱۰ یا۱۰۱۰ ویا ۱۰۱۰۱۰و...بعد$(00^{\ast}\: 1\: (10)^{\ast}\: \: )^{\ast}$ داریم که باز کل این پرانتز می تواند تهی باشد یا $(00^{\ast}\: 1\: (10)^{\ast}\: \: )^{ }$ ویا$(00^{\ast}\: 1\: (10)^{\ast}\: \: )(00^{\ast}\: 1\: (10)^{\ast}\: \: )$ ویا یعنی چندین بار می تواند با خودش الحاق شود حالا هر کدام از این حالت ها برای این پرانتز بزرگ انتخاب شد داخل اون هم باز دو تا استار داریم یکی برای ۰ و دیگری برای ۱۰ که حالت های انها هم مثل ۰ و ۱۰ ابتدای عبارت است.
منظور از + هم یعنی یا مثلا ۰+۱ یعنی یا رشته ۰ یا ۱ را می توانیم انتخاب کنیم ویا (۰+۱)استار یعنی تمام رشته ای تولیدی ممکن با الفبای ۰ و۱ در واقع چون استار داریم یا به قول شما انتخاب نمی شود (رشته تهی ) یا (۰+۱) یا (۰+۱)(۰+۱) که رشته ۰۰ و ۰۱و ۱۰ و۱۱ را تولید می کند به همین ترتیب می توانیم ۳ تا از این پرانتز ها را کنارهم الحاق کنیم و بیشتر
نکته ای که در بار این تست می توان به ان اشاره کرد یافتن زبان M است که برای اینکار حالت دوم را حذف میکنیم که باعث ایجاد حلقه ای با برچسب۱۰ روی حالت $q_1$ می شود.در حالت کلی با دو حالت شروع a و پدیرش b که $r_1$ روی حلقه a و $r_2$ روی یال از a به b و $r_3$ روی یال از b به a و $r_4$ روی حلقه b باشد زبان ماشین برابر با
$r_1^{\ast}\: r_2\: (r_4\: +\: r_3\: r_1^{\ast}\: r_2)^{\ast}$
حالا در ماشین تست که گفتیم حالت $q_2$ را حذف کردیم اگر مقدار برچسب ها را متناسب با $r$ ها قرار دهیم زبان سوم تست بدست می اید$(0^{\ast}\: 1\: (10\: +\: 00^{\ast}1)^{\ast}\: \: )$ و اگر از $(a+b)^{\ast}=a^{\ast}(b\: a^{\ast})^{\ast}$ استفاده کنیم زبان اول تست حاصل می شود.$L_1=L_3=L(M)$
همچنین اگر زبان دوم را روی M دنبال کنیم متوجه می شویم که به جز اخرین یک ما در نهایت در حالت شروع باقی میمانیم و با اخرین یک به حالت پذیرش می رویم این یعنی اینکه M تمام رشته های زبان دوم را شامل می شود ولی زبان دوم فقط رشته های منتهی به یک را دارد درحالی که M رشته های منتهی به ۰ هم دارد یعنی زبان دوم زیرمجموعه زبان M است همچنین چنین نتیجه ای برای زبان چهارم می توان گرفت یعنی با دنبال کردن زبان چهارم می توان نتیجه گرفت تمام رشته های زبان چهارم توسط M تولید می شود یعنی زیر مجموعه بودن ولی نه برعکس چون رشته ۱۱۰۰۱۰۱ توسط M پذیرفته می شود ولی توسط زبان چهارم خیر با این اوصاف جواب گزینه ۳