[21.02.11] Лекция №3 (Конспекты - Теория формальных языков)

Лекция №3 [21.02.11]

Регулярные грамматики и конечные автоматы

Для любого формального языка требуется создать порождающую модель и распознающую конструкцию. Порождение слов регулярного языка – регулярная грамматика. Распознавание слов – конечный автомат.

Регулярная грамматика := G =(V,N,S,P)

P: A -> aB (A,BN, aV)

A -> a (A->)

Пример: {aⁿb,n≥0}

S -> b | aS

S |-- b

S |-- aS |-- aaS |-- … |-- aⁿS |-- aⁿb

Пример: {aⁿbⁿ | n,m≥0}

V={a,b}, N={S}

P: S-> | a | b | aS | bS

S|--bS|--baS|--ba L

S -> aS | aB |  | bB

B -> bB | 

S |-- aS |-- … |-- aⁿS |-- aⁿ

S |-- *aⁿS |-- aⁿbB |-- aⁿb

S |-- *aⁿS |-- aⁿbB |-- aⁿbbB |-- *aⁿb^mB |-- aⁿb^m

Надо доказать, что никаких других цепочек, кроме приведённых, грамматика породить не сможет:

S |-- *aⁿS |-- aⁿ

|-- aⁿbB

S |-- *aⁿbB |-- aⁿb

|-- aⁿb^m

S |--bB |-- *b

|-- *b^m

Предъявленная грамматика решает поставленную задачу.

Попробуем убрать :

S -> aS | bB | b | 

B -> bB | b

Можно показать, что вариант B эквивалентен варианту A.

Домашнее задание: bmstu.ru – Персональные страницы – Ткачёв – Теория формальных языков – Задача №1. Сдать до 15 марта.

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

Пусть x – некоторая цепочка во входном алфавите. Мы хотим сделать устройство, распознающее, принадлежит ли эта цепочка некоторому фиксированному языку.

Полубесконечная входная лента, в ячейках которой записаны x₁,x₂,…,x_n…

Будет считывающая головка и блок управления.

Q – множество состояний блока управления.

q₀ – начальное (стартовое) состояние (когда считывающая головка указывает на первую ячейку ленты).

Замечание: с точки зрения алгебраической теории у автомата может быть несколько входов, поскольку решая системы уравнения в полукольцах, мы можем найти любые элементы матрицы стоимостей и сложить их между собой. Однако, в регулярных грамматиках и конечных автоматах начальная вершина (q₀) единственная.

Этот автомат будет считывать последовательно символы на входной ленте, по каждому символу переходя из состояния q_i в состояние q_j (некоторые элементы множества Q). Такой переход описывается командой конечного автомата:

q_ia->q_j

где q_i – текущее состояние, a – видимый символ на ленте, q_j – новое состояние

Кроме этого, допускаются переходы по пустой цепочке.

Конфигурация конечного автомата – упорядоченная пара (q,ay), где q – текущее состояние блока управления, a – текущий символ в обозреваемой ячейке, y – часть цепочки, находящаяся на ленте правее наблюдаемой ячейки. Цепочку ay называют непрочитанной частью входной цепочки. Если она пустая, то её считают равной .

Графовое представление автомата:

x = aaabb

(q₀,aaabb),(q₀aabb),(q₀abb),(q₀bb),(q₁b),(q₁)

Графовая интерпретация: q₀ ->^a q₀ ->^a q₀ ->^a q₀ ->^b q₁ ->^b q₁

Есть прямая связь между последовательностью конфигурации и переходами в соответствующем графе.

Язык конечного автомата M или L(M) – есть множество всех цепочек во входном алфавите, читаемых в автомате M на некотором пути из начального состояния в одно из заключительных.

L(M) = {x | q₀ =>^xq_f, q_fQ_f}

Связь между конечными автоматами и регулярными грамматиками

Язык допускается конечным автоматом тогда и только тогда, когда он порождается регулярной грамматикой.

Этапы доказательства:

1) нужно указать способ построения регулярной грамматики по предъявленному конечному автомату M и доказать, что язык, порождаемый автоматом, совпадает с языком, допускаемым грамматикой, L(M) = L(G);

2) способ построения конечного автомата по регулярной грамматике такой, что язык, допускаемый автоматом, совпадает с языком, порождаемым грамматикой, L(G) = L(M);

Построение регулярной грамматики по конечному автомату.

Дано: КА M: V – входной алфавит;

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

q₀ – начальное состояние;

Q_f – конечное состоние;

q_ia->q_j

Терминальный совпадает с алфавитом V конечного автомата.

Нетерминальный алфавит M грамматики G находится во взаимооднозначном соответствии множества Q состояний конечного автомата M, причём состоянию q мы ставим в соответствие S_q, а состоянию q₀ ставим S (стартовая аксиома). Множество правил вывода P строится по системе команд конечного автомата M следующим образом: правило вывода S_q->aS_r (где a – терминальный символ или пустое слово) принадлежит системе правил грамматике тогда и только тогда, когда в системе правил КА есть правило qa->r

Если и только если состояние r является заключительным, в множество правил добавляется Sr->a в дополнение к предыдущему правилу.

Если состояние q₀ принадлежит множеству заключительных состояний, то добавляется правило S_q0->

Построим грамматику для:

G: V={a,b}

N={S_q0,S_q1}

P: S_q0 -> aS_q0 | b S_q1 | b | 

S_q1 -> bS_q1 | b

S_q0 |--¹ aS_q0 |--¹ aaS_q0 |--¹ aaaS_q0 |--² aaabS_q0 |--⁶ aaabb