Обычная грамматика

В теоретической информатике и теории формального языка, регулярная грамматика - это формальная грамматика, регулярная справа или слева. Каждая регулярная грамматика описывает регулярный язык.

Содержание

• 1 Строго регулярные грамматики
  • 1.1 Расширенные регулярные грамматики
• 2 Примеры
• 3 Выразительная сила
• 4 Смешивание левых и правых регулярных правил
• 5 См. Также
• 6 Ссылки

Строго регулярные грамматики

A правильная регулярная грамматика (также называемая правая линейная грамматика ) - это формальная грамматика (N, Σ, P, S) такие, что все продукционные правила в P имеют одну из следующих форм:

1. A → a, где A - нетерминальный в N и a - терминал в Σ
2. A → aB, где A и B - нетерминалы в N, а a - в Σ
3. A → ε, где A - в N и ε обозначает пустую строку, то есть строку длины 0.

В левой обычной грамматике (также называемой левой линейной грамматикой ) все правила подчиняются образует

1. A → a, где A - нетерминал в N, а a - терминал в Σ
2. A → Ba, где A и B находятся в N, а a - в Σ
3. A → ε, где A находится в N, а ε - пустая строка.

A Regular ar grammar - это правая или левая регулярная грамматика.

Некоторые учебники и статьи запрещают пустые производственные правила и предполагают, что пустая строка отсутствует в языках.

Расширенные регулярные грамматики

Расширенные правые регулярные грамматики - это такие, в которых все правила подчиняются одному из

1. A → w, где A - нетерминал в N, а w - в (возможно, пустая) строка терминалов Σ
2. A → wB, где A и B находятся в N, а w находится в Σ.

Некоторые авторы называют этот тип грамматики правильной регулярной грамматикой (или правой линейной грамматикой) и тип выше - строго правильная регулярная грамматика (или строго правая линейная грамматика).

Расширенная левая регулярная грамматика - это такая, в которой все правила подчиняются одному из

1. A → w, где A - не -терминал в N и w находится в Σ
2. A → Bw, где A и B находятся в N, а w находится в Σ.

Примеры

Пример правильной правильной грамматики G с N = {S, A}, Σ = {a, b, c}, P состоит из следующих правил

S → aS

S → bA

A → ε

A → cA

, а S - начальный символ. Эта грамматика описывает тот же язык, что и регулярное выражение a * bc *, а именно. набор всех строк, состоящий из произвольного числа "a", за которым следует один "b", за которым следует произвольное количество "c".

Несколько более длинная, но более явная расширенная правая регулярная грамматика G для того же регулярного выражения задается формулой N = {S, A, B, C}, Σ = {a, b, c}, где P состоит из следующих правил:

S → A

A → aA

A → B

B → bC

C → ε

C → cC

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

В качестве примера из области языков программирования набор всех строк, обозначающих число с плавающей запятой, может быть описан расширенной правой регулярной грамматикой G с N = {S, A, B, C, D, E, F}, Σ = {0,1,2,3,4,5,6,7,8,9, +, -,., E}, где S - начальный символ, а P состоит из следующих правила:

S → + A	A → 0A	B → 0C	C → 0C	D → + E	E → 0F	F → 0F
S → -A	A → 1A	B → 1C	C → 1C	D → -E	E → 1F	F → 1F
S → A	A → 2A	B → 2C	C → 2C	D → E	E → 2F	F → 2F
	A → 3A	B → 3C	C → 3C		E → 3F	F → 3F
	A → 4A	B → 4C	C → 4C		E → 4F	F → 4F
	A → 5A	B → 5C	C → 5C		E → 5F	F → 5F
	A → 6A	B → 6C	C → 6C		E → 6F	F → 6F
	A → 7A	B → 7C	C → 7C		E → 7F ​​	F → 7F ​​
	A → 8A	B → 8C	C → 8C		E → 8F	F → 8F
	A → 9A	B → 9C	C → 9C		E → 9F	F → 9F
	A →.B		C → eD			F → ε
	A → B		C → ε

Выразительная сила

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

Каждая строгая правильная регулярная грамматика расширяется справа, в то время как каждая расширенная правая регулярная грамматика может быть сделана строгой путем вставки новых нетерминалов, так что результат генерирует тот же язык; следовательно, расширенные правые регулярные грамматики также порождают регулярные языки. То же самое и с расширенными левыми регулярными грамматиками.

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

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

Смешивание левых и правых регулярных правил

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

Например, грамматика G с N = {S, A}, Σ = {a, b}, P с начальным символом S и правилами

S → aA

A → Sb

S → ε

генерирует $\{aibi:\; i\; \ge \; 0\}\; \{\backslash \; displaystyle\; \backslash \; \{a\; ^\; \{i\}\; b\; ^\; \{i\}:\; i\; \backslash \; geq\; 0\; \backslash \}\}$, парадигматический нерегулярный линейный язык.

См. Также

• Регулярное выражение, компактная нотация для регулярных грамматик
• Регулярная древовидная грамматика, обобщение от строк к деревьям
• Префиксная грамматика
• Иерархия Хомского
• Перрен, Доминик (1990), «Конечные автоматы», в Левен, Ян ван (редактор), Формальные модели и семантика, Справочник по теоретической информатике, B, Elsevier, стр. 1–58.
• Пин, Жан-Эрик (октябрь 2012 г.). Математические основы теории автоматов (PDF)., глава III

Ссылки