Раздел 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> – порождающая грамматика.

Тогда Sa, Saba, Sababa, Sa(ba)^m, abSababS и т.д.

Определение 9.3.4. Множество L(G)={wA^*: Sw} называется языком, порождаемым грамматикой 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).