ТМВ-2020-Лекция-11.02.2020

Материал из Кафедра Прикладной Математики
Перейти к навигации Перейти к поиску

Тема лекции - Регулярный язык. Автоматы

Регулярные языки

Возьмем некоторое конечное множество символов \(A\), назовем его алфавитом, а его элементы — буквами.

\(\Sigma\) - конечный алфавит символов

Слово - конечная последовательность символов

Язык - множество слов.

Все возможные регулярные языки:

1) \(\emptyset\)

2) \({\lambda}\)(множество, состоящее из пустого слова)

3) \({a}\), если \(a \in \Sigma\)

Правила вывода (операции над языками):

Пусть A и B - регулярные языки. тогда:

1) Конкатенация (произведение)

Множество слов вида \(AB = \{\alpha\beta, \alpha\in A, \beta\in B\}\)

2) Объединение

Множество слов вида \(A \cup B = A+B=\{\alpha | \alpha\in A\cup\ \alpha\in B\}\)

3) Итерация

Язык вида \(A^*=\{\alpha_1,\alpha_2, \ldots \alpha_n | \alpha_i\in A, k\in\mathbb{N}_0\}\), где \(\mathbb{N}_0 = \{0\} \cup \mathbb{N}\)

Регулярные выражения (пример)

Регулярные выражения — удобная форма записи регулярных языков.

<[a-z A-Z 0-9]*>

(a+b+...+z+A+B+...+Z+0+1+...+9)*

a ? - либо есть, либо нет вхождений

a + - одно либо более вхождений

a * - ноль либо более вхождений

(https?://)?

(www2?\.)?

Конечный автомат

Конечный автомат
Конечный автомат для регулярного выражения aabc*a

Автомат - математическая модель компьютера. содержащая конечное число состояний.

Конечный автомат задаётся:

- \(\Sigma\) - алфавит

- Q -множество состояний

- \(S \in Q\) - начальное состояние

- \(T \subset Q\) - терминальные (допускающие) состояния

- \(\delta: Q*\Sigma \to Q\) - функция переходов

Граф переходов

Граф переходов - "неудачная попытка" обобщить конечный автомат.

Отличия:

- разрешено несколько входных состояний \(S \subset Q\)

- возможно несколько переходов с одним весом из одной вершины

- разрешены \(\lambda\)-переходы. Переходы разрешены по \(\lambda\)-переходам без сдвига позиций во входном слове

\(S: Q*(\Sigma \cup \{\lambda\})\to 2^Q \)

Эквивалентный детерминированный конечный автомат (ДКА)

ДКА
ДКА

Состояния конечного автомата - подмножества состояний графа переходов.

ДКА2.png

Определяем для \(k\)-го подмножества вершин графа переходов и символа из \(\Sigma\), в некоторое множество вершин можно попасть по \(\lambda\)-ребрам и по ребрам, содержащим эти символы.




Канонический граф переходов

ГП
Обычный граф переходов

Требования:

1) Одно начальное состояние

2) Одно терминальное состояние

3) В начальную вершину не входит ни одна дуга

4) Из терминальной вершины не выходит ни одна дуга

Канонический ГП
Канонический граф переходов

Обобщённый граф переходов

Обобщенный граф переходов.png

На ребрах данного графа написаны регулярные выражения

Алгоритм: берём граф переходов и начинаем из него убирать вершины, за исключением стартовой и терминальной

Примечание

Невозможно построить ГП для выражений вида: \(a^n b^n\), так как язык нерегулярный.

Построить ГП для выражений вида \(a^n b^m\) можно. Регулярное выражение: \(a*b*\)

Регулярные выражения по ГП
Обобщённый ГП
Пример построения обобщённого ГП