Лекция 2 Языки, операции над языками

Определение 2.1 Языком в алфавите называется произвольное множество цепочек в. Как следует из определения языка, язык в алфавите является подмножеством (может быть, собственным) множества * всех цепочек в данном алфавите. Поскольку пустое множество является подмножеством любого множества, то и L = есть язык в алфавите. Множество { }, содержащее только пустую цепочку, также является языком. Заметим, что и { } – два различных языка: первый язык (множество цепочек) пуст, а второй содержит единственную цепочку. Если необходимо подчеркнуть, что язык есть язык в алфавите, то будем записывать L( ).

Пример 2.1. Рассмотрим язык L1 ={ai | i 0}, содержащий пустую цепочку и все цепочки, составленные из символа а. Очевидно, что L1={a}*. Соглашение: В тех случаях, когда это не может привести к путанице, будем обозначать множество из одного символа самим этим элементом, т.е. a* = {a}*.

Определение 2.2 Если язык L таков, что никакая цепочка в L не является собственным префиксом (суффиксом) никакой другой цепочки в L, то говорят, что L обладает префиксным (суффиксным) свойством. Пример 2.2. Язык a* не обладает префиксным свойством, а язык {ai bi | i 0} обладает.

Задание 2 Привести примеры языков в алфавите 1. = {a, d, b, c, m} 2. = {a, d, b, f, k} 3. = {a, d, c, s, f} 4. = {a, b, c, n, m} 5. = {d, b, c, m, k} 6. = {b, c, s, k, l} 7. = {b, c, n, m, k} 8. = {c, k, f, n, l} 9. = {f, h, k, g, l} 10. = {a, b, c, f, i} 11. = {a, b, c, j, i} 12. = {a, b, c, k, l} 13. = {a, d, c, j, i} 14. = {a, d, c, k, i} 15. = {a, d, b, j, i} 16. = {a, d, b, k, f} 17. = {a, b, c, k, m} 18. = {a, c, k, j, i} 19. = {a, c, n, m, f} 20. = {a, c, h, g, k} 21. = {a, c, n, r, k} 22. = {a, j, i, k, n} 23. = {a, j, i, k, n} 24. = {b, d, i, j, n}

25. = {c, g, k, j, i} 26. = {d, f, j, i, l} 27. = {d, g, s, r, k} 28. = {d, j, r, s, m} 29. = {c, f, s, j, k} 30. = {c, f, g, s, n} 31. = {s, f, n, a, r} 32. = {f, t, w, i, a} 33. = {e, t, u, q, l} 34. = {a, g, k, l, i} 35. = {q, f, p, t, i} 36. = {z, c, b, j, i} 37. = {e, a, q, k, f} 38. = {w, g, k, e, m} 39. = {q, c, l, r, i} 40. = {u, o, p, m, f} 41. = {a, c, s, f, k} 42. = {a, f, h, r, j} 43. = {f, t, w, k, n} 44. = {a, e, t, k, m} 45. = {y, d, i, r, n} 46. = {c, s, k, f, i} 47. = {r, p, a, i, l} 48. = {w, v, d, r, k} 49. = {d, j, r, c, n} 50. = {z, s, e, j, k}

Рассмотрим теперь, какие операции могут выполняться над языками. Поскольку язык – это множество, то и операции объединения, пересечения, нахождения разности и дополнения применимы и к языкам. Операцию конкатенации можно применять к языкам так же, как к цепочкам.

Определение 2.3 Пусть L1 – язык в алфавите 1, L2 – язык в алфавите 2. Тогда язык L1L2 в алфавите 1 2, называется конкатенацией (а также сцеплением или произведением) языков L1 и L2, L1L2 = {xy | x L1 & y L2}. Определение 2.4. Итерация языка L, обозначаемая через L*, определяется так: 1. L0 = { } 2. Ln =LLn-1 3. L*= Ln.

Определение 2.5 Пусть 1 и 2 – алфавиты. Гомоморфизмом называются любое отображение h : 1 2*. Область определения гомоморфизма h можно расширить до 1*, полагая h( )= и h(xa)=h(x)h(a) для всех x 1* и a 1. Применяя гомоморфизм к языку L, мы получаем другой язык h(L), который представляет множество цепочек {h( )| L} в алфавите 2.

