Определение 9.2.1. Конкатенацией языков L 1, L 2 Í А* называется язык L 1× L 2={ xy: xÎL1, yÎL2 }.
Определение 9.2.2. Пусть LÍА*. Тогда L0= { e }, L1=L, Ln+1= Ln × L (n=1, 2, …).
Пример 9.2.1. Пусть А= { a, b }, L= { aa, ab }. Выпишем все слова языка L2 в следующей таблице:
aa | ab | |
aa | aaaa | aaab |
ab | abaa | abab |
Заметим, что L2= {(aa) n (ab) m (aa) k: m, n³0, m+n+k=2 }.
Слова языка L3 могут быть получены следующим образом:
aa | ab | |
aaaa | aaaaaa | aaaaab |
abaa | abaaaa | abaaab |
aaab | aaabaa | aaabab |
abab | ababaa | ababab |
Попутно заметим, что L3¹ {(aa) n (ab) m (aa) k: m, n³0, m+n+k=3 }, поскольку ababab Ï{(aa) n (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= { anbm : n³1, m³1 }, то L R={ bman : n³1, m³1 }.
|
|
Определение 9.2.5. Пусть А1 и А2 алфавиты. Отображение H: A1*® A2*, удовлетворяющее условию H(u×w)=H(u)×H(w) для любых u, wÎ A1*, называется гомоморфизмом (морфизмом).
Очевидно, каждый гомоморфизм однозначно определяется своими значениями на однобуквенных словах.
Пример 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. Говорят, что слово wn выводимо из слова w0 (пишут w0 wn), если
|
|
w0Þ w1Þw2Þ…Þwn (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 }. G1=< N, A, P, S > – грамматика, порождающая язык
L (G1)={ a(ba)m: m³0 }.
Пример 9.3.5. Пусть N ={ S, F }, A= { a, b }, P ={ S®FF, F®aFb, F®ab }. G2=< N, A, P, S > – грамматика, порождающая язык
L (G2)={ anbnambm: n³1, m³1 }.
Определение 9.3.5. Две грамматики называются эквивалентными, если они порождают один и тот же язык.
Пример 9.3.6. Пусть N ={ S, F }, A= { a, b }, P ={ S®aF, F®baF, F®e }. G3=< N, A, P, S > – грамматика, порождающая язык
L (G3)={ a(ba)m: m³0 }.
Грамматика G3 эквивалентна грамматике G3 (см. пример 9.3.4).