Лекции по теории алгоритмов. Лекция Интуитивное представление об алгоритме Интуитивное определение алгоритма. Примеры алгоритмов

• Название: Лекция Интуитивное представление об алгоритме Интуитивное определение алгоритма. Примеры алгоритмов
• Анкор: Лекции по теории алгоритмов
• Дата: 05.05.2022
• Размер: 2.84 Mb.
• Имя файла: Лекции по теории алгоритмов.doc
• Тип: Лекция; #513398
• страница: 6 из 7

Раздел 2. Формальные языки и грамматики
Лекция № 9. Иерархия формальных языков и грамматик

1. 
   Понятие формального языка
   
2. 
   Операции над языками
   
3. 
   Порождающие грамматики
   
4. 
   Иерархия языков по Хомскому
   

1. Понятие формального языка
Определение 9.1.1. Конечное непустое множество называется алфавитом, его элементы называются символами (буквами).

Определение 9.1.2. Конечная последовательность символов алфавита A называется словом в алфавите A.

Пример 9.1.1. ПустьA={а, б, в}. Тогда баба, ваб, ббб – слова в алфавите A, при этом осмысленность слов не предполагается.

Определение 9.1.3. Слово, не содержащее ни одного символа, называется пустым и обозначается .

Множество всех слов в алфавите А будем обозначать А^*, а через А⁺ – множество всех непустых слов.

Определение 9.1.4. Число символов в слове w называется длиной слова wи обозначается w. Длина пустого слова по определению равна нулю.

Определение 9.1.5. Конкатенацией слов x и y называется слово, обозначаемое как xy(или xy) и получающееся в результате приписывания слова yв конец слова x .

Если w – слово, то через wⁿ (n=1, 2, …) обозначается слово:

(при n=0 полагается, что wⁿ=), а через w_а – число вхождений буквы а в слово w.

Так как

,

а множество слов данной длины конечно, то множество А^*счетно.

Определение 9.1.6. Любое подмножество L множества А^* (L А^*) называется формальным языком (языком) над алфавитом А.

Определение 9.1.7. Язык А^*– Lназывается дополнением языкаLотносительно алфавита А.

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

Пример 9.1.1. Пусть над алфавитом А={a, b} заданы формальные языки L₁={(ab)ⁿ:n0} А^* иL₂={a^mb^m:m0}  А^*. Тогда пересечением этих языков будет язык L₁L₂={, ab} А^*.

Задача 9.1.1. Пусть над алфавитом А={a, b} заданы формальные языки L₁={w А^*:w=3} А^* иL₂={w А^*:w_а =1}  А^*. Сколько слов содержитязыкL₁ – L₂.

Решение. ЯзыкL₁ содержит 8 слов из трех букв: aaa, aab, aba, abb, baa, bab, bba, bbb. Буква а ровно один раз входит в 3 слова: abb, bab, bba. Таким образом, языкL₁ – L₂ содержит 5 слов_.
2. Операции над языками
Определение 9.2.1. Конкатенацией языков L₁, L₂ А^*называется язык L₁L₂={xy: xL₁, yL₂}.

Определение 9.2.2. Пусть LА^*. Тогда L⁰={}, L¹=L, Lⁿ⁺¹= LⁿL (n=1, 2, …).

Пример 9.2.1. Пусть А={a, b}, L={aa, ab}. Выпишем все слова языка L² в следующей таблице:

	aa	ab
aa	aaaa	aaab
ab	abaa	abab

Заметим, что L²={(aa)ⁿ(ab)^m(aa)^k: m, n0, m+n+k=2}.

Слова языка L³ могут быть получены следующим образом:

	aa	ab
aaaa	aaaaaa	aaaaab
abaa	abaaaa	abaaab
aaab	aaabaa	aaabab
abab	ababaa	ababab

Попутно заметим, что L³{(aa)ⁿ(ab)^m(aa)^k: m, n0, m+n+k=3}, поскольку ababab{(aa)ⁿ(ab)^m(aa)^k: m, n0, m+n+k=3}.

Определение 9.2.3. Итерацией языкаL называетсяязык

.
Пример 9.2.2. Если А={a, b} и L={aa, ab, ba, bb}, то:

L^*={wA^* : wmod 2=0}.

Определение 9.2.4. Обращением (зеркальным образом) слова w называется слово, записанное теми же буквами в обратном порядке (обозначается w^R).

Например, если w=abab, то w^R=baba.

Определение 9.2.5. Пусть LA^*. Тогда язык L^R={w^R :wL} называется обращением языка L.

Пример 9.2.3. Если А={a, b} и L={aa, ab, ba, bb}, то L^R=L.

Пример 9.2.4. Если А={a, b} и L={aⁿb^m:n1, m1}, то L^R={b^maⁿ:n1, m1}.

Определение 9.2.5. Пусть А₁и А₂ алфавиты. Отображение H:A₁^*A₂^*, удовлетворяющее условию H(uw)=H(u)H(w) для любых u, wA₁^*, называется гомоморфизмом (морфизмом).

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