Пример 2.3. Допустим, что хотим заменить каждое вхождение в цепочку символа 0 на символ а, и каждое вхождение символа 1 на bb. Тогда можно определить гомоморфизм h так, что h(0)=a и h(1)=bb. Если L={0n1n|n 1}, то h(L)={anb2n|n 1}. Хотя гомоморфизмы не всегда взаимно однозначны, часто бывает полезно говорить об их обращениях (как отношениях).

Определение 2.6 Если h: 1 2* - гомоморфизмы, то отношение h-1: 2* 2 1* (где 2 1* – множество всех возможных подмножеств множества 1*) определенное ниже, называется обращением гомоморфизма. Если y 2*, то h-1(y)- это множество цепочек в алфавите 1, которые отображаются гомоморфизмом h в цепочку y, т.е. h-1(y) = {x | h(x) = y}. Если L – язык в 2, то h1(L) язык в 1, состоящий из тех цепочек, которые h отображает в цепочки из L. Формально h-1(L)={x | h(x) L}.

Пример 2.4. Пусть h- гомоморфизм, для которого h(0)=a и h(1)=a. Тогда h-1(a)={0,1} и h-1(a*)={0,1}*. Пример 2.5. В качестве второго примера возьмем такой гомоморфизм h, что h(0)=a и h(1)=. Тогда h- 1( )=1* и h-1(a)=1*01*. Здесь 1*01* обозначает язык {1i01j | i,j 0}.

Определение 2.7 Подстановка языков L1, L2,…, Ln в язык L вместо символов a1, a2,…, an есть операция, сопоставляющая языку L в словаре = {a1, a2,…, an} и языкам L1, L2,…,Ln в словарях 1, 2,…, n соответственно язык S(L; a1, a2,…, an L1, L2,…,Ln ) в словаре 1 2 … n, где S(L; a1, a2,…, an L1, L2,…,Ln ) = {wi1wi2…wik ai1ai2…aik L, wi1 Li1,wi2 Li2,…wik Lik } L', где L' = { }, если пустая цепочка принадлежит языку L, и L' =, если пустая цепочка не принадлежит языку L.

Пример 2.5. Рассмотрим язык L = { } в словаре V = {, } и языки L1={a, b}, L2 ={+,-} в словарях V1={a, b}, V2 ={+,-}. Результатом подстановки будет язык S(L;, L1, L2 ) = {a+a, a+ b, b+ a, b+b, a-a, a-b, b-a, b-b}.

Задание 3 Описать язык, являющийся результатом применения указанного гомоморфизма h к заданному языку L. 1. L={anb2nan | n 1}, h(a)=1 и h(bb)=2 2. L={0n1n2n | n 1}, h(0)=b, h(1)=a, h(2)=cc 3. L={2n12n0n | n 1}, h(0)=b, h(11)=c, h(2)=bb 4. L={anbncn | n 1}, h(a)=11, h(b)=2, h(c)=3 5. L={3n2n1n2n | n 1}, h(1)=aa, h(2)=c, h(3) = bb 6. L={4n12n2n | n 1}, h(11)=a, h(4)=c, h(2) = b 7. L={1n32n1n2n | n 1}, h(1)=aa, h(2)=c, h(3) = b 8. L={anb2ncn | n 1}, h(a)=22, h(b)=1, h(c) = L={anb2nc2n | n 1}, h(a)=3, h(bb)=4, h(c) = L={1n2n12n | n 1}, h(1)=aa, h(2)=bb

