Главная страница Случайная лекция Мы поможем в написании ваших работ! Порталы: БиологияВойнаГеографияИнформатикаИскусствоИсторияКультураЛингвистикаМатематикаМедицинаОхрана трудаПолитикаПравоПсихологияРелигияТехникаФизикаФилософияЭкономика Мы поможем в написании ваших работ! |
Недетерминированный конечный автомат
Среди правил перехода НКА для некоторых пар (a, qi) имеется по два или более правил перехода в различные новые состояния. Это значит, что КА должен на каждом шаге одновременно находиться в нескольких состояниях из всего множества возможных состояний, и каждый раз выполнять одновременный переход из всех этих состояний в новое множество состояний. Может случиться, что некоторые из возможных переходов попадают в тупики. Если же получится хотя бы один нетупиковый переход, то работа НКА продолжается. Цепочка, анализируемая НКА, считается распознанной, если она прочитана до конца, и если хотя бы одно из текущих состояний НКА является заключительным. Таким образом, недетерминированность КА, возникающая при его построении из неоднозначной А-грамматики, означает, что одновременно отслеживаются несколько вариантов грамматического разбора, и для успешного распознавания достаточно, чтобы хотя бы один вариант разбора оказался успешным. При этом количество вариантов разбора не может превышать числа всех возможных состояний НКА, т.е. числа нетерминалов в А-грамматике.
Пример 2. А-грамматика задана правилами: S → 0A| 1A, A → 0A| 1A| 0 | 1. Здесь нетерминал S – начальный. Цепочки языка, порождаемого этой грамматикой, будут состоять из последовательностей нулей и единиц длиной не менее чем 2. После изменения грамматика будет содержать правила: S → 0A| 1A, A → 0A| 1A| 0R | 1R, R → ┴. Табл. 2 содержит правила перехода НКА. Табл. 2
При поступлении на вход этого КА цепочки 010┴, состояния КА в процессе работы будут изменяться следующим образом: S, A, (A,R), (A,R), F. Здесь на 3-м шаге работы КА параллельно выполняются два действия: (0,A) → (A,R) и (0,R) → ? При этом второе действие попадает в тупик, однако работа КА продолжается, так как первое действие переводит КА опять в два состояния A и R. На 4-м шаге работы КА также параллельно выполняются два действия: (┴, A) → ?, (┴, R) → F. Первое действие приводит к тупику, а второе – к заключительному состоянию F. Так как цепочка прочитана вся, то она считается распознанной, т.е. цепочка принадлежит языку. При входной цепочке 0┴ на втором шаге из состояния A возникнет тупик: для состояния A и входного символа ┴ перехода не задано. Это значит, что такая цепочка не принадлежит языку. Аналогичная ситуация возникнет и для входной цепочки 1┴. Конец примера.
Дата добавления: 2015-07-26; просмотров: 147; Нарушение авторских прав Мы поможем в написании ваших работ! |