Магазинный автомат - Большая Энциклопедия Нефти и Газа, статья, страница 4
"Я люблю путешествовать, посещать новые города, страны, знакомиться с новыми людьми."Чингисхан (Р. Асприн) Законы Мерфи (еще...)

Магазинный автомат

Cтраница 4


Мы анализируем вычислительную сложность определения того, является ли выполнимой формула F классического исчисления предикатов, удовлетворяющая определенным синтаксическим ограничениям. Нижние границы устанавливаются с использованием проблем допустимости для машин Тьюринга с ограниченным временем работы, альтернирующих магазинных автоматов и стековых автоматов.  [46]

Ограничения, накладываемые на вид машин или грамматик, порождающих языки, определяют классы языков. Традиционными классами языков являются: регулярный, контекстно-свободный, контекстно-связанный и языки типа 0, соответствующие конечным автоматам, магазинным автоматам, линейно-ограниченным автоматам и машинам Тьюринга. Каждый из классов языков порождается соответствующим классом автоматов. Это дает прекрасные средства для установления связи теории сетей Петри с теорией формальных языков: мы определяем класс языков сетей Петри как класс языков, порождаемых сетями Петри. Детали этого определения аналогичны деталям определения любого другого класса языков.  [47]

Нетрудно установить, что рекурсивная сеть эквивалентна магазинному автомату. Обратное утверждение, что каждый магазинный автомат имеет эквивалентную ему рекурсивную сеть, может быть доказано непосредственно, но проще доказать это, заметив, что каждый магазинный автомат имеет эквивалентную КС-грамматику, для которой имеется эквивалентная рекурсивная сеть.  [48]

У вертикальных станков масса, жесткость и мощность больше, чем у горизонтальных. Они предназначаются для обработки деталей большого диаметра и относительно небольшой длины. Токарные прутковые автоматы обрабатывают детали из прутка и тр-убы, магазинные автоматы - детали из точных штучных заготовок. На токарных полуавтоматах обрабатывают детали из штучных заготовок ( отливки, поковки, штамповки) или из заготовок, отрезанных от прутка или трубы. Токарные автоматы применяют для обработки ответственных крепежных деталей ( винты, гайки, шпильки), втулок, валиков, колец, роликов, ручек и других деталей, обычно изготовляемых из прутка или трубы, а в последнее время - и из штучных заготовок. На токарных полуавтоматах обрабатывают детали из штучных заготовок. Точность обработки на этих автоматизированных станках зависит от типа станка и инструмента.  [49]

Мы сводим к проблеме выполнимости для этого класса проблему о недопускании альтернирующим магазинным автоматом входного слова: согласно результатам из разд. Согласно утверждению 2.4, множество 2 - 5 также принадлежит DEXPTIME, а согласно утверждению 2.2, существует альтернирующий магазинный автомат, который допускает Е - S.  [50]

Этот подход тесно связан с параллельным аксиоматическим изучением семейств акцепторов. Например, как мы видели, исследование семейств рациональных языков прямо связано с исследованием соответствующих конечных автоматов. Аналогично, в теории алгебраических языков весьма важным инструментом служат соответствующие акцепторы, называемые автоматами с магазинной памятью или просто магазинными автоматами.  [51]

Нетрудно установить, что рекурсивная сеть эквивалентна магазинному автомату. Обратное утверждение, что каждый магазинный автомат имеет эквивалентную ему рекурсивную сеть, может быть доказано непосредственно, но проще доказать это, заметив, что каждый магазинный автомат имеет эквивалентную КС-грамматику, для которой имеется эквивалентная рекурсивная сеть.  [52]



Страницы:      1    2    3    4