سلام و سال نو مبارک.
عبارت منظم : (ab)∗b(aab)∗
رشته های به طول کمتر از ۴ ای که توسط عبارت منظم فوق توصیف می شود، شامل رشته های به طول ۱ و ۲ و ۳ می باشد زیرا زبان توصیف شده، فاقد لامبدا می باشد.
به طول ۱ :
این زبان توصیف شده حتما یک 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 یک بار می آید)
*در نهایت تعداد رشته های به طول کمتر از ۴ این زبان، ۱۱ می باشد*
