Словарь. Цепочка над словарем. Язык

Рассмотрим основные понятия теории формальных языков.

Словарь – это конечное множество элементов, называемых символами.

Пусть задан словарь V.

Цепочка над словарем V – это произвольная упорядоченная последовательность символов словаря.

Пример: V= {a, b, c} – словарь. a= aabbc – цепочка, b – bbaaca – другая цепочка.

Пустая цепочка – это цепочка, не содержащая символов (обозначается e).

Пусть V – некоторый словарь. V* будем обозначать множество всех возможных цепочек, составленных из символов словаря V, включая пустую цепочку.

Пусть aÎV, тогда a⁰= e, aⁿ= aaa…a(n-раз).

Операции над цепочками

1) конкатенация (склеивание) – бинарная операция на множестве V*.

Если a, bÎV*, то результат конкатенации – цепочка ab.

Свойства конкатенации:

a) пустая цепочка играет роль единицы: ae= ea= a;

b) любая цепочка есть конкатенация её подцепочек.

2) подстановка – замена некоторой цепочки заданной цепочки a цепочкой b: a= a abc c, b= bca, g= abcac.

Языком над словарем V называется некоторое множество цепочек над словарем V.

Обозначение: L(V)Î V*.

Над словарем V можно определить столько языков, сколько подмножеств содержит V*.

Если словарь V не пустой, то существует бесконечное число различных языков над словарем V.

Примеры языков

1) Словарь V₁= {a, b}. Определим язык L₁, как множество цепочек вида L₁= {aab, babaa, ababab}. Это пример конечного языка, состоящего из трех цепочек.

2) V₂= {a, b}, L₂= {aⁿ, bⁿ} (n³0). aaabbbÎ L₂, aaabbÏL₂. Это пример языка содержащего бесконечное количество цепочек.

3) V₃= {a, b, c}. L₂= {aⁿ, bⁿ, cⁿ} (n³1). aaabbbcccÎ L₃, abbcÏL₃.

4) V₄= {(,)}, L₄= {(()), (), (())()(()),…} – множество скелетов правильных скобочных выражений (язык Дика).

5) V₅= {a, b}, L₅= множество всех цепочек, содержащих одинаковое число вхождений символов a и b. abaabbÎ L₅, baabbÏL₅.

6) V₆= {a, b, c, d, *, /, +, –}, L₆ – множество правильных арифметических выражений, построенных из букв a, b, c, d. a-b*c+dÎ L₆, a-*b/cÏL₆.

7) V₇– множество словоформ русского языка. L₇ – русский язык.

8) V₈= {a, b, …, z, 0, 1, …, 9, *, /, +, –, begin, end, …}, L₈ – язык Паскаль.

Вопросы и упражнения

1. Что понимается под словарем языка? Синтаксисом? Семантикой?

2. В чем суть метода синтаксически-ориентированной трансляции?

3. Назовите основные понятия теории формальных языков.

4. Перечислите основные операции над цепочками.

5. Что называется языком над словарем?

6. Дан словарь V={a, в, с}. Приведите примеры конечного и бесконечного языков над данным словарем.

7. Дан язык L={синий лес, синий темный лес, темный лес}. Приведите примеры словарей, над которыми можно определить этот язык.