استاد جوانبخت

سلام
استاد جوانبخت یکی از کسانی هستند که نظریه زبان ها و ماشین ها رو درس میدن
تعریف گرامر های حساس به متن از دید ایشون اینه :

طول رشته در سمت چپ نباید بیشتر از ظول رشته در سمت راست باشد به علاوه این که این گرامر ها λ ندارند

ولی در حقیقت تعریف چیز دیگه ای هست :


این فقط یک نمونه بود
از این موارد توی تک تک صفحات جزوشون هست
حالا کسی می تونه را حل ارائه بده؟

سلام بر عزیز دل .. گل خوشگل
آقا این که داره درست میگه
سمت چپ نباید بزرگتر باشه ولی میتونه کوچکتر یا مساوی باشه .. برای همین مسله است که ما اصلا در سمت راست لاندا نداریم دیه . و همچنین در همین تعریفی که اینجا اومده 3 به 3 هستند . ولی طرف راست قدرت باز شدن داره (تعمیم )و حرف استاد جوانبخت با این که درسی با ایشون ندارم درست میباشد .
حالا اگر می گفتید که این تعریف از کجا اومده خیلی خوب می شد . از روی نمونه ایی که آوردید αAβ → αγβ اینجا هر چی α داشته باشیم طرف راست هم داریم و همچنین هر چی β داشته باشیم در طرف چپ در طرف راست هم داریم مهم در قسمت γ می باشد که طبق تعریفی که ارایه کرید باعث میشود که رشته تولید بزرگتر و مساوری رشته ی طرف چپ شود .
امیدوارم درست گفته باشم .
یاعلی

فرمایش شما بسیار متین
در نگاه اول این طور که شما میگین به نظر میاد
ولی به نظر شما گرامری که به طور مثال شامل :

aCb → bdda

باشه می تونه یه حساس به متن باشه؟

در ضمن αAβ → αγβ نمونه نیست ساختار کلی هستش و یه حرف خوبی که میزنه اینه که در هر مرحله فقط یک غیر پایانی تغییر پیدا می کنه و بقیه دست نخورده میمونن
منبع مطلبی که گفتم هم اینه
Introduction to Languages and the Theory of Computation by John C. Martin
McGraw Hill 1996 2nd edition

سلام
خانم اصغري براي ما حساس به متن رو اين طوري تعريف كردن:
u---->v آنگاه طول u كوچكتر يا مساوي طول v باشد. بنابراين شامل قواعد تهي نمي باشد.
يعني قواعد گرامر زير مجموعه متناهي از رابطه ي زير است:
+(V∪Σ)* V(V∪Σ)*----> (V∪Σ)
V:nonterminal & Σ:terminal
aCb → bddaبا توجه به تعريف به نظرم اين حساس به متنه.

سلام
این گرامری که مثال زدید :aCb--->bdda در هیچ دسته بندی از گرامرها جای نمیگیرد و اصلا چنین چیزی امکان ندارد!!چون اصلا معلوم نیست چی داره به چی تبدیل میشه و همانطور که خودتان هم به درستی اشاره کردید در هر مرحله باید یکی از متغیرها به رشته ای از متغیرها و حروف الفبا تبدیل بشه.
البته من نمیدونم خانم جوان بخت در این مورد چی گفتند اما تعریفی که خانم اصغری برای ما کردند و خانم یوسفی توضیح دادند هم درسته ولی نه به معنای اینکه گرامری که شما مثال زدید حساس به متن باشه چون ایشون تاکید کردند که در سمت چپ حتما باید یک متغیر یعنی V وجود داشته باشه و این متغیر(V) است که در هر مرحله به رشته ای از متغیرها و حروف الفبا تبدیل میشه و وقتی این تبدیل صورت گرفت ، سمت راست زیر مجموعه ای از +(V U Σ) میشه.
ولی در کل مطلبی که شما نوشتید قابل فهم تر است و لی با اون چیزی که به ما گفتند فرقی ندارد.
امیدوارم کمکی بوده باشه

مي شه بيشتر توضيح بدين؟ چرا aCb → bdda نمي تونه حساس به متن باشه؟آخه طبق تعريف نمي تونه اشتباه باشه!

مگه CجزV نيست. به نظر من كه طبق تعريف درسته. aCb → bddaجاي aو b رو عوض كرده و C هم به dd تبديل شده!فقط مسئله سر اينه كه آيا ميشه چند تا كارو با هم توي يك مرحله كرد يا نه! واقعا گيج شدم!
يه مسئله : به ما گفتن cB--->Bcحساس به متنه. يعني ميشه جاهاشون فقط عوض بشه.اون وقت چه طور با اين تعريف جور در مياد؟ αAβ → αγβ

