(۲۵ دى ۱۳۹۲ ۰۶:۴۳ ب.ظ)majidfathi69 نوشته شده توسط:  لطفا گزاره زیر را توضیح دهید.
ماشین pda مثل p را میتوان ساخت که کلیه مسیر های محاسبه برای کلیه ورودی های w نامتناهی (loop) باشند.

Sent from my C6903 using Tapatalk

سلام.
ببینید وقتی مسیری نا متناهی هستش،یعنی تعداد حروف یه رشته نا متناهی هستش،حتما حتما اگر میخوادتوسط یه pda پذیرفته بشه باید حلقه داشته باشه،چون ماشین های متناهی از حالات متناهی تشکیل شده مثلا ۵ تا q داریم،حالا اگه یه رشته بخواد ۳۰۰ حرف باشه و توسط این ماشین پذیرفته شه،باید تو یکیاز حالات یه حلقه داشته باشیم که هی بریمو برگردیم روش تا این ۳۰۰ کاراکتر یکی یکی خونده شن.
شکل ماشینو توو ذهنت بیاری متوجه میشی چی میگم
میتونم ایجوری هم بگم:
طبق اصل لانه کبوتر،اگر m جعبه داشته باشیم و n تا شی، بصورتیکه تعداد اشیا از جعبها بیشتر باشه،حداقل یکی از جعبها حاوی دوتا شی هستش...
که اگه اینو بیاریم توو ماشین متناهی،میبینیم که جعبها همون حالاتن و اشیا همون کاراکترهای رشته،پس حداقل یه حالت تکراری داریم توی پردازش رشته که این یعنی حلقه