34. Алфавит, слово, язык, множество языков над данным алфавитом, его мощность, операции над языками, полукольцо языков над данным алфавитом.

Алфавит — это произвольное непустое конечное множество V = {a₁, ... , a_n}, элементы которого называют буквами или символами.

Словом или цепочкой в алфавите V называют произвольный кортеж из множества V^k (k-й декартовой степени алфавита V) для различных k = 0,1,2,...

Например, если V = {а,b,с}, то (а), (b), (с), (а, b), (а, b, с),

(с, b, а, а, с) и т.д. есть слова в V.

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

Множество всех языков в алфавите V, т.е. множество 2^V*, есть булеан счетного множества, и, следовательно, оно в силу теоремы Кантора имеет мощность континуума(мощность множества всех вещественных чисел).

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

Объединением языков L₁ и L₂ называют язык L₁⋃ L₂, слова которого принадлежат по меньшей мере одному из этих языков.

Соединением (конкатенацией) языков L₁ и L₂ называют язык L₁L₂, состоящий из всех возможных соединений слов xy, в которых слово x принадлежит первому, а слово у — второму языку, т.е.

L₁L₂ = {ху: х ∈ L₁ и у ∈ L₂}.

Итерацией языка L называют объединение всех его степеней:

Алгебра есть замкнутое полукольцо.

1. По операции объединения множество всех языков образует коммутативный и идемпотентны моноид.

2. Операция соединения языков ассоциативна:

{ }L = L{ } = L

, для любого x.

3. (1)

(2)

Доказательство тождеств:

(1): Пусть , где y L₁, а z , т.е. z или z . Если z L₂, то yz L₁L₂, а если z L₃, то yz L₁L₃, т.е. . Пусть теперь . Тогда x = yz, где , или , т.е. . Второе тождество доказывается аналогично.

35. Регулярные операции и регулярные языки. Мощность множества регулярных языков. Образуют ли регулярные языки замкнутое полукольцо относительно регулярных операций?

Множество регулярных языков в алфавите V ={a₁, … ,a_n} есть не что иное, как замыкание конечного множества относительно операций объединения, соединения и итерации.

1) пустое множество множество {λ} (состоящее из одной пустой цепочки) и множество {а} для каждого a V считаем регулярным языком в алфавите V;

2) если известно, что P и Q — регулярные языки в алфавите V, то к множеству регулярных языков в алфавите V следует добавить объединение и соединение PQ.

3) если известно, что Р — регулярный язык в алфавите V, то к множеству регулярных языков в алфавите V следует добавить его итерацию Р*;

4) никаких других регулярных языков, кроме определенных в п. 1-3, не существует.

Регулярные операции – это операции объединения, соединения и итерации.

, где L₁ и L₂ – это регулярные языки.

Мощность множества регулярных языков:

Язык в V регулярный  он является элементом R(V) (полукольцо регулярных языков).

36. Регулярные языки и автоматы распознаватели. Построение языка по автомату и автомата по языку. Теорема Клини.

Регулярные языки порождаются регулярными грамматиками, для которых АаВ или Аа, где а — либо терминал, либо пустая цепочка (В — нетерминал).

Множество регулярных языков равномощно множеству натуральных чисел, т.е. оно счётное.

Автоматом-распознавателем называется упорядоченная четвёрка , где — ориентированный мультиграф, S — входы, а T — выходы.

Задача построения языка по автомату (анализа конечного автомата). Для решения этой задачи достаточно любым методом вычислить матрицу стоимости автомата (напр., решить в полукольце систему уравнений , где  — столбец, компоненты которого равны , кроме тех, которые соответствуют заключительным состояниям). Задача синтеза — задача построения автомата по языку.

Теорема Клини: Пусть — произвольный алфавит. Язык допускается некоторым конечным автоматом (КА).

⊲(⇒): Воспользуемся методом индукции по построению рег. языка, как элемента :

1. Строим графы автоматов языков . Они конечны.

2. Пусть КА для

На рисунках наглядно видно, что все автоматы конечны⊳

⊲(⇐): Язык КА — конечное объединение языков из матрицы стоимостей , где A* — итерация матрицы меток дуг, метка каждой дуги — регулярное выражение, обозначающее язык из — полукольцо с итерацией ⇒ матрица стоимостей КА состоит из языков полукольца язык КА — элемент

Соединение:

Итерация:

Объединение: