stringtranslate.com

Правильная грамматика

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

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

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

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

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

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

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

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

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

Правила обоих видов не должны смешиваться; например, грамматика с набором правил { S → aT , T → Sb , S→ε} не является регулярной и описывает язык , который также не является регулярным.

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

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

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

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

Некоторые авторы называют этот тип грамматики право-регулярной грамматикой (или право-линейной грамматикой ) [1] , а тип выше — строго право-регулярной грамматикой (или строго право-линейной грамматикой ) [2] .

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

  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 состоит из следующих правил:

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

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

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

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

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

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

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

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

С → аА
А → Сб
С → ε

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

Смотрите также

Ссылки

  1. ^ Джон Э. Хопкрофт и Джеффри Д. Ульман (1979). Введение в теорию автоматов, языки и вычисления . Чтение/MA: Addison-Wesley. ISBN 0-201-02988-X.Здесь: стр.217 (лево-, право-регулярные грамматики как подклассы контекстно-свободных грамматик ), стр.79 (контекстно-свободные грамматики)
  2. ^ Хопкрофт и Ульман 1979 (стр. 229, упражнение 9.2) называют это нормальной формой для праволинейных грамматик.
  3. ^ Хопкрофт и Ульман 1979, стр. 218-219, Теорема 9.1 и 9.2
  4. ^ Хопкрофт и Ульман 1979, стр. 229, Упражнение 9.2

Дальнейшее чтение