Пример 9.2.5. Пусть А={a, b}. Определим гомоморфизм H:A^*A^* равенствами H(a)=b, H(b)=a. ТогдаH(aaabb)=bbaaaи т.д.
3. Порождающие грамматики
Определение 9.3.1. Порождающей грамматикой (грамматикой типа 0) называется четверка G=<N, A, P, S>, где:

а) N – конечный алфавит, называемый нетерминальным (вспомогательным) алфавитом, символы которого будем обозначать прописными латинскими буквами;

б) А – конечный алфавит, именуемый основным (терминальным) алфавитом, символы которого будем обозначать строчными латинскими буквами;

в) АN=;

г) P – конечное подмножество декартового произведения:

P(NA)⁺  (NA)^*,

при этом пары (, )P называются правилами подстановки (просто правилами или продукциями) и записываются в виде ;

д) S – нетерминальный символ (SN), называемый начальным символом.

Пример 9.3.1. Пусть N={S}, A={a, b}, P={SabS, Sa}. Тогда G=<N, A, P, S> – является порождающей грамматикой.

Определение 9.3.2. Пусть дана порождающая грамматика G=<N, A, P, S>. Говорят, что слово v непосредственно выводимо из слова w (пишут wv), если w=, v=принекоторыхсловах, , , в алфавитеNAиP.

Пример 9.3.2. Пусть N={S}, A={a, b}, P={SabS, Sa}. G=<N, A, P, S> –порождающая грамматика.

Тогда S abS, Sa, abSaba, abS ababS, ababSababa.

Определение 9.3.3. Пусть дана порождающая грамматика G. Говорят, что слово w_n выводимо из слова w₀ (пишутw₀ w_n), если

w₀w₁w₂…w_n(n0).

Пример 9.3.3. Пусть N={S}, A={a, b}, P={SabS, Sa}. G=<N, A, P, S> – порождающая грамматика.

Тогда S a, S aba, S ababa, S a(ba)^m, abS ababS и т.д.

Определение 9.3.4. Множество L(G)={wA^*: S w} называется языком, порождаемым грамматикой G=<N, A, P, S>. Также говорят, что грамматика G порождает язык L(G).

Пример 9.3.4. Пусть N={S}, A={a, b}, P={SabS, Sa}. G₁=<N, A, P, S> – грамматика, порождающая язык

L(G₁)={a(ba)^m: m0}.

Пример 9.3.5. Пусть N={S, F}, A={a, b}, P={SFF, FaFb, Fab}. G₂=<N, A, P, S> – грамматика, порождающая язык

L(G₂)={aⁿbⁿa^mb^m: n1, m1}.

Определение 9.3.5. Две грамматики называются эквивалентными, если они порождают один и тот же язык.

Пример 9.3.6. Пусть N={S, F}, A={a, b},P={SaF, FbaF, F}. G₃=<N, A, P, S> – грамматика, порождающая язык

L(G₃)={a(ba)^m: m0}.

Грамматика G₃ эквивалентна грамматике G₃ (см. пример 9.3.4).
4. Иерархия языков по Хомскому
Определение 9.4.1. Формальный язык называется языком типа 0, если он порождается некоторой грамматикой типа 0.

Определение 9.4.2. Контекстной грамматикой (контекстно-зависимой грамматикой, грамматикой типа 1) называется порождающая грамматика, каждое правило которой имеет вид B, где BN, ,(NA)^*, (NA)⁺.

Определение 9.4.3. Формальный язык называется контекстным языком, если он порождается контекстной грамматикой (грамматикой типа 1).

Определение 9.4.4. Контекстно-свободной грамматикой (бесконтекстной грамматикой, грамматикой типа 2) называется порождающая грамматика, каждое правило которой имеет вид B, где BN, (NA)^*.

Пример 9.4.1. Пусть N={S, U, T}, A={a, b, c}, P={SUT, UaU, U, TbTc, T}. Тогда G=<N, A, P, S> – контекстно-свободная грамматика, порождающая язык

L(G)={aⁿb^mc^m: n0, m0}

Определение 9.4.5. Формальный язык называется контекстно-свободным языком, если он порождается контекстно-свободной грамматикой (грамматикой типа 2).

Определение 9.4.6. Праволинейной грамматикой (рациональной грамматикой, грамматикой типа 3) называется порождающая грамматика, каждое правило которой имеет вид BwилиBwT, где B, TN, wA^*.

Определение 9.4.7. Формальный язык называется праволинейным языком, если он порождается праволинейной грамматикой (грамматикой типа 3).

Классы формальных языков типа 0, 1, 2, 3 образуют иерархию Хомского. При этом следует иметь в виду, что:

1) каждая праволинейная грамматика является контекстно-свободной грамматикой;

2) каждая контекстно-свободная грамматика без правил вида является контекстной грамматикой;

3) каждая контекстная грамматика является порождающей грамматикой типа 0.

Пример 9.4.2. Пусть N={S, H}, A={a, b}, P={SaS, Sa, SH, HbH, Hb}. Тогда G=<N, A, P, S> – праволинейная грамматика, порождающая язык L(G)={aⁿb^m: n1 или m1}.