Двоичный сумматор последовательного действия и сравнение на равенство

       Двоичный сумматор последовательного действия (ДСПД) – устройство, имеющие два входа на которые поступают  и  начиная с младших разрядов, а на выходе имеется двоичная запись числа .

       Входным алфавитом является набор бинарных пар вида

 и выходным алфавитом вида . Состояние автомата определяется значением переноса при сложении двоичных разрядов , если при таком сложении образовывается перенос, тогда сумматор переходит в состояние  и при отсутствии переноса .

       Устройство, в котором на входе находятся два числа  начиная со старших разрядов и при совпадении разрядов формируется выходной сигнал 0 и при несовпадении 1, называется двоичным эквивалентом. Состояние  соответствует равенство сравниваемых разрядов, иными словами, находится в том же состоянии. Если разряды различны, тогда автомат переходит в новое состояние .

       Одну и ту же цепочку можно получить, применяя правила в различных последовательностях, когда деревья выводов различны. Если на каждом шаге для однозначности в процессе вывода применять правило к самому левому или правому петерминалу в сентенциальной форме, тогда получим левосторонний и правосторонний вывод. Исходя из этого:

1. Каждому дереву соответствует один или множество выводов;

2. Каждому дереву соответствует единственный правый или единственный левый выводы;

3. Если в каждый цепочке, выводимой в данный грамматике, соответствует единственное дерево вывода, тогда такая грамматика является однозначной, следовательно в каждом правиле грамматики не более одного петерминала.

Языком  порождаемым грамматикой G является множество всех цепочек , выводимых из начальной грамматики.

       Для классификации грамматик применяют иерархию Хомского, содержащую четыре типа грамматик:

1. Правила вида , где x, y – любые цепочки терминалов и нетерминалов – 0-ой тип;

2. Правила вида , где  – 1-ый тип с фразовой структурой;

3. Правила вида , где A – нетерминал, y – любая цепочка – 2-ой тип с контекстно-зависимой фразовой структурой;

4. Автоматные грамматики вида ,  или , где A, B – нетерминалы; a, b – терминалы,  – пустая цепочка – 3-ий тип с контекстно-независимой фразовой структурой.

Каждый тип включает грамматики более высоких уровней как частные случаи.

       Для построения распознавателей грамматик часто необходимо преобразовывать правила исходной грамматики к новому виду. При этом язык, порождающий исходной и полученной грамматик, меняться не должен.

       Две грамматики эквивалентны, если они порождают один и тот же язык или одни и те же цепочки терминальных символов. Для получения эквивалентной грамматики допустимы следующие операции: удаление или добавление бесполезных нетерминалов – непродуктивных или недостижимых.

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

       Недостижимый терминал – нетерминал, который не участвует в процессе. Для поиска недостижимых нетерминалов используют свойство: если нетерминал левой части правила достижимы, тогда правило в правой части так же достижимо. Алгоритм поиска недостижимых нетерминалов:

1. Образовать одноэлементный список начального нетерминала;

2. Если во множестве P найдено правило, которое есть в списке, тогда в список добавляют все нетерминалы в его правой части.

При неизменности списка получены все достижимые нетерминалы. Не попавшие в этот список являются недостижимыми, тогда их можно исключить.

       После удаления всех непродуктивных и недостижимых нетерминалов и содержащих их правил из P получим эквивалентную грамматику, реализующую тот же язык.

       Любое регулярное множество, которое распознает конечный автомат, можно описать с помощью автоматной грамматики. Алгоритм получения грамматики конечного автомата:

1. Начальное состояние конечного автомата – начальный символ грамматики – первый нетерминал;

2. Все символы без конца цепочки – все терминальные символы грамматики;

3. Конец строки – второй нетерминальный символ;

4. Множество состояний автомата – нетерминальные символы грамматики;

5. Если в таблице переходов есть переход из A и B при входном x, тогда получаем правило ;

6. Если D – допустимое состояние автомата, тогда вводится правило , где  – пустая цепочка;

Если обработаны все непустые клетки таблицы переходов, тогда составление правил завершено.