موضوع مقاله: آتاماتای خطی کران‌دار | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # آتاماتای خطی کران‌دار | مقدمه: در علوم کامپیوتر، آتاماتای خطی کران‌دار یک شکل محدود شده ماشین تورینگ نامعین است. | ## بخش 1: آتاماتای خطی کران‌دار | تاریخچه در سال ۱۹۶۰ جان میهیل یک مدل آتاماتا را که امروز با نام آتاماتای خطی کران‌دار معین شناخته می‌شود معرفی‌کرد. کمی بعد از آن، لندوبر اثبات کرد که زبان‌های پذیرفته شده در آتاماتاهای خطی کران‌دار معین حساس به متن هستند. کوردا مدل عمومی‌تری از آتاماتای خطی کران دار (نامعین) را معرفی کرد، و اظهار کرد که اثبات لندوبر برای آتاماتای خطی کران‌دار نامعین هم کار می‌کند، و نشان‌داد که زبان‌های پذیرفته‌شده توسط آن‌ها قطعاً زبان‌های حساس به متن هستند. عملیات آتاماتای خطی کران‌دار باید سه شرط زیر را داشته باشد: الفبای ورودی شامل دو نماد خاص است، که به عنوان دو آخرین نشانه‌های چپ و راست عمل می‌کنند. گذارهای آن ممکن است که به سمت چپ آخرین نشانه چپ یا سمت راست آخرین نشانه سمت راست حرکت نکند. همانطور که در تعریف ماشین‌های تورینگ آمده‌است، آن‌ها یک نوار تشکیل‌شده از سلول‌هایی که شامل نمادهایی از الفبای متناهی، یک راس که می‌تواند از سلول دیگر هم‌زمان بخواند یا بنویسد و می‌تواند حرکت کند، و یک عدد متناهی که نمایان‌گر حالات است، تشکیل شده‌است. | ## بخش 2: آتاماتای خطی کران‌دار | با ماشین تورینگ در این تفاوت دارد که با اینکه در ابتدا کران نوار نامحدود فرض می‌شود، تنها یک مقدار پیوسته محدودی از نوار که طولش یک تابع خطی از طول ورودی ابتدایی است، می‌تواند با راس خواندن / نوشتن مورد دسترسی قرار گیرد. به جای داشتن یک نوار نامحدود مورد نیاز برای محاسبه، محاسبات تنها به قسمتی از نوار که شامل ورودی به اضافه دو خانه نوار که آخرین نشانه‌ها در آنجا قرار دارند محدود می‌شود. از آنجایی که اندازه نوار قابل‌دسترس به چند تابع خطی از ورودی محدود شده‌است، آتاماتای خطی کران‌دار از لحاظ محاسباتی با یک ماشین تورینگ نامعین محدودشده به قسمتی از نوار که شامل ورودی است معادل است، بنابراین نامش آتاماتای خطی‌کران دار شده‌است. این محدودیت باعث می‌شود تا آتاماتاهای خطی کران‌دار به یک مدل دقیق‌تر کامپیوترها از چیزی که حقیقتاً در یک ماشین تورینگ وجود دارد تبدیل شود، که تعریفش به عنوان یک نوار نامحدود در نظر گرفته می‌شود. آتاماتاهای خطی کران‌دار و زبان‌های حساس به متن آتاماتاهای خطی کران‌دار پذیرنده زبان‌های حساس به متن هستند. تنها محدودیتی که دراین گرامرها گذاشته می‌شود این است که این زبان‌ها هیچ ساختار تولیدی برای تبدیل یک رشته به یک رشته کوچکتر را ندارد. | ## بخش 3: آتاماتای خطی کران‌دار | بنابراین هیچ اشتقاقی از یک رشته در زبان حساس به متن نمی‌تواند یک صورت جمله‌ای طولانی‌تر ازخود رشته را داشته‌باشد. بنابراین یک رابطه یک به یک بین آتاماتای خطی کران‌دار و این گرامرها وجود دارد، و هیچ نواری جز آن که توسط رشته اصلی پرشده‌است برای رشته‌ای که آتاماتا باید شناسایی کند نیاز نیست. مسائل آتاماتای خطی کران‌دار کوردا در مقاله اصلی خود، همچنین دو چالش تحقیقاتی را بیان کرد که بعدها به مسائل آتاماتای خطی کران‌دار معروف شدند. اولین مسئله این است که آیا کلاس زبان‌هایی که توسط آتاماتای خطی کران‌دار پذیرفته می‌شوند مساوی کلاس زبان‌های پذیرفته شده توسط آتاماتای خطی کران‌دار معین است یا نه؟ مسئله دوم آتاماتای خطی کران‌دار، این است که آیا کلاس زبان‌های پذیرفته‌شده توسط آتاماتای خطی کران‌دار تحت عمل متمم بسته است یا نه؟ | ## جمع‌بندی | اما جواب مسئله دوم آتاماتای خطی کران‌دار یک جواب مثبت است، که توسط فرضیه ایمرمن-زلپسنی بیست سال بعد از ارائه مسئله اثبات شد.