Оглавление
Обычная грамматика
-
Определение и свойства регулярных грамматик
- Регулярные грамматики описывают обычные языки и могут быть использованы для их анализа.
- Они состоят из нетерминалов, терминалов и правил, которые определяют, как создавать строки из нетерминалов и терминалов.
- Существуют различные типы регулярных грамматик, включая леворегулярные и правильнорегулярные.
-
Примеры и выразительная сила
- Примеры регулярных грамматик включают описание языка всех строк с “a” и “b” и языка чисел с плавающей запятой.
- Регулярные грамматики однозначно соответствуют детерминированным конечным автоматам, что позволяет им генерировать все обычные языки.
-
Смешивание правил
- Смешение правил левой и правой регулярности приводит к линейным грамматикам, которые могут генерировать нерегулярные языки.
-
Расширенные регулярные грамматики
- Расширенные регулярные грамматики включают правила, которые создают строки из нетерминалов и терминалов, а также правила, которые создают строки из нетерминалов и других нетерминалов.
-
Смешение правил “левый-обычный” и “правый-обычный”
- Смешение правил приводит к линейным грамматикам, которые могут генерировать нерегулярные языки, например, язык всех строк с “a” и “b”.
Полный текст статьи: