Пред. страница След. страница Раздел Содержание
2.6 Резюме
· Грамматики типа 3 называют автоматными, поскольку в качестве распознавателей цепочек, порождаемых этими грамматиками, используются конечные автоматы без выходов.
· Построение распознавателя для заданной автоматной грамматики выполняется достаточно просто путем построения диаграммы или таблицы переходов по схеме грамматики.
· Если заданная грамматика не содержит правил с одинаковой левой частью, правая часть которых начинается одинаковыми терминальными с символами, то такой грамматике соответствует детерминированный распознаватель.
· Интересным свойством А-распознавателей является то, что для любого недетерминированного распознавателя можно построить эквивалентный ему детерминированный распознаватель. Это означает, что все автоматные языки могут распознаваться с помощью детерминированных устройств.
· Одним из практических применений автоматных грамматик является построение распознавателей для конечных языков.
· Во многих случаях число состояний распознавателей конечных языков удается сократить за счет объединения эквивалентных состояний.
Пред. страница След. страница Раздел Содержание