Способы задания регулярных языков

конечных автоматов (КА);

регулярных множеств (и обозначающих их регулярных выражений).

А→Вγ или А→γ, где A,B∈VN, γ∈VT*

А→γВ или А→γ, где A,B∈VN, γ∈VT*

M(Q, V, δ, q0, F),

Все три способа в равной степени
могут быть использованы
для определения регулярных языков.

Если над множествами цепочек символов из алфавита V определить операции конкатенации и итерации как:
PQ – конкатенация P∈V* и Q∈V*: PQ={pq ∀p∈P, ∀q∈Q};
P* – итерация P∈V*: P*={pn ∀p∈P, ∀n∈N};

тогда для алфавита V регулярные множества определяются рекурсивно:
∅ – регулярное множество;
{λ} – регулярное множество;
{а} – регулярное множество ∀a∈V;
если Р и Q – произвольные регулярные множества, то множества P∪Q, PQ
и Р* также являются регулярными множествами;
ничто другое не является регулярным множеством.

Регулярные множества – это множества цепочек символов над заданным алфавитом, построенные определенным образом (с использованием операций объединения, конкатенации и итерации).

Существуют алгоритмы, которые позволяют для регулярного языка, заданного одним из указанных способов, построить другой способ, определяющий тот же самый язык.

Связь регулярных выражений и регулярных грамматик:
для любого регулярного языка, заданного регулярным выражением, можно построить регулярную грамматику, определяющую тот же язык;
для любого регулярного языка, заданного регулярной грамматикой, можно получить регулярное выражение, определяющее тот же язык.

Связь регулярных выражений и конечных автоматов:
для любого регулярного языка, заданного регулярным выражением, можно построить КА, определяющий тот же язык;
для любого регулярного языка, заданного КА, можно получить регулярное выражение, определяющее тот же язык.

Связь регулярных грамматик и конечных автоматов:
на основе имеющейся регулярной грамматики можно построить эквивалентный ей КА;
для заданного КА можно построить эквивалентную ему регулярную грамматику.

так как регулярные грамматики используются
для определения лексических конструкций
языков программирования, то, создав автомат
на основе известной грамматики, можно
получить распознаватель для лексических
конструкций данного языка,
то есть решить задачу разбора
для лексических конструкций языка,
заданных произвольной регулярной грамматикой

Q=VN∪{H}

каждому нетерминальному символу из множества VN грамматики G соответствует одно состояние из множества Q автомата М, также во множество состояний автомата добавляется еще одно дополнительное состояние, которое обозначается Н

V=VT

входным алфавитом автомата М является множество терминальных символов грамматики G′

P

просматривается множество правил P грамматики G

А→t, A∈VN, t∈VT

в δ добавляется:
δ (t, H)=A

А→Bt, A, B∈VN, t∈VT

в δ добавляется:
δ (t, B)=A

F={S}

q0=H

Имеется леволинейная грамматика
G(VT, VN, P, S),
необходимо построить эквивалентный ей КА
M(Q, V, δ, q0, F).

Все языки программирования определяют
нотацию записи «слева направо»,
в той же нотации работают и компиляторы,
поэтому далее рассмотрим
алгоритмы для леволинейных грамматик.

Сначала нужно преобразовать ее к автоматному виду:
G'({"а", "[", "]", "(", ")",";"}, {S, S1, S2, A, A1, A2, B, B1, B2, B3}, Р, S)
Р':
S→S;| S1)| S2)
S1→A(
S2→Ba
A→ A2;|A(|A)|Aa| A;
A2→A1]
A1→[
B→ B2] | B]|B)|B(|Ba|B[| B3;
B2→B1a
B1→[
B3→B)

Теперь на основе автоматной грамматики строится КА:

строится множество состояний КА:
Q=VN∪{H}={S, S1, S2, A, A1, A2, B, B1, B2, B3,H};

входной алфавит:
V={"а", "[", "]", "(", ")",";"};

просматривается множество правил грамматики и строятся функции переходов:

δ(‘;’, S)=S δ(‘)’, S1)=S δ(‘)’, S2)=S

δ(‘(’, A)=S1

δ(‘a’, B)=S2

δ(‘;’, A2)=A δ(‘(’, A)=A δ(‘)’, A)=A δ(‘a’, A)=A δ(‘;’, A)=A

δ(‘]’, A1)=A2

δ(‘[’, H)=A1

δ(‘]’, B2)=B δ(‘]’, B)=B δ(‘)’, B)=B δ(‘(’, B)=B
δ(‘a’, B)=B δ(‘[’, B)=B δ(‘;’, B3)=B

δ(‘a’, B1)=B2

δ(‘[’, H)=B1

δ(‘)’, B)=B3

начальное состояние КА q0=H;

множество конечных состояний F={S}.

Имеется КА
M(Q, V, δ, q0, F),
необходимо построить эквивалентную ему леволинейную грамматику
G(VT, VN, P, S).

VT=V

VN=Q/{q0}

множество VN грамматики G строится на основании множества Q автомата М так, чтобы каждому состоянию автомата, за исключением начального состояния, соответствовал один нетерминальный символ грамматики

δ

просматривается функция переходов автомата М

δ(t, А)=∅

δ(t, А)={B1, B2, …, Bn}, n>0,
A∈Q, ∀n≥i>0: Bi∈Q, t∈V

i=1, n, 1

A=q0

-

во множество P добавляется:
Bi→At

во множество P добавляется:
Bi→t

+

F={F0}

-

VN=VN∪{S}
S→F1|F2|…|Fn

S=F0

+

1

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

Регулярные языки замкнуты относительно следующих операций:

пересечения;

объединения;

дополнения;

итерации;

конкатенации;

гомоморфизма (изменения имен символов и подстановки цепочек вместо символов).