سلام
اینکه چرا حساس به متن نیست یا در هیچ گوه دیگری جای نمیگیرد به این خاطر است که به نظر من از نظر منطقی نمیتوانیم چند کارو همزمان و فقط در یک مرحله انجام دهیم چون این در ماشین ها یعنی همزمان به چند state جدید برویم، 1 حالت برای رفتن از C به dd و یک حالت برای جابه جایی a,b .
ولی در αAβ → αγβ باید ذکر شود که αوβ میتوانند باشند و میتوانند نباشند چون در مورد قانون شروع با مشکل برخورد میکنیم.
در موردcB--->Bc من فکر نمیکنم منظور این باشه که c به B و B به c تبدیل شده باشد چون c پایانه است و نمیتواند به چیزی تبدیل شود، احتمالا در این state فقط جهت خواندن عوض میشود.
نمیدونم قانع کننده بود یا نه ولی در هر صورت من فکر میکنم این دو مفهوم یکی هستند(منظورم مطلبی که آقای زواری نوشتند با مطلبی که خانم یوسفی گفتند.)

همچنان سلام
مساله بر سر این هست که خیلی موارد رو این تعریف رد می کنه ولی تعریف استاد جوانبخت اونها رو قبول می کنه
مثل مثالی که زدم
aCb → bdda
این λ نداره و سمت راست هم طول بیشتری داره
اما طبق تعریف کتاب نمیتونیم جای a و b رو عوض کنیم
یا این یکی
aCCb → acccb
که باز طبق تعریف کتاب درست نیست ولی طبق تعریف جزوه هیچ مشکلی نداره
در ضمن هیچ جای جزوه گفته نشده که در هر مرحله فقط یک nonterminal عوض میشه ولی این نتیجه تعریف کتاب هست!
شب مثال های دیگه ای غیر از حساس به متن هم میارم که جزوه اشکال داره به نظرم

با سلام
حمید جان عزیز هم تعریف شما درسته هم تعریف خانم جوانبخت هم تعریف استاد اصغری . به نظر من تعریفی که ارایه کردید اول موضوع مشکلی نداره .. در کل با بعضی از حرفای شما موافقم ولی .... میرم یه تعریف از یک کتاب دیگه بگیرم بیارم ببینم اون چی گفت وبزارم این جا تا همه ببینند . یاعلی

سلام دوباره خدمت دوستانی که آن هستند و آنان که نیستند !
یه سوال برامون پیش اومد و آن هم اینکه چرا نمتوان جای a, b را عوض نمود . مهندس زواری گفتند که در کتاب امده که نمیشود جای a, b را عوض کرد ؟ چرا نمیشود .a و b اگر در یک طرف باشند حتما باید در طرف دیگر هم قرار بگیرند .. به نظر من در تعریف کتاب این گفته شده ..ولی گفته نشده که نمی توانند جایشان با هم عوض شود .(در این مورد حرف هم دانشگاهی زمانیان رو فکر میکنم درست باشه ) .. به نظر من مشکلی برای مثال هایی که گفته شد وجود ندارد ..

عرض سلام مجدد
اول تشکر می کنم از توجهتون به مطلب
دوم هم این که در کتاب Linz هم همون تعریف غلط نوشته شده
جالب این هست که در این کتاب نوشته شده (صفحه 329): خیلی روشن نیست که چرا به این گرامر ها حساس به متن می گویند !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

در حالی که طبق تعریفی که بالا گفتم کاملا روشنه
αAβ → αγβ
α و β همان Context هستند و تغییر A مشروط به وجود در همان Context می باشد

حتما این فایل رو ببینید

در ضمن یه نگاهی هم به تعریف Context Sensitive Grammars در سایت Wikipedia بندازید

سلام دوباره
من واقعا متوجه نمیشم مشکل کجاست؟این دو تعریف دقیقا یکی هستند

aCb → bdda
CSG هست یا نه؟

سلام
به نظر من كه هست و اين دو تا تعريف مثل هم نيستن. تعريفي كه شما ارائه داديد(αAβ → αγβ) با اون چيزي كه اساتيد محترم مي گن.طبق تعريف شما اين رشته مجاز به نظر نميرسه چون توش امكان جابجايي نيست. اما ما ميدونيم كه cB--->Bc حساس به متنه! به هر حال من قول مي دم فردا از خانم اصغري بپرسم و جواب رو بذارم .

با تعریفی که شما عزیز دل گل .. عرق بیدمشک .. گل گاو زبون .. ربات پارسه .. جیگر و قلوه دادی نوچ
ولی با برداشتی که ما از تعریف شما کریدم یس
من نمیدونم آخه مشکل سر چیه هنوز ..
امابیاید بریا مثالی که دادید یک ماشین طراحی کنیم اگر درست بود برداشت ما درست اگر غلط شد تعریف هم درست و برداشت شما جای تامل بیشتری دارد .

