آتاماتای خطی کران‌دار
در علوم کامپیوتر، آتاماتای خطی کران‌دار (به انگلیسی: Linear Bounded Automata) یک شکل محدود شده ماشین تورینگ نامعین است.
تاریخچه
در سال ۱۹۶۰ جان میهیل یک مدل آتاماتا را که امروز با نام آتاماتای خطی کران‌دار معین شناخته می‌شود معرفی‌کرد. کمی بعد از آن، لندوبر اثبات کرد که زبان‌های پذیرفته شده در آتاماتاهای خطی کران‌دار معین حساس به متن هستند. در ۱۹۶۴ اس. وای. کوردا مدل عمومی‌تری از آتاماتای خطی کران دار (نامعین) را معرفی کرد، و اظهار کرد که اثبات لندوبر برای آتاماتای خطی کران‌دار نامعین هم کار می‌کند، و نشان‌داد که زبان‌های پذیرفته‌شده توسط آن‌ها قطعاً زبان‌های حساس به متن هستند.
عملیات
آتاماتای خطی کران‌دار باید سه شرط زیر را داشته باشد:
- الفبای ورودی شامل دو نماد خاص است، که به عنوان دو آخرین نشانه‌های چپ و راست عمل می‌کنند.
- گذارهای آن ممکن است دیگر نشانه‌های بعد از آخرین نشانه‌ها را چاپ نکند.
- گذارهای آن ممکن است که به سمت چپ آخرین نشانه چپ یا سمت راست آخرین نشانه سمت راست حرکت نکند.
همانطور که در تعریف ماشین‌های تورینگ آمده‌است، آن‌ها یک نوار تشکیل‌شده از سلول‌هایی که شامل نمادهایی از الفبای متناهی، یک راس که می‌تواند از سلول دیگر هم‌زمان بخواند یا بنویسد و می‌تواند حرکت کند، و یک عدد متناهی که نمایان‌گر حالات است، تشکیل شده‌است. با ماشین تورینگ در این تفاوت دارد که با اینکه در ابتدا کران نوار نامحدود فرض می‌شود، تنها یک مقدار پیوسته محدودی از نوار که طولش یک تابع خطی از طول ورودی ابتدایی است، می‌تواند با راس خواندن / نوشتن مورد دسترسی قرار گیرد. به جای داشتن یک نوار نامحدود مورد نیاز برای محاسبه، محاسبات تنها به قسمتی از نوار که شامل ورودی به اضافه دو خانه نوار که آخرین نشانه‌ها در آنجا قرار دارند محدود می‌شود. از آنجایی که اندازه نوار قابل‌دسترس به چند تابع خطی از ورودی محدود شده‌است، آتاماتای خطی کران‌دار از لحاظ محاسباتی با یک ماشین تورینگ نامعین محدودشده به قسمتی از نوار که شامل ورودی است معادل است، بنابراین نامش آتاماتای خطی‌کران دار شده‌است.
این محدودیت باعث می‌شود تا آتاماتاهای خطی کران‌دار به یک مدل دقیق‌تر کامپیوترها از چیزی که حقیقتاً در یک ماشین تورینگ وجود دارد تبدیل شود، که تعریفش به عنوان یک نوار نامحدود در نظر گرفته می‌شود.
آتاماتاهای خطی کران‌دار و زبان‌های حساس به متن
آتاماتاهای خطی کران‌دار پذیرنده زبان‌های حساس به متن هستند. تنها محدودیتی که دراین گرامرها گذاشته می‌شود این است که این زبان‌ها هیچ ساختار تولیدی برای تبدیل یک رشته به یک رشته کوچکتر را ندارد. بنابراین هیچ اشتقاقی از یک رشته در زبان حساس به متن نمی‌تواند یک صورت جمله‌ای طولانی‌تر ازخود رشته را داشته‌باشد. بنابراین یک رابطه یک به یک بین آتاماتای خطی کران‌دار و این گرامرها وجود دارد، و هیچ نواری جز آن که توسط رشته اصلی پرشده‌است برای رشته‌ای که آتاماتا باید شناسایی کند نیاز نیست.
مسائل آتاماتای خطی کران‌دار
کوردا در مقاله اصلی خود، همچنین دو چالش تحقیقاتی را بیان کرد که بعدها به مسائل آتاماتای خطی کران‌دار معروف شدند. اولین مسئله این است که آیا کلاس زبان‌هایی که توسط آتاماتای خطی کران‌دار پذیرفته می‌شوند مساوی کلاس زبان‌های پذیرفته شده توسط آتاماتای خطی کران‌دار معین است یا نه؟ این مسئله می‌تواند به صورت عبارت خلاصه شده در زبان با پیچیدگی محاسباتی (NSPACE(O(n)) = DSPACE(On) بیان شود.
مسئله دوم آتاماتای خطی کران‌دار، این است که آیا کلاس زبان‌های پذیرفته‌شده توسط آتاماتای خطی کران‌دار تحت عمل متمم بسته است یا نه؟ (NSPACE(O(n)) = co-NSPACE O(n)
به طوری که توسط خود کوردا مشاهده شد، جواب منفی به مسئله دوم آتاماتای خطی کران‌دار، جواب منفی مسئله اول را در برخواهدداشت. اما جواب مسئله دوم آتاماتای خطی کران‌دار یک جواب مثبت است، که توسط فرضیه ایمرمن-زلپسنی بیست سال بعد از ارائه مسئله اثبات شد. در حالی که تا سال ۲۰۱۱ مسئله اول آتاماتای خطی کران‌دار هنوز باز بود.
منابع
- John Myhill: Linearly Bounded Automata, WADD Technical Note ۶۰-۱۶۵, Wright-Patterson Air Force Base, Wright Air Development Division, Ohio, June 1960.
- (Peter S. Landweber: Three Theorems on Phrase Structure Grammars of Type 1, Information and Control 6(2): ۱۳۱-۱۳۶ (۱۹۶۳
- (Sige-Yuki Kuroda: Classes of languages and linear-bounded automata, Information and Control, 7(2): ۲۰۷–۲۲۳ (۱۹۶۴
پیوند به بیرون
- Linear Bounded Automata by Forbes D. Lewis
- Linear Bounded Automata slides, part of Context-sensitive Languages by Arthur C. Fleck
- Linear-Bounded Automata بایگانی‌شده در ۱۸ ژانویه ۲۰۲۱ توسط Wayback Machine, part of Theory of Computation syllabus, by David Matuszek