یعنی چی؟ منظورتون اینه که چطور میشه dfa یک زبان را رسم کرد؟

(۲۸ آبان ۱۳۹۰ ۰۷:۵۲ ب.ظ)f.b نوشته شده توسط:  یک سوال ساده:چطور میشه با dfa یک رشته رو پیاده سازی کرد و برعکسش

من قبلا این درس رو نگذروندم و همین اول کاری به بن بست رسیدم ممنون میشم راهنمایی کنید

خوب یک نمونه رو می ذاشتید تا بر اساس اون بشه توضیح داد.
یک سوالی رو که متوجه نشدید!

-dfa برای زبان زیر طراحی کنید؟(تمرین ۵ لینز)

{*{L={ab^5wb^4: w є {a,b


-زبانی را که توسط اتاماتای زیر پذیرفته می شود؟ (تمرین ۶ فصل ۲ لینز)(ببخشید شکل رو با کیفیت نتونستم بذارم)


(من کلا با روش dfa اشنا نیستم وگرنه حل تمرین کتاب رو دارم،ممنون میشم هر کدوم رو مرحله به مرحله توضیح بدید )

خوب با اجازه کنکوری های محترم من شروع می کنم بقیه توضیحات رو کامل کنند

در مورد dfa باید در هر حالت به ازا تمامی متغییرهای موجود در سیگما یک و فقط یک یال خروجی داشته باشیم و چون در اینجا سیگما دو تا متغییر a,b رو داره پس از هر حالت باید دقیقا دو تا یال یکی با a و یکی با b خارج شه.
از اون جایی که اولین متغییر ظاهر شده a هست پس با یه یال از حالت شروع با برچسب a خارج می شیم و به حالت دوم میریم. بعد از اون باید دقیقا ۵ تا b داشته باشیم پس از حالت دوم با یالی با برچسب b به حالت سوم و از اون هم به همین صورت تا ۵ تا یال با برچسب b داشته باشیم.
بعد از اون باید w رو تولید کنیم یعنی اجازه بدیم هر رشته ای با هر طولی از a,b تولید بشه و این رشته می تونه لاندا هم باشه یعنی هیچ متغیری رو شامل نشه

بنابراین در حالتی که فعلا هستیم که یه a و ۵ تا b قبلش هست یک دور میذلریم و روی ان a,b را قرار میدیم بدین ترتیب اگه اصلا دور رو نزنیم لاندا رو داریم و می تونیم هر تعداد این دور رو با هر متغییری داشته باشیم بعد از اون باید دوباره ۴ تا b تولید کنیم مثل قبل و حالت اخر ور به عنوان حالت پایانی در نظر می گیریم.

خوب حالا باید ببینیم هر کدوم از این حالات کدوم یک از متغییرها رو نداره مثلا حالت ۱ یال خروجی با متغییر b نداره ولی اگه با این برچسب به یالهایی که قبلا ایجاد کردیم بره اونوقت زبان رشته هایی رو که با b شروع می شن رو هم شامل می شه واسه حل این مشکل یه حالت جدید در نظر می گیریم و با b به اون میریم این کار رو واسه بقیه حالات هم تکرار می کنیم مثلا از حالت ۲ با یالی با برچسب a به همون حالت trap میریم.

امیدوارم درست گفته باشم اگه جاییش غلط بود دوستان اصلاح کنند ممنون

واقعا بابت راهنمایی خوبتون و وقتی که گذاشتید ممنونم. یه سوال بعدازاینکه a و ۵ تا b تولید شد برای حالت چرخش a b را باید دقیقا در حالت بعد قرار دهیم؟
چون در حل لینز یک حالت جدید برای خروجی های که گفتید در پایان باید اضافه کنیم قرار داده و حالت چرخش را روی ان گذاشته

و اگر یک راهنمایی کنید که اگر به ما شکل را بدهد و زبان تولیدی را بخاهد به چه شکل باید عمل کنیم
تشکر

خواهش می کنم
در حالت بعد نه در همان حالت که با اخرین b بهش وارد شدید و بعد از اون با b به حالت بعد میرید.
اون حالت اخر که اضافه می کنیم از اون جایی که باز هم در dfa هستیم پس باید به ازا هر متفییر یه یال داشته باشه و اون جالت اخر هم از این قانون مستثنی نیست ولی خوب از اون جایی که خودش یه حالت دام تله هست پس می تونیم به ازا هر دو تا متغییر به خودش بره نمی دونم خوب توضیح دادم یا نه در واقع اون دوری که روی حالت تله هست برای تکمیل dfa است و ربطی به w که تو رشته گفته نداره

اگه شکل هم بدن باید عکس این کار ور انجام بدید یعنی یا این که اول قواعد رو از روش بنویسید مثلا از s با a رفته به حالت A پس یه قانون در گرامر به شکل s -->aA می نویسیم و به این صورت زبان رو از روش می نویسیم . البته پیدا کردن زبان و کلا این موارد نیاز به حل مساله زیاد و دیدن مسائل مختلف داره سعی کنید تا حد امکان باهاش کلنجار برید و هر چی رو که می تونید حل کنید بعد درستش رو چک کنید

توضیحاتون عالی بود
الان که چند تا رو حل کردم خوب بود
بازم تشکر