Пред. страница   След. страница   Раздел   Содержание


2.6 Резюме

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

·                   Построение распознавателя для заданной автоматной грамматики выполняется достаточно просто путем построения диаграммы или таблицы переходов по схеме грамматики.

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

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

·                   Одним из практических применений автоматных грамматик является построение распознавателей для конечных языков.

·                   Во многих случаях число состояний распознавателей конечных языков удается сократить за счет объединения эквивалентных состояний.

 

Пред. страница   След. страница   Раздел   Содержание