Операции над языками

Определение 9.2.1. Конкатенацией языков L ₁, L ₂ Í А^* называется язык L ₁× L ₂={ xy: xÎL₁, yÎL₂ }.

Определение 9.2.2. Пусть LÍА^*. Тогда L⁰= { e }, 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)^*,

при этом пары (a, b)Î P называются правилами подстановки (просто правилами или продукциями) и записываются в виде a®b;

д) 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=h a q, v=h b q при некоторых словах a, b, h, q в алфавите N È A и a®bÎ 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®e }. G₃=< N, A, P, S > – грамматика, порождающая язык

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

Грамматика G₃ эквивалентна грамматике G₃ (см. пример 9.3.4).

Дата добавления: 2014-01-06