با سلام
من چندتا سوال از نظریه زبان داشتم که نتونستم حلش کنم و در واقع نتونستم بفهممش برای همین گفتم اول کار از بچه ها بپرسم تا بتونم پایه ام را قوی کنم
چون من تا حالا نظریه نخونده ام و از کتاب ابراهیم اکبری شروع کرده ام چون لینز را خوندم و چیزی متوجه نشدم
سوال:
فرض کنید
[tex]\sum\left \{ a,b \right \}[/tex]
به سواات زیر پاسخ دهید.
دوستان لطفا سوالات را بصورت کامل بیان کنید تا بتونم یاد بگیرم
1)عبارت منظمی بنویسید که شامل زیررشته aa نباشد
2)تمام رشته هایی که در ان طول جملات زوج باشد
3)تمام رشته هایی که در ان طول جملات فرد باشد
4)تمام رشته هایی که چهارمین نماد ان از راست a باشد
5)تمام رشته هایی که شامل زیررشته aba و با b شروع شود
سوال 2:
فرض کنید
[tex]\sum \left \{a,b,c \right \}[/tex]
1)تمام رشته هایی که aها قبل از b و b ها قبل از c ظاهر شود
2)تمام رشته هایی که حداقل طولشان 2 و a قبل از b ظاهر شود
3)تمام رشته هایی با طول زوج که شامل فقط یک a باشد
4)تمام رشته هایی که که مجموع تعداد a و b در ان 3 باشد
5)تمام رشته هایی که طول رشته فرد و شامل زیر رشته bb باشد
6)تمام رشته هایی با طول زوج و b فقط دوبار ظاهر شود
شرمنده که تعداد سوالات زیاد شد ولی تا اینا را نفهمم نمیتونم ادامه بدم
راستس این یعنی چی و چه رشته هایی را تولید میکند؟
[tex]\left ( a b \right ) \star[/tex]
راستس این یعنی چی و چه رشته هایی را تولید میکند؟
[tex]\left ( a b \right ) \star[/tex]
یعنی هر ترکیبی از a و b را میتواند تولید کند و همچنین لاندا(رشته پوچ) را.
[tex](a b)^{*}={\lambda ,a,b,aa,ab,ba,bb,aaa,aab,...}[/tex]
۱)عبارت منظمی بنویسید که شامل زیررشته aa نباشد
اگر b بیاید مشکلی وجود ندارد و بعد آن هر چیزی میتواند بیاید ولی اگر a بیاید باید کاری کنیم که بعد از آن یا هیچی نیاید و یا حتما" b بیاید یعنی:
[tex](b a(\lambda b))[/tex]
حالا هر ترکیبی از این ها امکان پذیره پس من star میزارم
[tex](b a(\lambda b))^*[/tex]
۲)تمام رشته هایی که در ان طول جملات زوج باشد
در این جور عبارات منظم ابتدا حداقل ها را در نظر میگیریم حداقل عدد زوج رو 2 میگیریم، حالا کاری میکنیم که در عبارت منظم بتونیم دو تا دوتا رشته های زوج بسازیم.
[tex]\left \{ (a b)(a b) \right \}^*[/tex]
علامت به علاوه تو عبارت منظم یعنی "یا"- الان داخل آکولاد من رشته ای به طول دو رو حتما" دارم.
۴)تمام رشته هایی که چهارمین نماد ان از راست a باشد
قبل از a هرچیزی میتونه بیاد و مهم نیست- بعد از a حتما" باید 3تا کاراکتر دیگه ظاهر بشه(حالا فرقی نمیکنه که این 3کاراکتر a باشن یا b)
[tex]\left ( a b \right )^*a\left ( a b \right )\left ( a b \right )\left ( a b \right )[/tex]
۵)تمام رشته هایی که شامل زیررشته aba و با b شروع شود
b حتما" اول میادبعد از اینکه دقیقا" چی میاد مشخص نیست ولی یه جایی بعد از b باید aba ظاهر بشه و دوباره بعد از aba هرچیزی میتواند بیاید:
[tex]b\left ( a b \right )^*aba\left ( a b \right )^*[/tex]
یعنی میشه گفت که
[tex]\left ( a b\ \right )\star[/tex]
همون
[tex]\sum \star[/tex]
میباشد
همچنین این ها یعنی چی؟
[tex]\left ( a b\star \right )[/tex]
[tex]\left (\left ( a b \right )\left ( a b \right ) \right ) \star[/tex]
[tex]\left (\left ( a b \right )\left ( a b \right ) \right ) \star[/tex]
(06 مرداد 1392 01:19 ب.ظ)MajidManesht2012 نوشته شده توسط: [ -> ]۱)عبارت منظمی بنویسید که شامل زیررشته aa نباشد
اگر b بیاید مشکلی وجود ندارد و بعد آن هر چیزی میتواند بیاید ولی اگر a بیاید باید کاری کنیم که بعد از آن یا هیچی نیاید و یا حتما" b بیاید یعنی:
[tex](b a(\lambda b))[/tex]
حالا هر ترکیبی از این ها امکان پذیره پس من star میزارم
[tex](b a(\lambda b))^*[/tex]
فکر نمیکنم جواب درست باشه aa به هر تعداد میتونه درست بشه جواب: [tex](b ab)^*(a \lambda)[/tex]
۳)تمام رشته هایی که در ان طول جملات فرد باشد
[tex](ab ba aa bb)^*(a b)[/tex]
۱)تمام رشته هایی که aها قبل از b و b ها قبل از c ظاهر شود
[tex]a^*b^*c^*[/tex]
۲)تمام رشته هایی که حداقل طولشان ۲ و a قبل از b ظاهر شود
[tex](ab (b c)(b c))(ab c b)^*[/tex]
۴)تمام رشته هایی که که مجموع تعداد a و b در ان ۳ باشد
[tex]c^*(a b)c^*(a b)c^*(a b)c^*[/tex]
جواب من برای سوالات ۳ ۵ ۶ کمی طولانی اند شاید دوستان جواب بهتری داشته باشند
حالا جواب این سوال چی میشه؟
عبارت منظمی بنویسید که شامل زیررشته aa نباشد
سلام. جواب این سوالتون رو آقای sadeghb نوشتند.
بقیه سوالات شما:
۲)تمام رشته هایی که حداقل طولشان ۲ و a قبل از b ظاهر شود
این سوالتون برای من یه مقدار گنگه. اینطور در نظر میگیرم که هیچ aیی بعد از اولین b (درصورت وجود) نداشته باشیم.
[tex](a c)(a c)(a c)^*(b c)^* (a c)(a c)^*(b c)^*(b c) (a c)^*(b c)^*(b c)(b c)[/tex]
۳)تمام رشته هایی با طول زوج که شامل فقط یک a باشد
[tex]((b c)(b c))^*a(b c)((b c)(b c))^* ((b c)(b c))^*(b c)a((b c)(b c))^*[/tex]
۵)تمام رشته هایی که طول رشته فرد و شامل زیر رشته bb باشد
[tex]((a b c)(a b c))^*bb(a b c)((a b c)(a b c))^* (a b c)((a b c)(a b c))^*bb((a b c)(a b c))^*[/tex]
۶)تمام رشته هایی با طول زوج و b فقط دوبار ظاهر شود
[tex]((a c)(a c))^*b((a c)(a c))^*b((a c)(a c))^* (a c)((a c)(a c))^*b(a c)((a c)(a c))^*b((a c)(a c))^* (a c)((a c)(a c))^*b((a c)(a c))^*b(a c)((a c)(a c))^* ((a c)(a c))^*b(a c)((a c)(a c))^*b(a c)((a c)(a c))^*[/tex]
(06 مرداد 1392 03:18 ب.ظ)nima20-20 نوشته شده توسط: [ -> ]یعنی میشه گفت که
[tex]\left ( a b\ \right )\star[/tex]
همون
[tex]\sum \star[/tex]
میباشد
اگه الفبامون فقط a,b باشه درسته.
(06 مرداد 1392 03:18 ب.ظ)nima20-20 نوشته شده توسط: [ -> ][tex]\left ( a b\star \right )[/tex]
[tex]\left (\left ( a b \right )\left ( a b \right ) \right ) \star[/tex]
[tex]\left (\left ( a b \right )\left ( a b \right ) \right ) \star[/tex]
اولی میشه [tex]a b^*=a \lambda b bb bbb bbbb ...[/tex].
دومی میشه [tex](a b)^*={\sum}^*[/tex]. یعنی تمام رشته ها در الفبای دو حرفی.
سومی میشه تمام رشته های بطول زوج در الفبای دوحرفی.