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

دو گزاره درموردطول پشته ی 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 نوشته شده توسط:  سلام.
در مورد سوال ۱ اگه منظورتون اینه که از یه حافظه محدود و مستقل از طول رشته استفاده کنیم زبان منظم میشه.
سوال ۲ منظم نیست.

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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  درستی چند گزاره در موردزبانهای منظم ؟(زیرمجموعه ) pooyaa ۲ ۱,۱۰۴ ۰۳ بهمن ۱۳۹۳ ۱۲:۲۴ ق.ظ
آخرین ارسال: pooyaa
  اتومات پشته ای قطعی در حالت خالی شدن پشته - مهندسی ۸۴ Imankhani ۱ ۷۶۱ ۲۵ دى ۱۳۹۳ ۰۹:۰۷ ب.ظ
آخرین ارسال: nlp@2015
  اتومات پشته ای معین میتونید بسازید برای این زبان؟؟ Imankhani ۵ ۱,۲۴۵ ۱۵ دى ۱۳۹۳ ۰۲:۵۵ ق.ظ
آخرین ارسال: Jooybari
  گرامر مستقل از متن و ماشین پشته ای uniquegirl ۲ ۱,۲۳۲ ۱۹ خرداد ۱۳۹۳ ۰۱:۱۱ ق.ظ
آخرین ارسال: fatemeh69
  پشته در گرامر های مستقل از متن- پذیرش با خالی شدن پشته e.shrm ۱۲ ۳,۰۰۶ ۱۶ بهمن ۱۳۹۲ ۰۶:۱۵ ب.ظ
آخرین ارسال: sara_omd
  ایده کلی برای پشته زبان مستقل از متن e.shrm ۸ ۱,۹۵۷ ۱۳ دى ۱۳۹۲ ۰۵:۵۶ ب.ظ
آخرین ارسال: Jooybari
  چرا زبان ww^R توسط آتاماتای پشته ای غیرقطعی پذیرفته میشه؟؟ hnrzd65 ۸ ۲,۹۹۵ ۲۸ مهر ۱۳۹۲ ۱۱:۳۱ ب.ظ
آخرین ارسال: pamta
  اتومات پشته ای (برای a^nb^nc^n) roz1 ۷ ۲,۱۲۲ ۰۳ آذر ۱۳۹۱ ۰۲:۵۸ ب.ظ
آخرین ارسال: Jooybari
  ماشین پشته ای برای {(L = {w: Na(w) = 2Nb(w nmusavi ۳ ۲,۴۳۳ ۲۴ دى ۱۳۹۰ ۰۳:۰۵ ب.ظ
آخرین ارسال: navid-p
  ماشین پشته ای معین و نامعین f.b ۱ ۳,۷۱۴ ۱۴ دى ۱۳۹۰ ۰۱:۳۴ ب.ظ
آخرین ارسال: homa

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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