аспирант физико-математических наук;
graduate student of physical and mathematical sciences;
В статье рассматривается задача сокращения количества состояний распознавателя с магазинной памятью за счет исключения лишних переходов, которые никогда не срабатывают, и исключения лишних состояний, в которых не может оказаться распознаватель в процессе обработки допустимой цепочки. Предлагается алгоритм поиска лишних переходов и состояний, основанный на представлении распознавателя в виде графа. Приводится пример распознавателя, в котором предложенный алгоритм устраняет лишние переходы и состояния. Этот алгоритм не гарантирует исключения всех лишних переходов и состояний. Приводится пример распознавателя с лишними переходами и состояниями, которые не обнаруживаются алгоритмом. Предложенный алгоритм может быть использован при разработке программ обработки формальных языков
The article considers the problem of reducing the number of states of the pushdown recognizer by eliminating unnecessary transitions that never work, and eliminating unnecessary states in which cannot be recognizer in processing a valid chain. There are suggested a search algorithm of unnecessary transitions and states, based on the representation of recognizer as a graph. The article demonstrates the example of recognizer in which the proposed algorithm eliminates unnecessary transitions and states. This algorithm does not guarantee elimination of all unnecessary transitions and states. The article demonstrates the example of recognizer with unnecessary transitions and states that are not detected by the algorithm. The proposed algorithm can be used at software design the processing for formal languages.