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

اذهب الى الأسفل

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

پست  AdActiva في الجمعة 19 ديسمبر 2008 - 11:26

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

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

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

A formal grammar G = (N, Σ, P, S) is context-sensitive if all rules in P are of the form

αAβ → αγβ

where A ∈ N (i.e., A is a single nonterminal), α,β ∈ (N U Σ)* (i.e., α and β are strings of nonterminals and terminals) and γ ∈ (N U Σ)+ (i.e., γ is a nonempty string of nonterminals and terminals).

In addition, a rule of the form

S → λ provided S does not appear on the right side of any rule

where λ represents the empty string is permitted. The addition of the empty string allows the statement that the context sensitive languages are a proper superset of the context free languages, rather than having to make the weaker statement that all context free grammars with no →λ productions are also context sensitive grammars.


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

AdActiva
مهمان


بازگشت به بالاي صفحه اذهب الى الأسفل

؟/؟

پست  david2007 في الجمعة 19 ديسمبر 2008 - 12:58

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

david2007

تعداد پستها : 126
تاريخ التسجيل : 2008-12-02

خواندن مشخصات فردي http://haminazdki.blogfa.com

بازگشت به بالاي صفحه اذهب الى الأسفل

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

پست  حمیدرضا زواری في الجمعة 19 ديسمبر 2008 - 16:46

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

aCb → bdda

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

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

تعداد پستها : 13
تاريخ التسجيل : 2008-11-30
العمر : 32

خواندن مشخصات فردي http://360.yahoo.com/AdActivator

بازگشت به بالاي صفحه اذهب الى الأسفل

re

پست  yousefi في الجمعة 19 ديسمبر 2008 - 17:43

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

yousefi

تعداد پستها : 25
تاريخ التسجيل : 2008-12-11

خواندن مشخصات فردي

بازگشت به بالاي صفحه اذهب الى الأسفل

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

پست  Zamanian في السبت 20 ديسمبر 2008 - 4:26

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

تعداد پستها : 60
تاريخ التسجيل : 2008-11-27

خواندن مشخصات فردي

بازگشت به بالاي صفحه اذهب الى الأسفل

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

پست  Movahedi في السبت 20 ديسمبر 2008 - 6:03

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

تعداد پستها : 31
تاريخ التسجيل : 2008-11-30

خواندن مشخصات فردي

بازگشت به بالاي صفحه اذهب الى الأسفل

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

پست  yousefi في السبت 20 ديسمبر 2008 - 6:08

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

yousefi

تعداد پستها : 25
تاريخ التسجيل : 2008-12-11

خواندن مشخصات فردي

بازگشت به بالاي صفحه اذهب الى الأسفل

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

پست  Zamanian في السبت 20 ديسمبر 2008 - 11:09

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

تعداد پستها : 60
تاريخ التسجيل : 2008-11-27

خواندن مشخصات فردي

بازگشت به بالاي صفحه اذهب الى الأسفل

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

پست  حمیدرضا زواری في السبت 20 ديسمبر 2008 - 12:11

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

تعداد پستها : 13
تاريخ التسجيل : 2008-11-30
العمر : 32

خواندن مشخصات فردي http://360.yahoo.com/AdActivator

بازگشت به بالاي صفحه اذهب الى الأسفل

؟/؟

پست  david2007 في السبت 20 ديسمبر 2008 - 12:58

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

david2007

تعداد پستها : 126
تاريخ التسجيل : 2008-12-02

خواندن مشخصات فردي http://haminazdki.blogfa.com

بازگشت به بالاي صفحه اذهب الى الأسفل

؟/؟

پست  david2007 في السبت 20 ديسمبر 2008 - 13:38

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

david2007

تعداد پستها : 126
تاريخ التسجيل : 2008-12-02

خواندن مشخصات فردي http://haminazdki.blogfa.com

بازگشت به بالاي صفحه اذهب الى الأسفل

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

پست  حمیدرضا زواری في السبت 20 ديسمبر 2008 - 15:24

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

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

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

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

تعداد پستها : 13
تاريخ التسجيل : 2008-11-30
العمر : 32

خواندن مشخصات فردي http://360.yahoo.com/AdActivator

