Кіріспе

Автоматтар теориясындағы шекті автоматтың түрі. Компьютер ғылымында, әсіресе автоматтар теориясында, екі бағытты шекті автомат – кірісті қайта оқуға мүмкіндік берілген шекті автомат.

Екі жақты детерминистік шекті автоматтары

Екі жолды детерминистік шекті автомат (2DFA) – бұл абстрактілі машина, детерминистік шекті автоматтың (DFA) жалпыланған түрі, ол бұрын өңделген символдарды қайта қарастыруға мүмкіндік береді. DFA сияқты, оның ағымдағы символға байланысты арасында өтулер болатын шекті сандағы күйлері бар, бірақ әрбір өту машинаның кірістегі орнын солға, оңға жылжытатынын немесе сол орнында қалатынын көрсететін мәнмен белгіленеді. Балама ретінде, 2DFA-ны тек оқуға арналған Тьюринг машиналары ретінде қарастыруға болады, оларда жұмыс таспасы жоқ, тек оқуға арналған кіріс таспасы бар. 2DFA-ны Рабин мен Скотт 1959 жылғы маңызды еңбегінде енгізген, олар олардың бір бағытты DFA-мен бірдей қуатқа ие екенін дәлелдеді. Яғни, 2DFA-мен танылатын кез келген формальді тілді тек әрбір символды ретпен қарап, тұтынатын DFA-мен тануға болады. DFA-лар 2DFA-ның ерекше жағдайы болғандықтан, бұл екі машинаның да реттелген тілдер класын дәл танитынын білдіреді. Дегенмен, 2DFA үшін эквивалентті DFA экспоненциалды түрде көп күйлерді қажет етуі мүмкін, бұл 2DFA-ны кейбір жалпы мәселелер үшін алгоритмдерді жүзеге асыру үшін әлдеқайда ыңғайлы етеді. 2DFA-лар сондай-ақ тек оқуға арналған Тьюринг машиналарымен тең, олар өз жұмыс таспасында тек тұрақты көлемдегі орынды пайдаланады, себебі кез келген тұрақты ақпаратты өнімдік құрылым арқылы шекті басқару күйіне енгізуге болады (жұмыс таспасы күйінің және басқару күйінің әр комбинациясы үшін күй).

Екі жақты nondeterministic шекті автоматтары

Екі жолды нондетерминистік шекті автоматта (2NFA) бірдей конфигурацияда бірнеше көшулер анықталған болуы мүмкін. Оның көшу функциясы стандартты бір жақты NFA сияқты, 2NFA егер мүмкін болатын есептеулердің кем дегенде біреуі қабылдаушы болса, жол қабылдайды. 2DFA сияқты, 2NFA да тек қана тұрақты тілдерді қабылдайды.

Екі жақты ауыспалы шекті автомат

Екі жақты ауыспалы шекті автомат (2AFA) – ауыспалы шекті автоматтың (AFA) екі жақты кеңейтімі. Оның күйлер жиынтығы:

мұнда
және күйлері экзистенциалдық, ал күйлері – универсалды деп аталады. Экзистенциалдық күйде 2AFA НФА сияқты келесі күйді белгісіздік бойынша таңдайды және егер нәтижесіндегі есептеулердің кем дегенде біреуі қабылдаса, қабылдайды. Универсалдық күйде 2AFA барлық келесі күйлерге көшеді және барлық есептеулер қабылдаса, қабылдайды.

Мемлекеттік күрделілік бойынша компромистік факторлар

Екі және бір бағытты шекті автоматтар, детерминистік және детерминистік емес, сондай-ақ кезектесіп жұмыс істейтін автоматтар, бірдей реттелген тілдер класын қабылдайды. Дегенмен, автоматтың бір түрін екінші түлге эквивалентті автоматқа түрлендіру күйлер санының өсуіне алып келеді. Christos Kapoutsis 2DFA-ны эквивалентті DFA-ға түрлендіру үшін ең нашар жағдайда күйлер қажет екенін анықтады. Егер 2DFA немесе 2NFA NFA-ға түрлендірілсе, ең нашар жағдайда қажетті күйлер саны Ladner, Lipton және Stockmeyer көрсеткендей болады. Ladner, Lipton және Stockmeyer 2AFA-ны күйлі DFA-ға түрлендіруге болатынын дәлелдеді. 2AFA-ны NFA-ға түрлендіру ең нашар жағдайда күйді қажет етеді, қараңыз Geffert және Okhotin. Кез келген 2NFA-ны күйлер санының полиномдық өсуімен 2DFA-ға түрлендіруге бола ма, жоқ па деген мәселе әлі шешілген жоқ. Бұл мәселені Sakoda және Sipser көтерді, олар оны есептеу күрделілігі теориясындағы P және NP мәселесімен салыстырды. Berman және Lingas осы мәселе мен L және NL ашық мәселесі арасындағы формалды байланысты тапты, толық ақпарат үшін Kapoutsis-ке жүгініңіз.

Тазалау автоматтары

Суап автоматтары – ерекше бір түрі 2DFA, олар кіріс жолын солдан оңға және оңнан солға кезекпен қарап, тек соңғы белгілерде ғана бағытын өзгертеді. Сипсер n күйлі NFA-мен қабылданатын, бірақ n-нен кем күйлі ешқандай суап автоматтарымен қабылданылмайтын тілдер тізбегін құрастырды.

Екі жақты кванттық шекті автоматтары

2DFA тұжырымдамасы 1997 жылы Джон Уотрустың «2 жолды кванттық шекті күйдегі автоматтардың мүмкіндіктері туралы» еңбегінде кванттық есептеуге қатысты жалпыландырылды, онда ол осы машиналар реттелмеген тілдерді тани алатынын және осылайша DFA-дан күштірек екенін көрсетті.