Словарь. Цепочка над словарем. Язык.
Рассмотрим основные понятия теории формальных языков.
Словарь – это конечное множество элементов, называемых символами.
Пусть задан словарь V.
Цепочка над словарем V – это произвольная упорядоченная последовательность символов словаря.
Пример: V= {a, b, c} – словарь. a= aabbc – цепочка, b – bbaaca – другая цепочка.
Пустая цепочка– это цепочка, не содержащая символов (обозначается e).
Пусть V – некоторый словарь. V* будем обозначать множество всех возможных цепочек, составленных из символов словаря V, включая пустую цепочку.
Пусть aÎV, тогда a0= e, an= aaa…a(n-раз).
Операции над цепочками
1) конкатенация (склеивание) – бинарная операция на множестве V*.
Если a, bÎV*, то результат конкатенации – цепочка ab.
Свойства конкатенации:
a) пустая цепочка играет роль единицы: ae= ea= a;
b) любая цепочка есть конкатенация её подцепочек.
2) подстановка – замена некоторой цепочки заданной цепочки a цепочкой b: a= aabcc, b= bca, g= abcac.
Языком над словарем Vназывается некоторое множество цепочек над словарем V.
Обозначение: L(V)Î V*.
Над словарем V можно определить столько языков, сколько подмножеств содержит V*.
Если словарь V не пустой, то существует бесконечное число различных языков над словарем V.
Примеры языков
1) Словарь V1= {a, b}. Определим язык L1, как множество цепочек вида L1= {aab, babaa, ababab}. Это пример конечного языка, состоящего из трех цепочек.
2) V2= {a, b}, L2= {an, bn} (n³0). aaabbbÎ L2, aaabbÏL2. Это пример языка содержащего бесконечное количество цепочек.
3) V3= {a, b, c}. L2= {an, bn, cn} (n³1). aaabbbcccÎ L3, abbcÏL3.
4) V4= {(,)}, L4= {(()), (), (())()(()),…} – множество скелетов правильных скобочных выражений (язык Дика).
5) V5= {a, b}, L5= множество всех цепочек, содержащих одинаковое число вхождений символов a и b. abaabbÎ L5, baabbÏL5.
6) V6= {a, b, c, d, *, /, +, –}, L6 – множество правильных арифметических выражений, построенных из букв a, b, c, d. a-b*c+dÎ L6, a-*b/cÏL6.
7) V7– множество словоформ русского языка. L7 – русский язык.
8) V8= {a, b, …, z, 0, 1, …, 9, *, /, +, –, begin, end, …}, L8 – язык Паскаль.
Вопросы и упражнения
1. Что понимается под словарем языка? Синтаксисом? Семантикой?
2. В чем суть метода синтаксически-ориентированной трансляции?
3. Назовите основные понятия теории формальных языков.
4. Перечислите основные операции над цепочками.
5. Что называется языком над словарем?
6. Дан словарь V={a, в, с}. Приведите примеры конечного и бесконечного языков над данным словарем.
7. Дан язык L={синий лес, синий темный лес, темный лес}. Приведите примеры словарей, над которыми можно определить этот язык.