Общий вид цепочек А-языков

ЯЗЫКОВ

СВОЙСТВА АВТОМАТНЫХ И КОНТЕКСТНО-СВОБОДНЫХ

Упражнения.

4.1. В грамматике

S ® abAcDkY

A ® nmDky ½ vaxYe ½ jab

D ® ghYo ½ kh

Y ® f ½ d

устраните правила

A ® nmDky ½ vaxYe ½ jab

D ® ghYo ½ kh

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

4.2. Исключите тупики из следующих грамматик:

(а)

S ® aBcD ½ kLMp L ® f M

B ® cLpDq ½ pDc ½ f M ® Lk ½ pMLc

D ® f Dr ½ f pq K ® r F

F ® abc ½ ab

(б)

S ® AB ½ BC ½ kL A ® aA ½ bL ½ c

B ® BS ½ AL L ® cB ½ j ½ p

C ® QS ½ dC Q ® qQ ½ aC

M ® xN ½ yM ½ zS ½ h N ® xC ½ v ½ wM

(в)

S ® BA ½ CB ½ AL C ® QS ½ dC

A ® aA ½ bB ½ cC Q ® qQ ½ aC

B ® BS ½ AL ½ g M ® xN ½ yM ½ zS ½ h

L ® cB ½ jC ½ p N ® xC ½ v ½ wM

4.3. Устраните аннулирующие правила из следующих грамматик:

(а)

S ® abCDe ½ Kp

C ® dSde ½ e

D ® dD ½ DD ½ e ½ f K ½ e

K ® e ½ mcf

(б)

S ® aSbS ½ bSaS ½ e

(в)

S ® ABC A ® BB ½ e

B ® CC ½ a C ® AA ½ b

4.4. Устраните цепные правила из грамматики

E ® E+T ½ T

T ® T * F ½ F

F ® (E) ½ a

4.5. Найдите приведенную грамматику, эквивалентную грамматике

S ® A ½ B A ® C ½ D

B ® D ½ E C ® S ½ a ½ e

D ® S ½ b E ® S ½ c ½ e

4.6. Устраните левую рекурсию в следующих грамматиках:

(а)

E ® E+T ½ E-T ½ T ½ -T

T ® T * F ½ T / F ½ F

F ® (E) ½ a

(б)

S ® AB

A ® Aa ½ Ab ½ d ½ e

B ® qK ½ rB ½ Bf ½ Bg

K ® vS ½ w

В этом разделе мы исследуем некоторые из основных свойств А- и КС-языков. Упомянутые здесь результаты образуют малую долю огромного богатства знаний об этих языках. Часть свойств этих языков уже были рассмотрены в разделах 1-4. Ниже мы обсудим общий вид цепочек этих языков, неоднозначность КС-грамматик и КС-языков, некоторые операции, относительно которых замкнуты классы А- и КС-языков.

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

Теорема 5.1. Пусть L - А-язык. Существует такая константа p, что, если y Î L и ½y½³ p, то цепочку y можно записать в виде abg, где 0 <½b½£ p и ab ⁱg Î L, для всех i ³ 0.

Доказательство. Если L - конечный язык, то положим константу p больше длины самой длинной цепочки языка L, тогда ни одна из цепочек языка не удовлетворяет условиям теоремы и она верна. В противном случае, пусть M = (Q,S, d, q₀, F) - конечный автомат с n состояниями и L(M) = L. Пусть p = n. Если y Î L и ½ y ½ ³ n, рассмотрим последовательность конфигураций, которую проходит автомат M, допуская цепочку y. Так как в этой последовательности, по крайней мере, n+1 конфигурация, то найдутся две конфигурации с одинаковыми состояниями. Поэтому, должна быть такая последовательность тактов, что

(q ₀, abg) ú¾^* (q ₁, bg) ú¾ ^k (q ₁, g) ú¾^* (q ₂, e),

для некоторого q ₁ и 0 < k £ n. Отсюда 0 <½b½£ n.

Но тогда, для любого i > 0 автомат может проделать следующую последовательность тактов:

(q ₀, ab ⁱ g) ú¾^* (q ₁, b ⁱ g)

(q ₁, b ⁱ g) ú¾ ⁺ (q ₁, b ^i-1 g)

..............

(q ₁, b ² g) ú¾ ⁺ (q ₁, bg)

(q ₁, bg) ú¾ ⁺ (q ₁, g)

(q ₁, g) ú¾^* (q ₂, e).

Для случая i = 0 все еще очевиднее:

(q ₀, ag) ú¾^* (q ₁, g) ú¾^* (q ₂, e)

Так как abg Î L, то и ab ⁱ g Î L, для всех i ³ 0. š

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

Следствие 5.1. Язык L, состоящий из цепочек x ⁿ y ⁿ не является автоматным языком.

Допустим, что он автоматный. Тогда, для достаточно большого n цепочка x ⁿ y ⁿ может быть представлена в виде abg, причем b ¹ e и ab ⁱ g Î L, для всех i ³ 0.

Если b = x...x или b = y...y, то ag = ab ⁰ g Ï L, так как количество символов x и y в цепочке ag различно. Если b = x...xy...y, то abbg = ab ²g Ï L, так как в цепочке abbg символы x и y будут перемешаны. Полученное противоречие, доказывает, что L - не является А-языком. š

Следствие 5.2. Язык арифметических выражений не является А-языком, так как он может содержать произвольное количество вложенных скобок, причем количество открывающих скобок совпадает с количеством закрывающих. Аналогично, не является А-языком любой язык, содержащий вложенные конструкции, типа фигурных скобок в языке C, begin - end, repeat - until и т.п. Каждая конечная А-грамматика, порождающая подобные конструкции, будет выводить и цепочки с неравным количеством открывающих и закрывающих скобок. Тем не менее, анализировать подобные цепочки можно и с помощью автоматного подхода. При этом, в синтаксисе языка допускается произвольное количество открывающих и закрывающих скобок, а контроль их парности возлагается на семантические подпрограммы. š

Дата добавления: 2015-06-27