Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

Строго регулярные грамматики [ править ]

Правая кнопка регулярная грамматика (также называется правым линейная грамматика ) является формальной грамматикой ( 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, а ε - пустая строка.

Регулярная грамматика является левой регулярной или правым регулярной грамматикой.

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

Расширенные регулярные грамматики [ править ]

Расширенное право-регулярная грамматика является один , в котором все правила ПОВИНУЕТСЯ один из

  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 → aS
S → bA
A → ε
А → сА

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

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

S → A
А → а
А → Б
B → bC
C → ε
С → сС

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

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

S → + А      А → 0А      В → 0С      С → 0С      D → + E      E → 0F      F → 0F
S → -AА → 1АБ → 1СС → 1СD → -EE → 1FF → 1F
S → AА → 2АВ → 2СС → 2СD → EE → 2FF → 2F
А → 3АВ → 3СС → 3СE → 3FF → 3F
А → 4АВ → 4СС → 4СE → 4FF → 4F
А → 5АВ → 5СС → 5СE → 5FF → 5F
А → 6АВ → 6СС → 6СE → 6FF → 6F
А → 7АВ → 7СС → 7СE → 7FF → 7F
А → 8АВ → 8СС → 8СE → 8FF → 8F
А → 9АВ → 9СС → 9СE → 9FF → 9F
А → .BC → eDF → ε
А → БC → ε

Выразительная сила [ править ]

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

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

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

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

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

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

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

S → aA
А → Sb
S → ε

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

См. Также [ править ]

Ссылки [ править ]

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