Нисходящий распознаватель с возвратом

      Комментарии к записи Нисходящий распознаватель с возвратом отключены

Этот распознаватель моделирует работу МП-автомата с одним состоянием q: R({q}, V,Z,,q,S,{q}). Автомат распознает цепочки КС-языка, заданного КС-грамматикой G(VT,VN,P,S). Входной алфавит автомата содержит терминальные символы грамматики: V=VT, а алфавит магазинных символов строится из терминальных и нетерминальных символов грамматики: Z = VTVN.

Начальная конфигурация автомата определяется так: (q,?,S) – автомат пребывает в своем единственном состоянии q, считывающая головка находится в начале входной цепочки символов ?VT*, в стеке лежит символ, соответствующий целевому символу грамматики S.

Конечная конфигурация автомата определяется так: (q,,) – автомат пребывает в своем единственном состоянии q, считывающая головка находится за концом входной цепочки символов, стек пуст.

Функция переходов МП-автомата строится на основе правил грамматики:

1. (q,?)(q,,A), AVN, ?(VTVN)*, если правило A? содержится во множестве правил Р грамматики G: A?  Р.

2. (q,)(q,a,a) aVT.

Этот МП-автомат уже был рассмотрен выше.

Работу данного МП-автомата можно неформально описать следующим образом: если на верхушке стека автомата находится нетерминальный символ А, то его можно заменить на цепочку символов ?, если в грамматике языка есть правило А?, не сдвигая при этом считывающую головку автомата (этот шаг работы называется “подбор альтернативы”); если же на верхушке стека находится терминальный символ а, который совпадает с текущим символом входной цепочки, то этот символ можно выбросить из стека и передвинуть считывающую головку на одну позицию вправо (этот шаг работы называется “выброс”). Данный МП-автомат может быть недетерминированным, поскольку при подборе альтернативы в грамматике языка может оказаться более одного правила вида А?, следовательно, тогда функция (q,,A) будет содержать более одного следующего состояния – у автомата будет несколько альтернатив.

Данный МП-автомат строит левосторонние выводы для грамматики G(VT,VN, P,S). Для моделирования такого автомата необходимо, чтобы грамматика G(VT, VN,P,S) не была леворекурсивной (в противном случае, очевидно, автомат может войти в бесконечный цикл). Поскольку, как было доказано выше, произвольную КС-грамматику всегда можно преобразовать к нелеворекурсивному виду, то этот алгоритм применим для любой КС-грамматики, следовательно, им можно распознавать цепочки любого КС-языка.

Рассмотренный МП-автомат строит левосторонние выводы и читает цепочку входных символов слева направо. Поэтому для него естественным является построение дерева вывода сверху вниз. Такой распознаватель называется нисходящим.

Решение о том, выполнять ли на каждом шаге работы МП-автомата выброс или подбор альтернативы, принимается однозначно. Моделирующий алгоритм должен обеспечивать выбор одной из возможных альтернатив и хранение информации о том, какие альтернативы на каком шаге уже были выбраны, чтобы иметь возможность вернуться к этому шагу и подобрать другие альтернативы. Такой алгоритм разбора называется алгоритмом с подбором альтернатив.

3.5.3. Распознаватель на основе алгоритма “сдвиг-свертка”

Этот распознаватель строится на основе расширенного МП-автомата с одним состоянием q: R({q},V,Z,,q,S,{q}). Автомат распознает цепочки КС-языка, заданного КС-грамматикой G(VT,VN,P,S). Входной алфавит автомата содержит терминальные символы грамматики: V=VT; а алфавит магазинных символов строится из терминальных и нетерминальных символов грамматики: Z=VTVN.

Начальная конфигурация автомата определяется так: (q,?,) – автомат пребывает в своем единственном состоянии q, считывающая головка находится в начале входной цепочки символов ?VT*, стек пуст.

Конечная конфигурация автомата определяется так: (q,,S) – автомат пребывает в своем единственном состоянии q, считывающая головка находится за концом входной цепочки символов, в стеке лежит символ, соответствующий целевому символу грамматики S.

Функция переходов МП-автомата строится на основе правил грамматики:

1. (q,A)(q,,?), АVN, ?(VTVN)*, если правило А? содержится во множестве правил Р грамматики G: А?  Р.

2. (q,a)(q,a,) aVT.

Неформально работу этого расширенного автомата можно описать так: если на верхушке стека находится цепочка символов ?, то ее можно заменить на нетерминальный символ А, если в грамматике языка существует правило вида А?, не сдвигая при этом считывающую головку автомата (этот шаг работы называется “свертка”); с другой стороны, если считывающая головка автомата обозревает некоторый символ входной цепочки а, то его можно поместить в стек, сдвинув при этом головку на одну позицию вправо (этот шаг работы называется “сдвиг” или “перенос”). Сам алгоритм, моделирующий работу такого расширенного автомата, называется алгоритмом “сдвиг-свертка” или “перенос-свертка” (по названиям основных действий алгоритма).

Данный расширенный МП-автомат строит правосторонние выводы для грамматики G(VT,VN,P,S). Для моделирования такого автомата необходимо, чтобы грамматика G(VT,VN,P,S) не содержала -правил и цепных правил (в противном случае, очевидно, автомат может войти в бесконечный цикл из сверток). Поскольку, как было доказано выше, произвольную КС-грамматику всегда можно преобразовать к виду без -правил и цепных правил, то этот алгоритм применим для любой КС-грамматики, следовательно, им можно распознавать цепочки любого КС-языка.

Этот расширенный МП-автомат строит правосторонние выводы и читает цепочку входных символов слева направо. Поэтому для него естественным является построение дерева вывода снизу вверх. Такой распознаватель называется восходящим.

Данный расширенный МП-автомат потенциально имеет больше неоднозначностей, чем рассмотренный ваше МП-автомат, основанный на алгоритме подбора альтернатив. На каждом шаге работы автомата надо решать следующие вопросы:

 что необходимо выполнять: сдвиг или свертку;

 если выполнять свертку, то какую цепочку ? выбрать для поиска правил (цепочка должна встречаться в правой части правил грамматики);

 какое правило выбрать для свертки, если окажется, что существует несколько правил вида А? (несколько правил с одинаковой правой частью).

Чтобы промоделировать работу этого расширенного МП-автомата, надо на каждом шаге запоминать все предпринятые действия, чтобы иметь возможность вернуться к уже сделанному шагу и выполнить эти же действия по-другому. Этот процесс должен повторяться до тех пор, пока не будут перебраны все возможные варианты.

Статьи к прочтению:

Распознавание речи в C#. Microsoft Speech Platform


Похожие статьи: