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

Определение 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² в следующей таблице:

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

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

Попутно заметим, что 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=haq, v=hbq принекоторыхсловах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).