آتاماتای خطی کران دار. در علوم کامپیوتر، آتاماتای خطی کران دار (به انگلیسی: Linear Bounded Automata) یک شکل محدود شده ماشین تورینگ نامعین است.
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): ۲۰۷–۲۲۳ (۱۹۶۴
در سال ۱۹۶۰ جان میهیل یک مدل آتاماتا را که امروز با نام آتاماتای خطی کران دار معین شناخته می شود معرفی کرد. کمی بعد از آن، لندوبر اثبات کرد که زبان های پذیرفته شده در آتاماتاهای خطی کران دار معین حساس به متن هستند. در ۱۹۶۴ اس. وای. کوردا مدل عمومی تری از آتاماتای خطی کران دار (نامعین) را معرفی کرد، و اظهار کرد که اثبات لندوبر برای آتاماتای خطی کران دار نامعین هم کار می کند، و نشان داد که زبان های پذیرفته شده توسط آن ها قطعاً زبان های حساس به متن هستند.
آتاماتای خطی کران دار باید سه شرط زیر را داشته باشد:
همانطور که در تعریف ماشین های تورینگ آمده است، آن ها یک نوار تشکیل شده از سلول هایی که شامل نمادهایی از الفبای متناهی، یک راس که می تواند از سلول دیگر هم زمان بخواند یا بنویسد و می تواند حرکت کند، و یک عدد متناهی که نمایان گر حالات است، تشکیل شده است. با ماشین تورینگ در این تفاوت دارد که با اینکه در ابتدا کران نوار نامحدود فرض می شود، تنها یک مقدار پیوسته محدودی از نوار که طولش یک تابع خطی از طول ورودی ابتدایی است، می تواند با راس خواندن / نوشتن مورد دسترسی قرار گیرد. به جای داشتن یک نوار نامحدود مورد نیاز برای محاسبه، محاسبات تنها به قسمتی از نوار که شامل ورودی به اضافه دو خانه نوار که آخرین نشانه ها در آنجا قرار دارند محدود می شود. از آنجایی که اندازه نوار قابل دسترس به چند تابع خطی از ورودی محدود شده است، آتاماتای خطی کران دار از لحاظ محاسباتی با یک ماشین تورینگ نامعین محدودشده به قسمتی از نوار که شامل ورودی است معادل است، بنابراین نامش آتاماتای خطی کران دار شده است.
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): ۲۰۷–۲۲۳ (۱۹۶۴
در سال ۱۹۶۰ جان میهیل یک مدل آتاماتا را که امروز با نام آتاماتای خطی کران دار معین شناخته می شود معرفی کرد. کمی بعد از آن، لندوبر اثبات کرد که زبان های پذیرفته شده در آتاماتاهای خطی کران دار معین حساس به متن هستند. در ۱۹۶۴ اس. وای. کوردا مدل عمومی تری از آتاماتای خطی کران دار (نامعین) را معرفی کرد، و اظهار کرد که اثبات لندوبر برای آتاماتای خطی کران دار نامعین هم کار می کند، و نشان داد که زبان های پذیرفته شده توسط آن ها قطعاً زبان های حساس به متن هستند.
آتاماتای خطی کران دار باید سه شرط زیر را داشته باشد:
همانطور که در تعریف ماشین های تورینگ آمده است، آن ها یک نوار تشکیل شده از سلول هایی که شامل نمادهایی از الفبای متناهی، یک راس که می تواند از سلول دیگر هم زمان بخواند یا بنویسد و می تواند حرکت کند، و یک عدد متناهی که نمایان گر حالات است، تشکیل شده است. با ماشین تورینگ در این تفاوت دارد که با اینکه در ابتدا کران نوار نامحدود فرض می شود، تنها یک مقدار پیوسته محدودی از نوار که طولش یک تابع خطی از طول ورودی ابتدایی است، می تواند با راس خواندن / نوشتن مورد دسترسی قرار گیرد. به جای داشتن یک نوار نامحدود مورد نیاز برای محاسبه، محاسبات تنها به قسمتی از نوار که شامل ورودی به اضافه دو خانه نوار که آخرین نشانه ها در آنجا قرار دارند محدود می شود. از آنجایی که اندازه نوار قابل دسترس به چند تابع خطی از ورودی محدود شده است، آتاماتای خطی کران دار از لحاظ محاسباتی با یک ماشین تورینگ نامعین محدودشده به قسمتی از نوار که شامل ورودی است معادل است، بنابراین نامش آتاماتای خطی کران دار شده است.
wiki: آتاماتای خطی کران دار