06 آبان 1393, 06:04 ب.ظ
06 آبان 1393, 08:29 ب.ظ
دو زبان اول ذاتا مبهم هستند و زبان سوم را می توان به صورت قطعی در نظر گرفت:
در زبان اول ما دو نوع رشته را می پذیریم نوع اول رشته هایی هستند که تعداد a,b باید برابر باشد و تعداد c ها هر چیزی می تواند باشد
نوع دوم رشته هایی است که تعداد A ها در آن مهم نیست ولی تعداد b,c ها باید برابر باشد
اگر بخواهیم یک ماشین برای تشخیص هر دو نوع بنویسیم این ماشین تکلیف خودش را نمی داند که یاید برابری a,b ها را مقایسه کند یا برابری b,c ها را .
دقت کنید که یک ماشین pda نمی تواند همزمان برابری a,b و برابری b,c را چک کند چون یک ماشین pda برای برابری تعداد دو کاراکتر این کار را انجام می دهد که به ازای هر عدد از کاراکتر نوع اول یک علامتی را push می کند و بعد به ازای هر دونه از کاراکتر نوع دوم یکی از علامت های بالای پشته رو pop می کنه.
مثلا در این زبان برای تشخیص رشته هایی که تعداد a,b برابره و تعداد c ها مهم نیست باید برابر a را با برابری b مقایسه کنیم به ازای هر یه دونه a یه علامت داخل پشته push می کنیم تا وقتی که A ها تموم بشه . و بعد به ازای هر یه دونه b ای که در ورودی می بینیم یه دونه از علامت های داخل پشته را pop می کنیم اگر بعد از تمام شدن b ها علامت های داخل پشته همه شون pop بشن یعنی تعداد A ها با b ها برابر بوده (اگه بعد از تمام شدن چیزی ته پشته بمونه یعنی a ها بیشتر بوده و اگر وسط کار b ای در ورودی ببینیم و بهخواهیم علامتی از پشته را pop کنیم اماچیزی در پشته نباشد یعنی تعداد bها بیشتر یوده)
خب حالا برای تشخیص رشته هایی که a,b برابره و c هر تعدادی می تونه باشه برای هر A باید علامتی push و به ازای هر b باید علامتی از پشته pop کنیم و بعد هر چی c دیدیم فقط رد کنیم.
و برای تشخیص رشته هایی که تعداد a آن ها هر چی می تواند باشد اما تعداد b,c برابر دارد باید ابتدا هر چی a دیدیم فقط رد کنیم و بعد به ازای هر b علامتی را داخل پشته push کنیم و بعد به ازای هر c علامتی را از پشته pop کنیم.
دقت کنید که ما می خواهیم برای تشخیص هر دو نوع رشته ها فقط یک ماشین بنویسیم اما اگر به قسمت های bold شده دقت کنید این ماشین بالاخره تکلیف خودش را نمی داند که باید به ازای هر b علامتی را داخل پشته push کند یا از پشته pop کند.
پس این زبان ذاتا مبهم است.
برای زبان دو باید به این نکته توجه کنید که اگر بخواهیم ماشینی برای تشخیص رشته هایی داشتهخ باشیم که تعداد b ها دوبرابر a هاست دو راه داریم یا اینکه در ابتدا به ازای هر A که دیدیم دو علامت داخل پشته بریزیم و بعد به ازای هر B یک علامت برداریم واضحه که تنها زمانی پشته در انتهای رشته خالی می شود که تعداد b ها دو برابر a ها باشد.
یا اینکه اون اول به ازای هر a ای که می بینیم یک علامت داخل پشته بریزیم و بعد به ازای هر دو تا B یه دونه علامت از پشته برداریم.
فر کنید ما روش اول را انتخاب کرده ایم.
خب ما برای تشخیص زبان دوم باید یک سری رشته هایی بپذیریم که تعداد a ها برابر b هاست و یک سری رشته هایی بپذیریم که تعداد b ها دو برابر تعداد a هاست. اگر بخواهیم اونایی رو بپذریریم که تعداد b ها برابر a هاست باید به ازای هر a یک علامت داخل پشته بپذریرم و به ازای هر b یک علامت از پشته برداریم اما اگر بخواهیم اونایی رو بپذریرم که تعداد b ها دوبرابر تعداد a هاست باید به ازای هر a دو علامت داخل پشته بریزیم و برای هر b یک علامت از پشته برداریم
اگه به قسمت های bold شده دقت کنید می بینید اگه بخواهیم یک ماشین بنویسیم که بتونه هر دونوع رشته رو تشخیص بده این ماشین نمی دونه باید به ازای هر a یه دونه علامت داخلا پشته بریزه یا دوتا. پس ذاتا مبهمه
اگه روش دوم رو هم برای تشخیص رشته های با تعداد b دوبرابر تعداد A ها انتخاب می کردیم باز هم زبان ذداتا مبهم بود چرا. چون هم باید به ازای هر a یه دونه علامت بذاره و به ازای هر b یه دونه برداره . هم باید به ازای هر a یه دونه علامت داخل پشته بذاره و به ازای هر دو تا b یه دونه علامت از پشته برداره که باز هم ذاتا مبهم است.
اما زبان سوم ذاتا مبهم نیست چرا چون تیکه اول زیر مجموعته ای از تیکه دومه.
این زبان می گه رشته اهیی را بپذیر که یا تعداد B ها شون بیشتر از a هاست یا رشته هایی را بپذیر که تعداد b هاشون بیشتر از A هاست. خب واضحه که اگه ما فقط رشته هایی رو بپذیریم که تعداد B هاش بیشتر از A ها باشه رشته های مدل اول رو هم پذیرفته ایم پس کلا زبان سوم معادل این زبانه :
[tex]L_3=\{a^nb^m,\: n>=m\}[/tex]
که این زبان قطعی است
در زبان اول ما دو نوع رشته را می پذیریم نوع اول رشته هایی هستند که تعداد a,b باید برابر باشد و تعداد c ها هر چیزی می تواند باشد
نوع دوم رشته هایی است که تعداد A ها در آن مهم نیست ولی تعداد b,c ها باید برابر باشد
اگر بخواهیم یک ماشین برای تشخیص هر دو نوع بنویسیم این ماشین تکلیف خودش را نمی داند که یاید برابری a,b ها را مقایسه کند یا برابری b,c ها را .
دقت کنید که یک ماشین pda نمی تواند همزمان برابری a,b و برابری b,c را چک کند چون یک ماشین pda برای برابری تعداد دو کاراکتر این کار را انجام می دهد که به ازای هر عدد از کاراکتر نوع اول یک علامتی را push می کند و بعد به ازای هر دونه از کاراکتر نوع دوم یکی از علامت های بالای پشته رو pop می کنه.
مثلا در این زبان برای تشخیص رشته هایی که تعداد a,b برابره و تعداد c ها مهم نیست باید برابر a را با برابری b مقایسه کنیم به ازای هر یه دونه a یه علامت داخل پشته push می کنیم تا وقتی که A ها تموم بشه . و بعد به ازای هر یه دونه b ای که در ورودی می بینیم یه دونه از علامت های داخل پشته را pop می کنیم اگر بعد از تمام شدن b ها علامت های داخل پشته همه شون pop بشن یعنی تعداد A ها با b ها برابر بوده (اگه بعد از تمام شدن چیزی ته پشته بمونه یعنی a ها بیشتر بوده و اگر وسط کار b ای در ورودی ببینیم و بهخواهیم علامتی از پشته را pop کنیم اماچیزی در پشته نباشد یعنی تعداد bها بیشتر یوده)
خب حالا برای تشخیص رشته هایی که a,b برابره و c هر تعدادی می تونه باشه برای هر A باید علامتی push و به ازای هر b باید علامتی از پشته pop کنیم و بعد هر چی c دیدیم فقط رد کنیم.
و برای تشخیص رشته هایی که تعداد a آن ها هر چی می تواند باشد اما تعداد b,c برابر دارد باید ابتدا هر چی a دیدیم فقط رد کنیم و بعد به ازای هر b علامتی را داخل پشته push کنیم و بعد به ازای هر c علامتی را از پشته pop کنیم.
دقت کنید که ما می خواهیم برای تشخیص هر دو نوع رشته ها فقط یک ماشین بنویسیم اما اگر به قسمت های bold شده دقت کنید این ماشین بالاخره تکلیف خودش را نمی داند که باید به ازای هر b علامتی را داخل پشته push کند یا از پشته pop کند.
پس این زبان ذاتا مبهم است.
برای زبان دو باید به این نکته توجه کنید که اگر بخواهیم ماشینی برای تشخیص رشته هایی داشتهخ باشیم که تعداد b ها دوبرابر a هاست دو راه داریم یا اینکه در ابتدا به ازای هر A که دیدیم دو علامت داخل پشته بریزیم و بعد به ازای هر B یک علامت برداریم واضحه که تنها زمانی پشته در انتهای رشته خالی می شود که تعداد b ها دو برابر a ها باشد.
یا اینکه اون اول به ازای هر a ای که می بینیم یک علامت داخل پشته بریزیم و بعد به ازای هر دو تا B یه دونه علامت از پشته برداریم.
فر کنید ما روش اول را انتخاب کرده ایم.
خب ما برای تشخیص زبان دوم باید یک سری رشته هایی بپذیریم که تعداد a ها برابر b هاست و یک سری رشته هایی بپذیریم که تعداد b ها دو برابر تعداد a هاست. اگر بخواهیم اونایی رو بپذریریم که تعداد b ها برابر a هاست باید به ازای هر a یک علامت داخل پشته بپذریرم و به ازای هر b یک علامت از پشته برداریم اما اگر بخواهیم اونایی رو بپذریرم که تعداد b ها دوبرابر تعداد a هاست باید به ازای هر a دو علامت داخل پشته بریزیم و برای هر b یک علامت از پشته برداریم
اگه به قسمت های bold شده دقت کنید می بینید اگه بخواهیم یک ماشین بنویسیم که بتونه هر دونوع رشته رو تشخیص بده این ماشین نمی دونه باید به ازای هر a یه دونه علامت داخلا پشته بریزه یا دوتا. پس ذاتا مبهمه
اگه روش دوم رو هم برای تشخیص رشته های با تعداد b دوبرابر تعداد A ها انتخاب می کردیم باز هم زبان ذداتا مبهم بود چرا. چون هم باید به ازای هر a یه دونه علامت بذاره و به ازای هر b یه دونه برداره . هم باید به ازای هر a یه دونه علامت داخل پشته بذاره و به ازای هر دو تا b یه دونه علامت از پشته برداره که باز هم ذاتا مبهم است.
اما زبان سوم ذاتا مبهم نیست چرا چون تیکه اول زیر مجموعته ای از تیکه دومه.
این زبان می گه رشته اهیی را بپذیر که یا تعداد B ها شون بیشتر از a هاست یا رشته هایی را بپذیر که تعداد b هاشون بیشتر از A هاست. خب واضحه که اگه ما فقط رشته هایی رو بپذیریم که تعداد B هاش بیشتر از A ها باشه رشته های مدل اول رو هم پذیرفته ایم پس کلا زبان سوم معادل این زبانه :
[tex]L_3=\{a^nb^m,\: n>=m\}[/tex]
که این زبان قطعی است
07 آبان 1393, 06:11 ب.ظ
(06 آبان 1393 08:29 ب.ظ)fatemeh69 نوشته شده توسط: [ -> ]اما زبان سوم ذاتا مبهم نیست چرا چون تیکه اول زیر مجموعته ای از تیکه دومه.
این زبان می گه رشته اهیی را بپذیر که یا تعداد B ها شون بیشتر از a هاست یا رشته هایی را بپذیر که تعداد b هاشون بیشتر از A هاست. خب واضحه که اگه ما فقط رشته هایی رو بپذیریم که تعداد B هاش بیشتر از A ها باشه رشته های مدل اول رو هم پذیرفته ایم پس کلا زبان سوم معادل این زبانه :
[tex]L_3=\{a^nb^m,\: n>=m\}[/tex]
که این زبان قطعی است
سلام. وقت بخیر. به نظرم توانها رو اشتباه گرفتید. اگه n<=m بود زیرمجموعه میشد.
19 آبان 1393, 02:58 ق.ظ
(07 آبان 1393 06:11 ب.ظ)Jooybari نوشته شده توسط: [ -> ](06 آبان 1393 08:29 ب.ظ)fatemeh69 نوشته شده توسط: [ -> ]اما زبان سوم ذاتا مبهم نیست چرا چون تیکه اول زیر مجموعته ای از تیکه دومه.
این زبان می گه رشته اهیی را بپذیر که یا تعداد B ها شون بیشتر از a هاست یا رشته هایی را بپذیر که تعداد b هاشون بیشتر از A هاست. خب واضحه که اگه ما فقط رشته هایی رو بپذیریم که تعداد B هاش بیشتر از A ها باشه رشته های مدل اول رو هم پذیرفته ایم پس کلا زبان سوم معادل این زبانه :
[tex]L_3=\{a^nb^m,\: n>=m\}[/tex]
که این زبان قطعی است
سلام. وقت بخیر. به نظرم توانها رو اشتباه گرفتید. اگه n<=m بود زیرمجموعه میشد.
بله همینطوره و فک کنم با این اوصاف زان سوم هم مبهم باشه
21 آبان 1393, 10:14 ب.ظ
سلام مرسی از پاسختون ولی این جواب پاسخنامس
[attachment=17237]
[attachment=17237]
22 آبان 1393, 04:47 ق.ظ
(21 آبان 1393 10:14 ب.ظ)Elena_71 نوشته شده توسط: [ -> ]سلام مرسی از پاسختون ولی این جواب پاسخنامس
از نظر من پاسخنامه اشتباهه.
22 آبان 1393, 01:10 ب.ظ
(21 آبان 1393 10:14 ب.ظ)Elena_71 نوشته شده توسط: [ -> ]سلام مرسی از پاسختون ولی این جواب پاسخنامس
خیلی اشتباهه چون لینز وقتی خواسته زبان های غیر قطعی رو یاد بده با [tex]L_2[/tex] یاد داده یعنی L2 دقیقا مثال 7-11 لینزه که بر اساس همین زبان اومده مفهوم غیر قطعی بودنو توضیح داده.
22 آبان 1393, 09:09 ب.ظ
(22 آبان 1393 01:10 ب.ظ)fatemeh69 نوشته شده توسط: [ -> ](21 آبان 1393 10:14 ب.ظ)Elena_71 نوشته شده توسط: [ -> ]سلام مرسی از پاسختون ولی این جواب پاسخنامس
خیلی اشتباهه چون لینز وقتی خواسته زبان های غیر قطعی رو یاد بده با [tex]L_2[/tex] یاد داده یعنی L2 دقیقا مثال ۷-۱۱ لینزه که بر اساس همین زبان اومده مفهوم غیر قطعی بودنو توضیح داده.
با این اوصاف هر گرامر غیر قطعی ذاتا مبهم هستش!زبانهای ذاتا مبهم تعدادشون زیاد نیست!بنظرم جواب پارسه صحیحه.
23 آبان 1393, 01:27 ق.ظ
(22 آبان 1393 09:09 ب.ظ)ahp89 نوشته شده توسط: [ -> ]با این اوصاف هر گرامر غیر قطعی ذاتا مبهم هستش!زبانهای ذاتا مبهم تعدادشون زیاد نیست!بنظرم جواب پارسه صحیحه.
تا اونجا که میدونم قطعی بودن گرامر و ابهام زبان ارتباطی به هم ندارن. یکی مربوط به زبانه و اون یکی گرامر. برای یه زبان غیرمبهم هم میشه گرامر قطعی نوشت و هم گرامر غیرقطعی.
23 آبان 1393, 01:44 ق.ظ
ببخشید من غیر قطعی رو با ذاتا مبهم اشتباه گرفته بودم ممنون که متوجهم کردید.
زبان دوم ذاتا مبهم نیست این هم یه گرامر غیر مبهم برای زبان دوم:
[tex]S-->\lambda|aAb|aBbb[/tex]
[tex]A-->\lambda|aAb[/tex]
[tex]B-->\lambda|aBbb[/tex]
لاندا فقط مستقیم از S تولید می شه بقیه رشته ها هم با توجه به این که تعداد a,b برابر داره یا دو برابر واضحه که از کدوم قانون تولید می شن.
زبان سوم هم ذاتا مبهم نیست:
[tex]S-->aAbb|aBb|\lambda[/tex]
[tex]A-->aAbb|\lambda[/tex]
[tex]B-->C|aBb|\lambda[/tex]
[tex]C-->aC|\lambda[/tex]
اینم واضحه دیگه یا تعداد a ها کمتر از b هاست یا برابره یا بیشتر. اگه برابر باشه که تنها رشته با تعداد برابر a,b که داخل زبان باشه لاندا ست که تنها از S تولید می شه. اگه تعداد a ها کمتر باشه پس باید تعداد a ها نصف b ها باشه که تنها از A قابل تولیده. و اگه a ها بیشتر از b ها باشن تنها از B قابل تولیده.
زبان اول هم که کلا ذاتا مبهمه تمرین لینز هم هست.
زبان دوم ذاتا مبهم نیست این هم یه گرامر غیر مبهم برای زبان دوم:
[tex]S-->\lambda|aAb|aBbb[/tex]
[tex]A-->\lambda|aAb[/tex]
[tex]B-->\lambda|aBbb[/tex]
لاندا فقط مستقیم از S تولید می شه بقیه رشته ها هم با توجه به این که تعداد a,b برابر داره یا دو برابر واضحه که از کدوم قانون تولید می شن.
زبان سوم هم ذاتا مبهم نیست:
[tex]S-->aAbb|aBb|\lambda[/tex]
[tex]A-->aAbb|\lambda[/tex]
[tex]B-->C|aBb|\lambda[/tex]
[tex]C-->aC|\lambda[/tex]
اینم واضحه دیگه یا تعداد a ها کمتر از b هاست یا برابره یا بیشتر. اگه برابر باشه که تنها رشته با تعداد برابر a,b که داخل زبان باشه لاندا ست که تنها از S تولید می شه. اگه تعداد a ها کمتر باشه پس باید تعداد a ها نصف b ها باشه که تنها از A قابل تولیده. و اگه a ها بیشتر از b ها باشن تنها از B قابل تولیده.
زبان اول هم که کلا ذاتا مبهمه تمرین لینز هم هست.