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

دو گزاره درموردطول پشته ی pdaها

ارسال:
  

pooyaa پرسیده:

دو گزاره درموردطول پشته ی pdaها

سلام

درستی گزاره های زیر رو میخواستم:
۱-اگر یک pda برای هرورودی کمتر از n حرف در پشته اش push کند آنگاه زبانی که میپذیرد منظم است.
۲-اگر یک pda برای هرورودی بطول n کمتر از n حرف در پشته اش push کند آنگاه زبانی که میپذیرد منظم است.

۲
ارسال:
  

MiladCr7 پاسخ داده:

RE: دو گزاره درمورد pdaها

سلام ببخشید البته خود اساتید هستند ولی چون قبلا این سوالو دیدم گفتم مثالشم خدمتتون بگم

توی علوم کامپیوتر ۹۰ یه سوال اومده درستی یا نادرستی ۴ تا عبارت رو خواسته که یکی از گزینه ها این هستش:

اگر یک [tex]PDA[/tex] برای هر ورودی به طول [tex]n[/tex]، کمتر از [tex]n[/tex] حرف در پشته اش [tex]Push[/tex] کند، ان گاه زبانی که میپذیرد منظم است.
میگیم اشتباهه. چون زبانی مثل [tex]L=\{a^pb^pcca^mb^k|p,m,k>=0\}[/tex] که نامنظم و مستقل از متن هستش برای هر ورودی به طول [tex]n[/tex]، نیازی نداره که [tex]n[/tex] حرف رو تو پشته [tex]Push[/tex] کنه

۲
ارسال:
  

Jooybari پاسخ داده:

RE: دو گزاره درمورد pdaها

سوال گفته کمتر از n حرف که طول رشتست رو پوش کنه. اگه این مقدار وابسته به n نباشه منظمه. ولی اگه به n وابسته باشه مثلاً n/2 یا n/5 یا هر مقدار دیگه مستقل از متن میشه.

۱
ارسال:
  

Jooybari پاسخ داده:

RE: دو گزاره درمورد pdaها

سلام.
در مورد سوال ۱ اگه منظورتون اینه که از یه حافظه محدود و مستقل از طول رشته استفاده کنیم زبان منظم میشه.
سوال ۲ منظم نیست.

ارسال:
  

fatemeh69 پاسخ داده:

RE: دو گزاره درمورد pdaها

(۰۷ بهمن ۱۳۹۳ ۰۱:۱۰ ق.ظ)Jooybari نوشته شده توسط:  سلام.
در مورد سوال ۱ اگه منظورتون اینه که از یه حافظه محدود و مستقل از طول رشته استفاده کنیم زبان منظم میشه.
سوال ۲ منظم نیست.

چطور می شه اثیات کرد که سوال ۲ منظم نیست؟
یافتن تمامی ارسال‌های این کاربر



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  استفاده از پشته armiii ۰ ۹۱۲ ۰۳ دى ۱۴۰۰ ۱۲:۴۳ ق.ظ
آخرین ارسال: armiii
  حداقل اندازه پشته Mr.R3ZA ۰ ۱,۴۸۵ ۱۰ تیر ۱۳۹۷ ۰۲:۳۰ ق.ظ
آخرین ارسال: Mr.R3ZA
  موارد صف پشته و لیست پیوندی و.. در برنامه نویسی هم کاربرد داره؟ R.g- ۳ ۲,۶۴۴ ۰۵ شهریور ۱۳۹۶ ۰۱:۲۳ ق.ظ
آخرین ارسال: R.g-
  روش های بهبود زمان و فضا در مرتب سازی سریع از طریق کاستن عمق پشته بازگشت shamim1395 ۱ ۱,۷۵۱ ۰۳ بهمن ۱۳۹۵ ۰۲:۲۱ ب.ظ
آخرین ارسال: Saman
Thumbs Up سوال از استنتاج در منطق گزاره‌ای (کنکور ۹۴) رضا ۱۳۷۰ ۷ ۴,۶۳۴ ۱۶ خرداد ۱۳۹۵ ۰۱:۲۶ ق.ظ
آخرین ارسال: Jooybari
  ماشین پشته ای تقویت شده Baranmalihe ۱ ۱,۸۷۸ ۱۴ اسفند ۱۳۹۴ ۰۹:۳۴ ب.ظ
آخرین ارسال: RinoOo
  سوال منطق گزاره ای - کامپیوتر ۸۶ Nesyan ۰ ۱,۴۸۷ ۲۹ بهمن ۱۳۹۴ ۰۲:۲۱ ب.ظ
آخرین ارسال: Nesyan
  انتقال عناصر پشته به ترتیب(راهنمایی لطفااا) shirin0101 ۲ ۲,۸۳۰ ۲۵ دى ۱۳۹۴ ۱۱:۱۲ ق.ظ
آخرین ارسال: shirin0101
  سوال ۱۲۰ مهندسی کنکور ۹۲ ( گزاره ضعیف) shamim_s ۱ ۱,۹۴۷ ۰۹ بهمن ۱۳۹۳ ۰۷:۵۴ ب.ظ
آخرین ارسال: artmiss
  درستی چند گزاره در موردزبانهای منظم ؟(زیرمجموعه ) pooyaa ۲ ۲,۲۷۵ ۰۳ بهمن ۱۳۹۳ ۱۲:۲۴ ق.ظ
آخرین ارسال: pooyaa

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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