1610906280-c80d8404f2eaa01776b47d41b0f18e85 (824375), страница 7
Текст из файла (страница 7)
.£uqk- i -. . .¢£w1qkqk- i -. . . - i -. . .¢ ......£wsqk- i -. . .¢£vqj- i¢Тогда u ∈ R(i, k, k − 1), w1 , . . . , ws ∈ R(k, k, k − 1) и v ∈ R(k, j, k − 1). Отсюдаследует, что слово w = uw1 . . . ws v ∈ R(i, k, k − 1)R(k, k, k − 1)∗ R(k, j, k − 1).Объединяя оба случая, заключаем, что имеет место включение R(i, j, k) ⊆R(i, j, k − 1) ∪ R(i, k, k − 1)R(k, k, k − 1)∗ R(k, j, k − 1). Нетрудно проверить, чтообратное включение тоже верно.
Таким образом, мы доказали равенствоR(i, j, k) = R(i, j, k − 1) ∪ R(i, k, k − 1)R(k, k, k − 1)∗ R(k, j, k − 1).Следовательно, в силу индукционного предположения и замкнутости регулярных языков относительно объединения, конкатенации и звездочки Клини окончательно получаем, что R(i, j, k) — регулярный язык. Что и требовалось доказать.Следствие 10. Язык является регулярным тогда и только тогда, когда он является обобщенно регулярным.26Глава II. Конечные автоматы и формальные грамматикиДоказательство.
Если язык L — регулярный, то, очевидно, L — обобщенно регулярный, поскольку любое регулярное выражение является обобщенно регулярным.С другой стороны, если L — обобщенно регулярный, то, используя теорему 5 (дополнение), можно так же, как и в первой части доказательства предыдущей теоремы,показать, что L — автоматный. Следовательно, L — регулярный.Таким образом, регулярные и обобщенно регулярные выражения задают одни ите же языки.
Однако этот факт не стал поводом для прекращения изучения свойствобобщенно регулярных выражений. Более того, с обобщенно регулярными выражениями связана одна достаточно известная математическая проблема, которая имеетпростую формулировку, но до сих пор является открытой.Определение. Определим отображение sh из множества всех обобщенно регулярных выражений над алфавитом A в множество ω следующим образом:sh(∅) = 0,sh(Λ) = 0,sh(a) = 0, для любого a ∈ A,sh(αβ) = max{sh(α), sh(β)},sh(α ∪ β) = max{sh(α), sh(β)},sh(α∗ ) = sh(α) + 1,sh(α) = sh(α).Число sh(α) называется звездной высотой выражения α.Определение.
Для каждого регулярного языка L над алфавитом A определим:sh(L) = min{sh(α) | α — регулярное выражение такое, что L(α) = L},gsh(L) = min{sh(α) | α — обобщенно регулярное выражение такое, что L(α) = L}.Число sh(L) называется звездной высотой языка L, а gsh(L) — обобщенно звезднойвысотой языка L. Нетрудно видеть, что gsh(L) 6 sh(L).Пример. Найдем звездную и обобщенно звездную высоту языка L = {w ∈ {0, 1}∗ | wсодержит подслово 11}. Сначала заметим, что конкатенация и объединение конечных языков являются конечными языками.
Поэтому, в силу бесконечности языкаL, заключаем, что любое регулярное выражение, задающее L, должно содержатьзвездочку Клини. Отсюда следует, что sh(L) > 1. С другой стороны, язык L можнозадать регулярным выражением (0 ∪ 1)∗ 11(0 ∪ 1)∗ , звездная высота которого равна1.
Таким образом, sh(L) = 1.Обобщенно звездная высота gsh(L) = 0, поскольку L можно задать обобщеннорегулярным выражением ∅11∅, не содержащим звездочек Клини.Замечание. Известно, что для любого n ∈ ω существует регулярный язык L такой,что его звездная высота sh(L) = n. Однако вопрос о существовании примеров языковL таких, что gsh(L) > 1, до сих пор является нерешенным.§ 8. Определение формальных грамматик§ 8.27Определение формальных грамматикЧасто формальные языки описываются как совокупности слов, полученных с помощью правил замены одних цепочек символов на другие.
Такой подход лежит в основепонятия формальной грамматики. В отличие от конечных автоматов, формальныеграмматики не распознают слова, а порождают их. Любую формальную грамматику можно представлять как некоторый генератор языка. Запуск такого генераторапроизводится с помощью «стартового сигнала», после чего начинается порождениеслов языка. Действия генератора на каждом этапе порождения слов недетерминированны, но ограничены конечным списком правил.
Время от времени этот процесспрерывается для того, чтобы выдать очередное выходное слово. Множество всехслов, появившихся на выходе в процессе работы, образует язык, порожденный данной грамматикой. Процесс порождения слов по правилам формальной грамматикибезусловно является алгоритмическим.Пример. Термин «формальная грамматика» неслучайно имеет такое лингвистическое происхождение. Процесс порождения слов в латинском языке может служитьпримером использования некоторой формальной грамматики.Рассмотрим определенный фрагмент латинского языка, который неформальноописывается следующими правилами словообразования:1) Любое слово имеет приставку, корень, суффикс и окончание, причем они расположены в слове именно в указанном здесь порядке.2) Приставка либо отсутствует, либо присутствует в единственном числе и является элементом множества {ad, de, dis, in, prae, suc, ...}.3) В слове может быть либо один, либо два корня из множества {albi, capill,cub, fect, it, laborat, ...}.4) Суффикс либо отсутствует, либо присутствует в единственном числе и являетсяэлементом множества {bu, re, ūr, ...}.5) В слове может быть только одно окончание из множества {ā, o, ōrum, nt,s, us, ...}.Теперь перепишем правила (1)–(5) формально, используя так называемые продукции:1) (слово)−→(приставка)(корень)(суффикс)(окончание)2) (приставка)−→ Λ(приставка)−→in(приставка)−→ad(приставка)−→prae(приставка)−→de(приставка)−→suc(приставка)−→dis · · ·3) (корень)−→(корень1)(корень2) (корень2)−→ Λ(корень1)−→albi(корень2)−→albi(корень1)−→capill(корень2)−→capill(корень1)−→cub(корень2)−→cub(корень1)−→fect(корень2)−→fect······4) (суффикс)−→ Λ (суффикс)−→re(суффикс)−→bu (суффикс)−→ūr······28Глава II.
Конечные автоматы и формальные грамматики5) (окончание)−→ā(окончание)−→o(окончание)−→ōrum (окончание)−→nt(окончание)−→s(окончание)−→us······Например, процесс порождения слова albicapillus (седовласый) по данным правилам выглядит следующим образом:(слово) → (приставка)(корень)(суффикс)(окончание) →(корень)(суффикс)(окончание) → (корень1)(корень2)(суффикс)(окончание) →albi(корень2)(суффикс)(окончание) → albicapill(суффикс)(окончание) →albicapill(окончание) → albicapillus.Слово aditūrus (намеревающийся подойти) порождается так:(слово) → (приставка)(корень)(суффикс)(окончание) →ad(корень)(суффикс)(окончание) → ad(корень1)(корень2)(суффикс)(окончание) →adit(корень2)(суффикс)(окончание) → adit(суффикс)(окончание) →aditūr(окончание) → aditūrus.Слово incubus (инкуб ) порождается следующим образом:(слово) → (приставка)(корень)(суффикс)(окончание) →in(корень)(суффикс)(окончание) → in(корень1)(корень2)(суффикс)(окончание) →incub(корень2)(суффикс)(окончание) → incub(суффикс)(окончание) →incub(окончание) → incubus.Слово succubus (суккуб ) имеет схожую цепочку порождения:(слово) → (приставка)(корень)(суффикс)(окончание) →suc(корень)(суффикс)(окончание) →suc(корень1)(корень2)(суффикс)(окончание) →succub(корень2)(суффикс)(окончание) → succub(суффикс)(окончание) →succub(окончание) → succubus.Определение.
Формальной грамматикой называется упорядоченная четверка Γ =hV, T, P, Si, состоящая из следующих объектов:а) V — конечное множество нетерминальных (вспомогательных) символов;б) T — конечное множество терминальных символов такое, что V ∩ T = ∅;в) P — конечное множество продукций, т. е. цепочек вида α −→ β, где α, β ∈(V ∪ T )∗ , и в α содержится хотя бы один элемент из V ;г) S — начальный символ, S ∈ V .Определение.
Пусть Γ = hV, T, P, Si — формальная грамматика, α, β ∈ (V ∪ T )∗ .Говорят, что слово β непосредственно получается из слова α в грамматике Γ, ипишут α −→ β, если существуют слова α0 , α1 , γ, δ такие, что α = α0 γα1 , β = α0 δα1 ,Γи продукция γ −→ δ принадлежит множеству P .§ 8. Определение формальных грамматик29Определение. Говорят, что слово β выводимо из слова α в грамматике Γ, и пишут∗α −→ β, если существует конечная последовательность слов β0 , . .
. , βk такая, чтоΓβk = β и имеет местоα −→ β0 −→ β1 −→ . . . −→ βk .ΓΓΓΓ(∗)Цепочка (∗) называется выводом слова β из слова α в грамматике Γ.Определение. Пусть Γ = hV, T, P, Si — формальная грамматика. Язык L(Γ) = {w ∈∗T ∗ | S −→ w} называется языком, порожденным грамматикой Γ.ΓПример.
Вернемся к предыдущему примеру. С формальной точки зрения в даннойграмматике множество нетерминальных символов имеет вид V = { (слово), (приставка), (корень), (корень1), (корень2), (суффикс), (окончание) }, множеством терминальных символов является множество T = { ad, de, dis, in, prae, suc, albi,capill, cub, bu, ūr, ā, nt, o, . . .}. Продукциями являются цепочки из пунктов(1)–(5). Начальный символ — это символ (слово).Пример.
Рассмотрим теперь пример формальной грамматики, которая порождаетязык всех десятичных записей натуральных чисел в алфавите из десяти терминальных цифр T = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Каждая запись натурального числа есть либо0, либо получается приписыванием ненулевой цифры слева к некоторой последовательности цифр. В свою очередь каждая последовательность цифр есть либо пустоеслово Λ, либо получается приписыванием любой цифры (включая 0) слева к некоторому слову, про которое уже известно, что оно является последовательностью цифр.Эти рассуждения позволяют формально выписать множество продукций P :S −→ 0S −→ 1AS −→ 2A···S −→ 9AA −→ ΛA −→ 0AA −→ 1A···A −→ 9AТаким образом, алфавит нетерминальных символов V = {S, A} состоит из двух букв.Символ S — начальный, он соответствует термину «запись натурального числа».Символ A соответствует термину «последовательность цифр».Определение (типы грамматик).
Формальная грамматика Γ = hV, T, P, Si называется:а) неукорачивающей, если для любой ее продукции α → β выполняется |α|6|β|;б) контекстно-свободной, если все ее продукции имеют вид A −→ β, где A ∈ V ,β ∈ (V ∪ T )∗ , |β| > 1;в) регулярной, если все ее продукции имеют вид A −→ aB или A −→ a, гдеA, B ∈ V , a ∈ T .Замечание. Любая регулярная грамматика является контекстно-свободной.
Любаяконтекстно-свободная грамматика является неукорачивающей. Регулярные грамматики также иногда называют праволинейными, поскольку при порождении слов в таких грамматиках каждый новый терминальный символ появляется справа от предыдущего, т. е. слово порождается слева направо.30Глава II. Конечные автоматы и формальные грамматики§ 9.Свойства формальных грамматикКак было замечено выше, в регулярных грамматиках слова порождаются слева направо без возможности возврата в начальные символы слова. Иначе говоря, если напромежуточном шаге было выведено слово a1 a2 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
