زمان کنونی: ۳۰ مهر ۱۳۹۷, ۰۳:۵۸ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

زبان مستقل از متن a^n b^m c^k d^p m+p=n+k

ارسال:
  

miladdn13 پرسیده:

زبان مستقل از متن a^n b^m c^k d^p m+p=n+k

a^n b^m c^k d^p
m+p=n=k
چرا زبان بالا مستقل از متنه؟یه تحلیل بدید،مثلا وقتیaرو دیدی یه Aپوش میکنیم و....
ممنون

چرا زبان a^n b^j c^n c^j مستقل از متن هست ولی این زبان نه: a^n b^j a^n b^j

۰
ارسال:
  

reyhaneh64 پاسخ داده:

RE: زبان مستقل از متن

(۱۱ دى ۱۳۹۰ ۰۱:۳۸ ب.ظ)miladdn13 نوشته شده توسط:  چرا زبان a^n b^j c^n c^j مستقل از متن هست ولی این زبان نه: a^n b^j a^n b^j

این زبانو a^n b^j c^n c^j میشه به این شکل نوشت:
a^n b^j c^j c^n
اگر a اومد که پوش میشه، b اومد پوش میشه تو استک، اگه c اومد تا موقعی که b تو استک میبینه، pop میکنیم،اگر b‌ها تموم شد و بازم c میومد، تا موقعی که استک a داره pop میکنیم. اگرc تموم شد و بازم تو استک a داشتیم که reject میشه.و همینطور حالات دیگه ای هم میشه واسه عدم پذیرش رشته در نظر گرفت.

اما تو زبان دوم نیاز به دو حافظه داریم.

۰
ارسال:
  

rezatotti پاسخ داده:

زبان مستقل از متن

البته قسمت دومش رو من یه اصلاح کنم
۲-- اگر تعداد b‌ها بیشتز از a بود به ازای هر b یک a پاپ می کنیم بعد از پاپ همه a‌ها بقیه b‌ها پوش می شود و
سپس به ازای هر C یک b از پشته pop می کنیم وقتی تعداد b‌ها تموم شد، C های باقیمانده رو push می کنیم.
در پایان به ازای هر d یک C را Pop می کنیم .
با تمام شدن رشته ،پشته هم خالی می شود و رشته پذیرفته می شه.

در مورد گزینه چهار هم که گفته:
مکمل هر زبان مستقل از متن یک زبان بازگشتی است ولی مستقل از متن نیست .

قسمت اول جمله درسته ولی وقتی می گه مستقل از متن نیست درست نیست
چون زبان های مستقل از متن تحت عمل مکمل بسته نیست ولی وجود داره زبانی که مستقل از متن باشه و مکملش هم مستقل از متن باشد .

۰
ارسال:
  

Msccom پاسخ داده:

زبان مستقل از متن

(۱۱ دى ۱۳۹۰ ۰۱:۳۸ ب.ظ)miladdn13 نوشته شده توسط:  a^n b^m c^k d^p
m+p=n=k
سوال منم هست

ارسال:
  

hadi_m پاسخ داده:

RE: زبان مستقل از متن

(۱۱ دى ۱۳۹۰ ۰۶:۵۵ ب.ظ)NoOne نوشته شده توسط:  
(11 دى ۱۳۹۰ ۰۱:۳۸ ب.ظ)miladdn13 نوشته شده توسط:  a^n b^m c^k d^p
m+p=n=k
سوال منم هست

به نظرم شکل و شمایل این زبان بیشتر به حساس به متن بخوره تا مستقل از متن .
با این حال مطمئن هستین مستقل از متنه؟

[tex]a^{n}b^{m}c^{n}d^{p} , n=p k[/tex]
یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

Msccom پاسخ داده:

زبان مستقل از متن

سوال آزمون پارسه بوده

۰
ارسال:
  

hadi_m پاسخ داده:

زبان مستقل از متن

جواب خود پارسه برای این سئوال چی بوده؟ گرامر؟ ماشین پشته ایی؟

۰
ارسال:
  

Msccom پاسخ داده:

RE: زبان مستقل از متن

چیزی ننوشته فقط نوشته میشه ماشین پشته ای واس گزینه ۳ کشید
اما بنظر من گزینه ۴ درسته


فایل‌(های) پیوست شده

۰
ارسال:
  

hadi_m پاسخ داده:

زبان مستقل از متن

لطفا دقت کنید شرط با توجه به سئوال M+P==N+K هست نه این M+P=N=K
و طبق فرامایشات دوست عزیزمون _azarbarzin این زبان مستقل از متن هست و به راحتی میتوان برای ان ماشین پشته ایی طراحی کرد اما زبان با اون شرایطی که نوشتین یک زبان حساس به متن هست وبا پشته نمیتوان شرط رو چک کرد .

