تمامی رشته موجود در [tex]L((a b)^{\ast}b(a ab)^{\ast})[/tex] با طول کمتر از ۴ را پیدا کنید .
ممنون می شم یکی از دوستان با راه حل این مسئله رو برام توضیح بده ، با تشکر
سلام و سال نو مبارک.
عبارت منظم : [tex](a b)^∗b(a ab)^∗[/tex]
رشته های به طول کمتر از ۴ ای که توسط عبارت منظم فوق توصیف می شود، شامل رشته های به طول ۱ و ۲ و ۳ می باشد زیرا زبان توصیف شده، فاقد لامبدا می باشد.
به طول ۱ :
این زبان توصیف شده حتما یک b در رشته های خود دارد. بنابراین رشته های به طول یک، تنها یکی است و همان b است.
به طول ۲ :
رشته های به طول دو می توانند به دو صورت توصیف شوند :
الف- با استفاده از الفبای اجباری b به همراه یک حرف از عبارت سمت چپ آن
ب- با استفاده از الفبای اجباری b به همراه یک حرف از عبارت سمت راست آن
ابتدا مورد الف را بررسی می کنیم.
یکی از این دو حرف همان b است. بنابراین یک حرف از عبارت سمت چپ استخراج می کنیم. رشته های یک حرفی عبارت سمت چپ، a و b هستند. بنابراین دو رشته به طول ۲ خواهیم داشت. ab و bb
حال مورد ب را بررسی می کنیم.
یکی از این دو حرف همان b است. بنابراین یک حرف از عبارت سمت راست استخراج می کنیم. رشته یک حرفی عبارت سمت راست، تنها a است. بنابراین یک رشته به طول دو خواهیم داشت. ba
- نتیجه : رشته های به طول دو در زیر آمده اند :
ab , bb , ba
به طول ۳ :
رشته های به طول ۳ می توانند به سه طریق توصیف شوند :
الف - با استفاده از الفبای اجباری b به همراه دو حرف از عبارت سمت چپ آن
ب - با استفاده از الفبای اجباری b به همراه دو حرف از عبارت سمت راست آن
پ - با استفاده از الفبای اجباری b به همراه یک حرف از عبارت سمت راست و یک حرف از عبارت سمت چپ
الف را بررسی می کنیم :
رشته های دو حرفی عبارت سمت چپ، موارد زیر هستند :
aa,ab,ba,bb
بنابراین وقتی با b دنبال شوند، چهار رشته به طول ۳ ایجاد خواهد شد :
aab,abb,bab,bbb
ب را بررسی می کنیم :
رشته های دو حرفی عبارت سمت راست، موارد زیر هستند :
aa,ab
بنابراین وقتی b، پیش تر از آن ها بیاید، دو رشته خواهیم داشت :
baa,bab
پ را بررسی می کنیم :
رشته های یک حرفی عبارت سمت چپ، a و b هستند.
رشته یک حرفی عبارت سمت راست، تنها رشته a است.
با قرار داده b در میان این ها، رشته های زیر را خواهیم داشت :
aba,bba
- نتیجه : مجموعه رشته های سه حرفی، این ها می باشند :
aab,abb,bab,bbb,baa,aba,bba (دقت شود که در مجموعه ها عضو تکراری نداریم بنابراین رشته bab یک بار می آید)
*در نهایت تعداد رشته های به طول کمتر از ۴ این زبان، ۱۱ می باشد*
(۱۱ فروردین ۱۳۹۳ ۰۵:۲۱ ق.ظ)Morris نوشته شده توسط: سلام و سال نو مبارک.ممنونم سال نو شمام مبارک کی خواستم بدونم که چرا این زبان لاندا تولید نمی کنه ، با تشکر
عبارت منظم : [tex](a b)^∗b(a ab)^∗[/tex]
رشته های به طول کمتر از ۴ ای که توسط عبارت منظم فوق توصیف می شود، شامل رشته های به طول ۱ و ۲ و ۳ می باشد زیرا زبان توصیف شده، فاقد لامبدا می باشد.
به طول ۱ :
این زبان توصیف شده حتما یک b در رشته های خود دارد. بنابراین رشته های به طول یک، تنها یکی است و همان b است.
به طول ۲ :
رشته های به طول دو می توانند به دو صورت توصیف شوند :
الف- با استفاده از الفبای اجباری b به همراه یک حرف از عبارت سمت چپ آن
ب- با استفاده از الفبای اجباری b به همراه یک حرف از عبارت سمت راست آن
ابتدا مورد الف را بررسی می کنیم.
یکی از این دو حرف همان b است. بنابراین یک حرف از عبارت سمت چپ استخراج می کنیم. رشته های یک حرفی عبارت سمت چپ، a و b هستند. بنابراین دو رشته به طول ۲ خواهیم داشت. ab و bb
حال مورد ب را بررسی می کنیم.
یکی از این دو حرف همان b است. بنابراین یک حرف از عبارت سمت راست استخراج می کنیم. رشته یک حرفی عبارت سمت راست، تنها a است. بنابراین یک رشته به طول دو خواهیم داشت. ba
- نتیجه : رشته های به طول دو در زیر آمده اند :
ab , bb , ba
به طول ۳ :
رشته های به طول ۳ می توانند به سه طریق توصیف شوند :
الف - با استفاده از الفبای اجباری b به همراه دو حرف از عبارت سمت چپ آن
ب - با استفاده از الفبای اجباری b به همراه دو حرف از عبارت سمت راست آن
پ - با استفاده از الفبای اجباری b به همراه یک حرف از عبارت سمت راست و یک حرف از عبارت سمت چپ
الف را بررسی می کنیم :
رشته های دو حرفی عبارت سمت چپ، موارد زیر هستند :
aa,ab,ba,bb
بنابراین وقتی با b دنبال شوند، چهار رشته به طول ۳ ایجاد خواهد شد :
aab,abb,bab,bbb
ب را بررسی می کنیم :
رشته های دو حرفی عبارت سمت راست، موارد زیر هستند :
aa,ab
بنابراین وقتی b، پیش تر از آن ها بیاید، دو رشته خواهیم داشت :
baa,bab
پ را بررسی می کنیم :
رشته های یک حرفی عبارت سمت چپ، a و b هستند.
رشته یک حرفی عبارت سمت راست، تنها رشته a است.
با قرار داده b در میان این ها، رشته های زیر را خواهیم داشت :
aba,bba
- نتیجه : مجموعه رشته های سه حرفی، این ها می باشند :
aab,abb,bab,bbb,baa,aba,bba (دقت شود که در مجموعه ها عضو تکراری نداریم بنابراین رشته bab یک بار می آید)
*در نهایت تعداد رشته های به طول کمتر از ۴ این زبان، ۱۱ می باشد*
(۱۴ فروردین ۱۳۹۳ ۰۲:۱۳ ب.ظ)joyebright نوشته شده توسط: ممنونم سال نو شمام مبارک می خواستم بدونم که چرا این زبان لاندا تولید نمی کنه ، با تشکر
لطفا بفرمایید چرا به نظر شما لامبدا تولید می کند تا اینکه من برای شما توضیح دهم که اشتباه شما از کجاست.
کوچکترین رشته ای که این زبان تولید می کند b است.
(۱۴ فروردین ۱۳۹۳ ۰۵:۳۹ ب.ظ)Morris نوشته شده توسط:(14 فروردین ۱۳۹۳ ۰۲:۱۳ ب.ظ)joyebright نوشته شده توسط: ممنونم سال نو شمام مبارک می خواستم بدونم که چرا این زبان لاندا تولید نمی کنه ، با تشکر
لطفا بفرمایید چرا به نظر شما لامبدا تولید می کند تا اینکه من برای شما توضیح دهم که اشتباه شما از کجاست.
کوچکترین رشته ای که این زبان تولید می کند b است.
ممنونم مشکلم حل شد
