سلام به همگی
تو جزوه آقای کارگهی مثالی اورده شده که من تصویرشو گذاشتم میخواستم بدونم چرا نتیجه الحاق مجموعه تهی شده است؟
با تشکر از دوستان
سلام.
ببین، زبان تهی (زبان تهی با رشته تهی فرق میکنه)، مانند عدد صفر میمونه که با هر عدد دیگه ای "ضرب" بشه؛ که کلا نتیجه رو صفر می کنه. پس الحاق هر رشته ای با زبان تهی، برابر میشه با زبان تهی.
اما رشته تهی که اونو با {} یا لاندا نشون می دن، مانند عدد یک میمونه که با هر عدد دیگه ای "ضرب" بشه؛ که کلا نتیجه برابر خود رشته اصلی میشه. پس الحاق هر زبان با رشته تهی، برابر میشه با زبان اصلی.
---------------------------------------
@.L = L.@ = @ ---- الحاق زبان تهی با زبان L
#.L = L.# = L ---- الحاق رشته تهی با زبان L
---------------------------------------
فکر کنم اشتباه تایپی تو اون عکس که گذاشتین باشه.
مطمئنید که الحاق زبان L با زبان تهی تهی میشه؟
آخه مثلا گرامر های زیر رو در نظر بگیرید
L1 :
A ->Ba
B->Bb | b
L2 :
S-> lambda
حالا الحاق این دو زبان رو میشه اینطور ساخت :
C->AS
A->Ba
B->Bb | b
S->lambda
حالا این زبان تهی یا من اشتباه میکنم؟
ممنون از شما اقای احمدی این عکس عین تو جزوه ایشونه،سر کلاس ما هم همین سوال مطرح شده
این لینک جزوه هستش که اقای Avicenna گذاشتند:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
حالا از کجا بایستی متوجه شد که منظور سوال ،زبان تهی بود یا رشته تهی؟
پس این سوال دو جواب داره درسته؟
(۲۹ مهر ۱۳۹۱ ۰۲:۰۲ ب.ظ)javadem نوشته شده توسط: مطمئنید که الحاق زبان L با زبان تهی تهی میشه؟
آخه مثلا گرامر های زیر رو در نظر بگیرید
L1 :
A ->Ba
B->Bb | b
L2 :
S-> lambda
حالا الحاق این دو زبان رو میشه اینطور ساخت :
C->AS
A->Ba
B->Bb | b
S->lambda
حالا این زبان تهی یا من اشتباه میکنم؟
سلام. بله دوست عزیز، از گفته خودم مطمئنم.
زبان L1 که شما نوشتین در حقیقت این رشته رو تولید می کنه b+ a (یعنی زبانی که هرتعداد b در اول بیاید و با یک a تمام شود).
حالا زبان L2 رو نوشتین، این زبان، "زبان تهی نیست"، چون رشته تهی (لاندا) رو که داره. زبان تهی یعنی هیچ رشته ای نداشته باشه(حتی لاندا). و از الحاق اون دوتا زبان که نوشتین L3 بدست اومده که برابر با همون زبان L1 است.
موفق باشی.
بله الان متوجه اشتباهم شدم. من زبان تهی رو اشتباه گرفته بودم.
خیلی ممنون. اصلا فکرم سمت ربانهایی که مثلا حلقه دارن نرفت واسه همین اسیر این اشتباه شدم.
(۲۹ مهر ۱۳۹۱ ۰۲:۲۲ ب.ظ)Pakzad نوشته شده توسط: ممنون از شما اقای احمدی این عکس عین تو جزوه ایشونه،سر کلاس ما هم همین سوال مطرح شده
این لینک جزوه هستش که اقای Avicenna گذاشتند:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
حالا از کجا بایستی متوجه شد که منظور سوال ،زبان تهی بود یا رشته تهی؟
پس این سوال دو جواب داره درسته؟
در صورت سوال حتما باید اشاره کنه که زبان تهی بوده یا نه.
اگه گرامر داده بود که می شه حدس زد که زبان تهی هست یا نه( اگه توانایی تولید هیچ رشته ای رو نداشته باشه، یا اگه حالت پایانی نداشته باشه، یا اگه از حالت شروع به حداقل یک حالت پایانی راهی وجود نداشته باشه زبان تهی بوده) اما اگه در همون حالت شروع (حالت S) قانون S-->lambda وجود داشته باشه (این زبان توانایی رشته تهی رو داره).
---------------------
اگه ماشین داده بود صورت سوال، از حالت شروع به یکی از حالات پایانی راهی نداشته باشه، یا اصلا حالت پایانی نداشته باشد، یا کلا حالت شروع مشخص نباشد، زبان، یک زبان تهی است. اما اگه همون حالت اولی(q0 یا S) حالت پایانی هم باشد ماشین رشته لاندا رو هم قبول می کند.
--------------------
موفق باشی.
(۲۹ مهر ۱۳۹۱ ۰۱:۱۵ ب.ظ)Pakzad نوشته شده توسط: سلام به همگیمطمئنا فرض شده زبان L یک زبان تهی است ، که اینجا نیاورده.
تو جزوه آقای کارگهی مثالی اورده شده که من تصویرشو گذاشتم میخواستم بدونم چرا نتیجه الحاق مجموعه تهی شده است؟
با تشکر از دوستان
==
در مورد سوال دومت L1 اگه غیر تهی باشه و L2 یک زبان تهی، صد درصدconcatenation یا الحاقشون می شه اونی که غیر تهی هست.(یعنی L1 در اینجا)
==
موفق باشی.
اینم یه تصویر و یه نکته در مورد الحاق