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

В теоретической информатике и теории формального языка регулярная грамматика — это грамматика , которая является праворегулярной или леворегулярной .Хотя их точное определение варьируется от учебника к учебнику, все они требуют, чтобы

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

Каждая регулярная грамматика описывает регулярный язык .

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

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

1. А → а
2. А → аБ
3. А → е

где A , B , S ∈ N — нетерминальные символы, a ∈ Σ — терминальный символ, а ε обозначает пустую строку , т. е. строку длины 0. S называется начальным символом.

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

1. А → а
2. А → Нет
3. А → е

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

Правила обоих видов нельзя смешивать; например, грамматика с набором правил { S → aT , T → Sb , S→ε} не является регулярной и описывает язык $\{a^{i}b^{i}:i\in \mathbb {N} \}$, что тоже не является регулярным.

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

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

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

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

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

С → А

А → аА

А → Б

Б → БС

С → е

С → СС

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

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

С → +А	А → 0А	Б → 0С	С → 0С	Д → +Е	Е → 0F	Ф → 0Ф
С → −А	А → 1А	Б → 1С	С → 1С	Д → −Е	Е → 1F	Ф → 1Ф
С → А	А → 2А	Б → 2С	С → 2С	Д → Е	Е → 2F	Ф → 2Ф
	А → 3А	Б → 3С	С → 3С		Е → 3F	Ф → 3Ф
	А → 4А	Б → 4С	С → 4С		Е → 4F	Ф → 4Ф
	А → 5А	Б → 5С	С → 5С		Е → 5F	Ф → 5Ф
	А → 6А	Б → 6С	С → 6С		Е → 6F	Ф → 6Ф
	А → 7А	Б → 7С	С → 7С		Е → 7F	Ф → 7Ф
	А → 8А	Б → 8С	С → 8С		Е → 8F	Ф → 8Ф
	А → 9А	Б → 9С	С → 9С		Е → 9F	Ф → 9Ф
	А → .Б		С → еД			Ж → е
	А → Б		С → е

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

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

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

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

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

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

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

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

С → аА

А → Сб

С → е

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

См. также

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