بازگشت به بالاي صفحه اذهب الى الأسفل

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

پست  Zamanian في السبت 20 ديسمبر 2008 - 16:20

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

تعداد پستها : 60
تاريخ التسجيل : 2008-11-27

خواندن مشخصات فردي

بازگشت به بالاي صفحه اذهب الى الأسفل

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

پست  حمیدرضا زواری في السبت 20 ديسمبر 2008 - 16:32

aCb → bdda
CSG هست یا نه؟
avatar
حمیدرضا زواری

تعداد پستها : 13
تاريخ التسجيل : 2008-11-30
العمر : 32

خواندن مشخصات فردي http://360.yahoo.com/AdActivator

بازگشت به بالاي صفحه اذهب الى الأسفل

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

پست  yousefi في السبت 20 ديسمبر 2008 - 16:42

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

yousefi

تعداد پستها : 25
تاريخ التسجيل : 2008-12-11

خواندن مشخصات فردي

بازگشت به بالاي صفحه اذهب الى الأسفل

؟/؟

پست  david2007 في السبت 20 ديسمبر 2008 - 16:48

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

david2007

تعداد پستها : 126
تاريخ التسجيل : 2008-12-02

خواندن مشخصات فردي http://haminazdki.blogfa.com

بازگشت به بالاي صفحه اذهب الى الأسفل

از علی به حمید

پست  david2007 في السبت 20 ديسمبر 2008 - 17:00

آقا من یه کمی با نظر خانم یوسفی موافقم
اما این قسمت هم جالبه
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.)
این رو اگر ممکنه برای من تفسیر کن . (معنیش رو بفرمایید تا با معنی که در ذهن داریم مقایسه کنیم )

david2007

تعداد پستها : 126
تاريخ التسجيل : 2008-12-02

خواندن مشخصات فردي http://haminazdki.blogfa.com

بازگشت به بالاي صفحه اذهب الى الأسفل

به به

پست  حمیدرضا زواری في السبت 20 ديسمبر 2008 - 17:57

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

تعداد پستها : 13
تاريخ التسجيل : 2008-11-30
العمر : 32

خواندن مشخصات فردي http://360.yahoo.com/AdActivator

بازگشت به بالاي صفحه اذهب الى الأسفل

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

پست  Zamanian في الأحد 21 ديسمبر 2008 - 13:37

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

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

تعداد پستها : 60
تاريخ التسجيل : 2008-11-27

خواندن مشخصات فردي

بازگشت به بالاي صفحه اذهب الى الأسفل

?/?

پست  david2007 في الأحد 21 ديسمبر 2008 - 15:05

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

david2007

تعداد پستها : 126
تاريخ التسجيل : 2008-12-02

خواندن مشخصات فردي http://haminazdki.blogfa.com

بازگشت به بالاي صفحه اذهب الى الأسفل

سلام

پست  حمیدرضا زواری في الأحد 21 ديسمبر 2008 - 16:59

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

تعداد پستها : 13
تاريخ التسجيل : 2008-11-30
العمر : 32

خواندن مشخصات فردي http://360.yahoo.com/AdActivator

بازگشت به بالاي صفحه اذهب الى الأسفل

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

پست  Zamanian في الخميس 25 ديسمبر 2008 - 14:02

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

تعداد پستها : 60
تاريخ التسجيل : 2008-11-27

خواندن مشخصات فردي

بازگشت به بالاي صفحه اذهب الى الأسفل

استاد

پست  حمیدرضا زواری في الجمعة 26 ديسمبر 2008 - 6:48

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

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

تعداد پستها : 13
تاريخ التسجيل : 2008-11-30
العمر : 32

خواندن مشخصات فردي http://360.yahoo.com/AdActivator

بازگشت به بالاي صفحه اذهب الى الأسفل

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

پست  Zamanian في الجمعة 26 ديسمبر 2008 - 7:26

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

تعداد پستها : 60
تاريخ التسجيل : 2008-11-27

خواندن مشخصات فردي

بازگشت به بالاي صفحه اذهب الى الأسفل

بازگشت به بالاي صفحه


 
صلاحيات هذا المنتدى:
شما نمي توانيد در اين بخش به موضوعها پاسخ دهيد