آقا من یه کمی با نظر خانم یوسفی موافقم
اما این قسمت هم جالبه
Xb → bX
Xc → bYc
Yc → cY
Yd → Rcdd
cR → Rc
bR → Rb
aR → aaX | aa

(This grammar is not in fact context-sensitive, because of the presence of productions such as Xb → bX. However, there does exist a context-sensitive grammar for this language.)
این رو اگر ممکنه برای من تفسیر کن . (معنیش رو بفرمایید تا با معنی که در ذهن داریم مقایسه کنیم )

دقیقا منظورم این بود که به اینجا برسین
دقیقا اشاره کرده که Xb → bX نمی تونه Context Sensitive باشه ولی می شه به CS تبدیلش کرد
پس خودش CS نیست
ولی طبق تعریف اساتید این خودش CS هست

با سلام مجدد
این که Xb--->bX حساس به متن نیست ، من هم موافقم، چون با تعریف کتاب لینز هم درست نیست،چون هر بار 1 متغیر V تبدیل میشود.
ولی این که این گرامر aCb → bdda حساس به متن است یا نه همچنان معتقدم که نه تنها حساس به متن نیست بلکه جزو هیچ کدام از دسته بندی چامسکی قرار نمیگیرد، از نظر منطقی شما نمیتوانید چنین گرامری را بسازید
آیا تفسیر من از گرامر شما درست است؟ C به dd تبدیل میشود و همزمان در همین مرحله a,b جایشان عوض میشود.
شما به این موضوع دقت کردید که گرامرها بیانگر زبانها هستند؟
آن گرامری که شما نوشتید چه زبانی را توصیف میکند؟ میتواند زبانی را توصیف کند؟
بله از روی تعریفی که در کتاب لینز آمده هر گرامری را میشود مثال زد که مانند مثال شما به نظر درست باشند ولی در عمل به کار نیایند،این یک تعریف است ولی حتما باید پشت آن یک منطقی وجود داشته باشد

میخواهم این نتیجه گیری را بکنم که این بیانی که شما از گرامرهای حساس به متن نوشتید یک تعریف واضح است ولی تعریفی که در کتاب لینز آمده هم همین است.من ادعا میکنم که در این تعریف هر بار فقط V به رشته ای از الفبا و متغیر ها تبدیل میشود چراکه *(V U Σ) که در دو طرف آن هستند نمیتوانند طبق قوانین گرامر به چیزی تبدیل شوند(فقط متغیرها میتوانند به متغیر، رشته ای از متغیرها و حروف الفبا و یا فقط حروف تبدیل شوند.)
حال آیا این دو مطلب از نظر شما یکی نیستند؟

با سلام . مهندس زواری هم دانشگاهی زمانیان راست میگویند .. من هم به این نتیجه رسیدم ولی در کل من فکر میکنم یه نفر باید بره از اساتید دیگر هم سوال بکنه .. البته یه فکر دیگه ایی که میکنم اینه که همه دارن یه چیز میگن به شکل های محتلف !!
حالا کی پیدا میکند پرتغال فروش رو نمیدونم .

بازم ممنون که توجه می کنید
ممکنه خواهش کنم با ذکر شماره صفحه بفرمایید کجای Linz نوشته در هر مرحله یک حرف تغییر می کنه؟
چون خودم هنوز Linz رو نخوندم

سلام
من نگفتم کتاب لینز گفته که یک متغیر تغییر میکنه ، من از این تعریف این برداشت رو دارم و دلیلش رو هم توضیح دادم و فکر میکنم دلیلم منطقی باشه
اگر منطقی نیست لطف کنید بگید کجاش اشکال داره؟

آخه هیچ جا توی تعریف ها نیست که در هر مرحله فقط یک غیر پایانی عوض بشه
اما از تعریفی که اول نوشتم این برداشت میشه
شمام اگر جای دیگه دیدین لطفا یه توضیح بدین ممنون میشم

به هر حال از نظر من دو تا تعریف تفاوت خیلی زیاد دارند
نمی دونم دیگه !!!!!

شما بالاخره نگفتید کجای برداشت من اشتباهه؟
درسته گفته نشده ولی این مطلب ازش استنباط میشه
تعریف شما زیر مجموعه ای از تعریف لینزه که کاملتر به نظر می آد ولی اینکه چرا منم نمیدونم
فکر کنم باید از یکی از اساتید کمک بگیریم تو دانشگاه بالاخره یکی پیدا میشه که جواب بده البته اگه ما دنبالش بریم