11. L={2n12n2n12n | n 1}, h(2)=aa, h(1)=b 12. L={a2nbna2nbn | n 1}, h(aa)=1, h(b)= L={anbnc2nan | n 1}, h(a)=11, h(b)=2, h(cc) = L={1n2n1n32n | n 1}, h(1)=aa, h(2)=c, h(33) = b 15. L={22n12n22n3n | n 1}, h(22)=a, h(1)=b, h(3) =cc 16. L={anc2nb2nan | n 1}, h(a)=3, h(bb)=2, h(c) = L={cnb2ncnan | n 1}, h(a)=11, h(bb)=2, h(c) = L={b2ncnancn | n 1}, h(a)=22, h(b)=1, h(c) = L={c2nb2nancn | n 1}, h(a)=1, h(bb)=2, h(cc) = L={a2nbnc2na2n | n 1}, h(aa)=1, h(b)=22, h(c) = L={22n1n32n1n | n 1}, h(1)=cc, h(22)=b, h(3) = a 22. L={3n22n12n3n | n 1}, h(11)=a, h(2)=b, h(3) = cc 23. L={anbnc2nan | n 1}, h(a)=11, h(b)=2, h(c) = L={2n32n1n2n| n 1}, h(1)=aa, h(2)=b, h(3) = c 25. L={cna2nb2ncn | n 1}, h(aa)=1, h(b)=2, h(c) = 33

26. L={a2nb2na2ncn | n 1}, h(a)=1, h(bb)=2, h(c) = L={1n22n1n3n | n 1}, h(1)=bb, h(22)=a, h(3) = cc 28. L={anbnanc2n | n 1}, h(a)=1, h(b)=222, h(cc) = L={2n32n1n2n| n 1}, h(1)=ccc, h(2)=b, h(33) = a 30. L={32n22n32n1n | n 1}, h(1)=cc, h(22)=b, h(3) = a 31. L={4n152n26n172n | n 1}, h(2)=aa, h(1)=b, h(4)=cc, h(5)=n, h(6)=r, h(7)=w 32. L={1n42n5n62n7n | n 1}, h(2)=aa, h(1)=b, h(4)=cc, h(5)=n, h(6)=r, h(7)=w 33. L={agnbfnc2nan | n 1}, h(a)=11, h(b)=2, h(cc) = 3, h(gg) = 4, h(f) = L={11n223n122n332n | n 1}, h(1)=aa, h(2)=c, h(33) = b 35. L={2112n1232n2212n321n | n 1}, h(22)=a, h(1)=b, h(3) =cc 36. L={abncab2nba2nan | n 1}, h(a)=3, h(bb)=2, h(c) = 1

37. L={cacnbca2ncanacn | n 1}, h(a)=11, h(bb)=2, h(c) = L={bca2ncaanabbncn | n 1}, h(a)=22, h(b)=1, h(c) = L={abc2nbac2nacncbn | n 1}, h(a)=1, h(bb)=2, h(cc) = L={ac2nbcanca2nab2n | n 1}, h(aa)=1, h(b)=22, h(c) = L={2122n13n3122n1n | n 1}, h(1)=cc, h(22)=b, h(3) = a 42. L={31n2312n1232n31n | n 1}, h(11)=a, h(2)=b, h(3) = cc 43. L={abcnbcnca2nabn | n 1}, h(a)=11, h(b)=2, h(c) = L={213n3212n12n23n| n 1}, h(1)=aa, h(2)=b, h(3) = c 45. L={cabnac2nba2ncbn | n 1}, h(aa)=1, h(b)=2, h(c) = L={aba2nbc2nac2ncan | n 1}, h(a)=1, h(bb)=2, h(c) = L={12n212n13n3n | n 1}, h(1)=bb, h(22)=a, h(3) = cc 48. L={bcanbcnacncab2n | n 1}, h(a)=1, h(b)=222, h(cc) = L={21n322n132n213n| n 1}, h(1)=ccc, h(2)=b, h(33) = a 50. L={312n232n312n1n | n 1}, h(1)=cc, h(22)=b, h(3) = a

Задать язык - значит указать множество цепочек, принадлежащих языку. Существует несколько способов задания языков. 1. Явное задание языка. В данном случае перечисляется все множество цепочек языка. Данный способ задания языка часто используется в диалоговых системах при задании языка, при помощи которого производится диалог пользователя с программой. 2. Задание языка регулярным выражением. 3. Задание языка при помощи порождающей грамматики. 4. Задание языка при помощи распознавателя. Далее будут подробно рассмотрены способы задания языков при помощи регулярных выражений, при помощи порождающей грамматики, при помощи распознавателя.