نظریه زبان

ادامه تمرین ۷

و)L={w:|na(w)−nb(w)|mod3<2}">L={w:|na(w)−nb(w)|mod3<</span>2}L={w:|na(w)−nb(w)|mod3<2}

ی) L=left { w: left ( n_{a}left ( w right ) 2n_{b} right left ( w right )) mod 3 < 2 right }">L=left { w: left ( n_{a}left ( w right ) 2n_{b} right left ( w right )) mod 3 < 2 right }L=left { w: left ( n_{a}left ( w right ) 2n_{b} right left ( w right )) mod 3 < 2 right }

۸-یک دنباله در یک رشته، یک زیر رشته با طول حداقل دو علامت یکسان است. به عنوان مثال رشته abbbaab شامل یک دنباله به طول ۳ از b ها و یک دنباله به طول ۲ از a ها می باشد. یک dfa برای زبان های زیر روی {a,b}">{a,b}{a,b} پیدا کنید.

الف) L={w:wcontainsnorunsoflengthlessthenfour}.">L={w:wcontainsnorunsoflengthlessthenfour}.L={w:wcontainsnorunsoflengthlessthenfour}.
(w شامل هیچ دنباله ای به طول کمتر از ۴ نمی باشد.)

ب)L=left { w:;every; run; of; a's; has; length; either; tow; or; three}right }.">L=left { w:;every; run; of; a's; has; length; either; tow; or; three}right }.L=left { w:;every; run; of; a's; has; length; either; tow; or; three}right }.
(طول هر دنباله از a ها ۲ یا ۳ باشد.)

ج) L={w:thereareatmosttworunsofa′soflengththree}.">L={w:thereareatmosttworunsofa′soflengththree}.L={w:thereareatmosttworunsofa′soflengththree}.
(حداکثر ۲ تا دنباله از a ها بطول ۳ وجود داشته باشد.)

د)L={w:thereareexactlytworunsofa′soflength3}.">L={w:thereareexactlytworunsofa′soflength3}.L={w:thereareexactlytworunsofa′soflength3}.
(دقیقاً ۲ دنباله با طول ۳ از a ها وجود داشته باشد.)

۹-مجموعه رشته های روی {۰,۱} را که طبق شروط زیر تعریف می شوند در نظر بگیرید.برای هر کدام یک dfa طراحی کنید.

الف) پس از هر ۰۰ فوراً یک ۱ بیاید.به عنوان مثال، رشته های ۱۰۱ و ۰۰۱۰ و ۰۰۱۰۰۱۱۰۰۱ در زبان هستند اما ۰۰۰۱و۰۰۱۰۰ در زبان نیستند.

ب) همه رشته هایی که شامل ۰۰ بوده ولی شامل ۰۰۰ نباشند.

ج)سمت چپ ترین نماد با سمت راست ترین نماد متفاوت باشد.

د)هر زیر رشته ای از چهار نماد که حداکثر دارای دو ۰ باشد. برای مثال، ۰۰۱۱۱۰ و ۰۱۱۰۰۱ در زبان هستند، ولی ۱۰۰۱۰ در زبان نیست زیرا یکی از زیر رشته های آن، یعنی ۰۰۱۰ دارای سه ۰ می باشد.

***حل نشده***

ه)همه رشته هایی با طول پنج یا بیشتر که در آنها چهارمین نماد از سمت راست ازچپ ترین نماد متفاوت باشد.

***حل نشده***

و)تمام رشته هایی که دو نماد سمت چپ آن با دو نماد سمت راست آن یکسان باشد.

ی)تمام رشته هایی با طول ۴ یا بیشتر که ۳ نماد سمت چپ آن یکسان بوده و با سمت راست ترین نماد متفاوت باشد.

***حل نشده***

۱۰- یک پذیرنده متناهی قطعی بسازید که رشته های روی {a,b} را بپذیرد، اگر و فقط اگر مقدار رشته که به عنوان نمایش دودویی از یک عدد صحیح تفسیر میشود، به پیمانه پنج برابر صفر شود(بر صف تقسیم پذیر باشد). برای مثال، ۰۱۰۱ و ۱۱۱ که به ترتیب نشان دهنده اعداد صحیح ۵ و ۱۵ می باشند، پذیرفته می شوند.

***حل نشده***

۱۱- نشان دهید که زبان L={vwv:v,w∈{a,b}∗,|v|=2}">L={vwv:v,w∈{a,b}∗,|v|=2}L={vwv:v,w∈{a,b}∗,|v|=2} منظم است.

برای نشان دادن اینکه زبانی منظم است کافی است برای آن یک dfa رسم کنیم لذا:

۱۲- نشان دهید که زبان L={an:n⩾4}">L={an:n⩾4}L={an:n⩾4} منظم است

۱۳- نشان دهید که زبان L={an:n⩾0,n≠4}">L={an:n⩾0,n≠4}L={an:n⩾0,n≠4} منظم است.

۱۴- نشان دهید که زبان L={an:niseitheramultipleofthreeoramultipleoffive}">L={an:niseitheramultipleofthreeoramultipleoffive}L={an:niseitheramultipleofthreeoramultipleoffive}
منظم است.(n مضربی از ۳ یا ۵ باشد)

سوال: آیا برای هر زبان بصورت an">anan که n مضربی از x یا y باشد، نقطه x*y همان نقطه شروع است؟(تشکیل حلقه)

۱۵- نشان دهید که زبان L={an:nisamultipleofthree,butnotamultipleoffive}">L={an:nisamultipleofthree,butnotamultipleoffive}L={an:nisamultipleofthree,butnotamultipleoffive}
منظم است.(n مضربی از ۳ باشد اما مضربی از ۵ نباشد)