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

АГЕНТСТВО ПО ОБРАЗОВАНИЮ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
УФИМСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ

Кафедра ТК

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

помощью:
регулярных (праволинейных и леволинейных) грамматик G(VT,VN,P,S), V=VN∪VT;
конечных автоматов

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

А→Вγ или А→γ, где 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 соответствует

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, необходимо построить КА:

G({"а", "[", "]",

Сначала нужно преобразовать ее к автоматному виду:
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)

{S, S1, S2, A, A1, A2, B, B1, B2, B3},

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

строится множество состояний КА:

Q=VN∪{H}={S, S1, S2, A, A1, A2, B, B1, B2, B3,H};

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

{S, S1, S2, A, A1, A2, B, B1, B2, B3},

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

δ(‘;’, 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),

необходимо построить эквивалентную

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

относительно некоторой операции, если в результате выполнения этой операции над

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

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

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

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

дополнения;

итерации;

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

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

леволинейная грамматика G, необходимо построить полностью определенный КА