ارسال: #۱۰
  

miladdn13 پاسخ داده:

RE: زبان مستقل از متن

(۱۲ دى ۱۳۹۰ ۱۲:۳۶ ب.ظ)hadi_m نوشته شده توسط:  لطفا دقت کنید شرط با توجه به سئوال M+P==N+K هست نه این M+P=N=K
و طبق فرامایشات دوست عزیزمون _azarbarzin این زبان مستقل از متن هست و به راحتی میتوان برای ان ماشین پشته ایی طراحی کرد اما زبان با اون شرایطی که نوشتین یک زبان حساس به متن هست وبا پشته نمیتوان شرط رو چک کرد .
از همه به خاطر اشتباه تایپی که کردم معذرت می خوام
یافتن تمامی ارسال‌های این کاربر

۰
ارسال: #۱۱
  

miladdn13 پاسخ داده:

زبان مستقل از متن

من ۲ رو متوجه نمیشم چه جوری وقتی هنوز پشته خالیه به ازای هر b یک a پاپ می کنیم؟مثلا وقتی داریم a^3 b^6 c^5 d^2 مااول باید a هارو ببینیم و تا a‌ها رو نبینیم که نمیتونیم سراغ b‌ها بریم

۰
ارسال: #۱۲
  

Jooybari پاسخ داده:

زبان مستقل از متن

وقتی پشته خالیه میتونیم b رو پوش کنیم. اونوقت اول c های اول رو با b های پسته میزنیم و بعد c هارو پوش میکنیم. مرحله آخر هم زدن a و c های پشته با dهاست.
میشه از گرامر هم استفاده کرد:
[tex]S \to aSd | ABC[/tex]
[tex]A \to aAb | \lambda[/tex]
[tex]B \to bBc | \lambda[/tex]
[tex]C \to cCd | \lambda[/tex]



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  چرا مستقل از متنه؟ Wa^nb^mW^R poldasht ۱۱ ۲,۷۸۹ ۱۴ بهمن ۱۳۹۳ ۰۹:۱۰ ب.ظ
آخرین ارسال: ss.hoseini
  خواص مستقل از متن maryam.roshan ۳ ۱,۸۵۷ ۱۲ بهمن ۱۳۹۳ ۱۱:۰۱ ب.ظ
آخرین ارسال: fatemeh69
  تشخیص قطعی بودن ۴ زبان مستقل از متن MR.oracle ۹ ۳,۱۰۱ ۱۲ بهمن ۱۳۹۳ ۱۲:۲۳ ب.ظ
آخرین ارسال: ریحان
  چرا عکس نقیض لم تزریق مستقل از متن نشان دهنده نامنظم بودنه؟ ریحان ۷ ۱,۸۸۸ ۱۲ بهمن ۱۳۹۳ ۱۲:۱۳ ب.ظ
آخرین ارسال: ریحان
Question تشخیص زبان های مستقل از متن Ametrine ۹ ۳,۴۸۲ ۱۲ بهمن ۱۳۹۳ ۰۱:۵۱ ق.ظ
آخرین ارسال: ریحان
  چرا n(a)=!n(b) مستقل از متن قطعیه؟ ریحان ۸ ۲,۰۵۲ ۱۱ بهمن ۱۳۹۳ ۱۱:۰۲ ب.ظ
آخرین ارسال: ریحان
  آیا این زبان مستقل از متن است؟؟ K<=max(i,j) Imankhani ۸ ۲,۴۲۳ ۱۱ بهمن ۱۳۹۳ ۰۷:۴۷ ب.ظ
آخرین ارسال: ریحان
  تشخیص اجتماع و اشتراک یک زبان جساس به متن با مستقل از متن یا منظم maryam.roshan ۱ ۱,۲۷۹ ۱۱ بهمن ۱۳۹۳ ۱۲:۴۳ ق.ظ
آخرین ارسال: fatemeh69
  آیا مستقل از متن قطعی است؟${a^mb^mc^n:0≤m≤n≤۲m\}$ archer22 ۳ ۱,۵۷۰ ۰۷ بهمن ۱۳۹۳ ۰۹:۰۲ ب.ظ
آخرین ارسال: Hamid_0311
  مشکل در تشخیص ویژگی های زبان مستقل از متن قطعی mostafa2012 ۴ ۱,۹۱۷ ۰۶ بهمن ۱۳۹۳ ۰۲:۳۲ ب.ظ
آخرین ارسال: mostafa2012

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close