Автоматы, языки и грамматики

Автоматы, языки и грамматики.

Язык – это совокупность правильно построенных конструкций (предложений). Грамматика - это совокупность следующих объектов: G=<Vт,Vn,I,R>

Vт – словарь терминальных символов, который состоит из основных символов языка, к которым относятся буквы, цифры, знаки и неделимые конструкции языка (for, while,…).

Vт = {a,b,…,z}

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

Vn = {A,B,…,Z}

I – начальный символ грамматики, является элементом нетерминального словаря.

I € Vn

R – множество порожденных правил вида:

φ  ψ, где φ и ψ – некоторые последовательности символов полного алфавита грамматики: V* = (Vт v Vn)*,

где

V = Vт v Vn – полный словарь (алфавит) грамматики. В φ входит хотя бы один нетерминальный символ.

Vт* - множество конечных цепочек, построенных из терминальных символов.

V* - множество всех конечных цепочек, построенных из символов полного словаря (терминальных и нетерминальных символов).

φ, ψ € V* - конечные цепочки, построенные из символов общего словаря.

Порождающее правило определяет подстановку, при котором рассматриваемая цепочка последовательных символов φ заменяется на последовательность ψ.

Пусть задано правило R : φ  ψ, тогда, если задана цепочка:

ώ1 = ξ1 φ ξ2, где ξ1 ξ2 € V* - цепочки, и если из нее получается цепочка следующего вида:

ώ2 = ξ1 ψ ξ2

Тогда говорят, что ώ2 выводима непосредственно из ώ1 и обозначается

ώ1 => ώ2 или

*

ώ1 => ώn

Предположим, что есть множество цепочек:

Ω = { ώ1 , ώ2 , ώ3 , … , ώn}, таких, что ώ1 => ώ2 ώ2 => ώ3

…

ώn-1 => ώn, то говорят, что

*

ώ1 => ώn (ώn выводима из ώ1)

Определение. Множество конечных цепочек, которые выводятся из начального символа грамматики и, которые представлены только терминальными символами, называются языком порождаемой грамматикой:

*

L(G) = { ώ : ώ € Vт* & I => ώ }

Рассмотрим примеры грамматик и языков:

1.G1:

Vт = {a , b , c} I

Vn = {I}

R = {Iabc} L(G1) = {(abc)}

2. G2:

Vт = {a , d , c}

I

Vn = {I , B , C}
R = { IaB,	- правило 1
BCd,	- правило 2
BdC,	- правило 3
C c}	- правило 4

I 1=> aB 2=> aCd 4=> acd 3=> adC 4=> adc

L(G2) = {(acd) , (adc)}

3.G3:

Vт = {a , b , e} I

Vn = {I , A}
R = { IaAb,	- правило 1
aAaaAb,	- правило 2
Ae}	- правило 3

где e VT – пустой символ

I 1=> aAb 3=> ab

I 1=> aAb 2=> aaAbb 2=> aabb

I 1=> aAb 2=> aaAbb 2=> aaaAbbb 3=> aaabbb

…

L(G3) = {(anbn) n>=1}

4.G4:

Vт = {a, b} I

Vn = {I , A}
R = { IaA,	- правило 1
AbA}	- правило 2

I 1=> aA 2=> abA 2=> abbA 2=> …

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

Чтобы язык был не пуст в нем должно быть:

a)хотя бы одно правило вида:

η w , w € Vт*

*

b)I => η

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

Пример:

G5:

Vт = {a , b}
Vn = {I , A}
I
R = {I  aAb,	- правило 1
A  aAb,	- правило 2
A  ab,	- правило 3
A  e},	- правило 4

где e VT – пустой символ
	I
a		b
a	A	b
a	A	b
a	A	b
	e	aaaabbbb

L(G5) = {(anbn) n>=1}

Это синтаксический разбор цепочки. Порожденная цепочка представляет собой конечные вершины дерева, которые выписываются при обходе вершин дерева против часовой стрелки. Определение. Две грамматики называются эквивалентными, если они порождают одинаковые языки.

G3 и G5 – эквивалентны: L(G3) = L(G5).

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

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

G6 :

Vт = {a , b , с , d} I

Vn = {I , A , B}
R = { IAB,	- правило 1
Aa,	- правило 2
Aac,	- правило 3
Bb,	- правило 4
Bcb}	- правило 5

I 1=> AB 2=> aB 4=> ab

I 1=> AB 3=> acB 4=> acb I 1=> AB 2=> aB 5=> acb

Данная цепочка неоднозначна, следовательно G6 неоднозначна.

Задача распознавания цепочек языка.

Задачей распознавания является задача, определяющаяся является ли заданная цепочка порождением заданной грамматикой.

Определение. Пусть заданы две цепочки:

ώ1 = ξ1 φ ξ2 ώ2 = ξ1 ψ ξ2 ξ1 ξ2 € V*

И правило:

R = φψ, где φ,ψ € V*

то говорят, что цепочка ώ1 получается из цепочки ώ2 путем непосредственного сворачивания ώ1<= ώ2 за счет применения правила R, либо

n

ώ1<= ώ2

Определение. Пусть задано множество цепочек:

Ω = { ώ1 , ώ2 , ώ3 , … , ώn}

ώn-1 < = ώn

…

ώ1 <= ώ2

то говорят, что

*

ώ1<= ώn (просто сворачивание)

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

Классификация грамматик по Хомскому.

1)Грамматика типа 0 или общего вида.

Порождающие правила этой грамматики не имеют ограничений:

R:φ  ψ , φ ≠ e (e – символ конца)

φ может содержать не только терминальные символы | ώ | - длина цепочки – число символов цепочки.

| φ | < | ψ |

Могут быть правила, которые укорачивают цепочки. Эта грамматика не имеет практического использования.

2)Грамматика типа 1 или непосредственных составляющих.

Это контекстно-зависимая грамматика, то есть применение правил этих грамматик зависит от контекста, и не укорачивает длину цепочки.

R: ξ1 φ ξ2  ξ1 ψ ξ2 ξ1 ξ2 φ ψ € V*

Пример:

G8

Vт = {a, b, с, d} I

Vn = {I, A, B} R = { IaAI,

AIAAI, AAAABA, AB,

aBA  bcdA, bI  ba}

3)Грамматика типа 2 или контекстно-свободная На порождающее правило накладывается гораздо большее ограничение:

R: A ώ

A € Vn, ώ € V*

Пример:

G9

Vт = {a , b} I

Vn = {I }

R = { IaIa,	- правило 1
IbIb,	- правило 2
Iaa,	- правило 3
I  bb}	- правило 4

I 1=> aIa2=> abIba1=> abaIaba4=> ababbaba L(G9) = {xx1 ; x € Vт*}

где x1 – зеркальное отражение x.

4)Грамматика типа 3 или автоматная На порождающее правило накладывается суровое ограничение:

a)	Левосторонняя автоматная грамматика:	A  a, A  Ba
b)	Правосторонняя автоматная грамматика:	A  a, A  aB

A, B € Vn, a € Vт

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

Правила вида:

A  aA – для правосторонней грамматики, A  Aa - для левосторонней грамматики называются рекурсивными.

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

Пример:

G10

Vт = {a, b} I

Vn = {I, A} R = { IaI,

IaA, AbA, A  b}

I 1=> aI1=> aaI2=> aaaA3=> …4=>aa…abb…bb

L(G10) = {anbm, a,b € Vт , n>0 , m>0 }

Язык, порождаемый грамматикой типа i, называется языком типа i, где i меняется от 0 до 3.

L0<=LI<=LII<=LIII

Язык LIII более узкий – самый простой, автоматный, чем язык L0 (наиболее общий язык).

Примеры построения грамматик.

Предположим, что необходимо построить грамматику, содержащую 2 символа *, /, при этом каждая цепочка начинается с одной *, а заканчивается **, называемыми, началом и концом цепочки. Внутри содержит последовательность ////, разделенных *, т.е. допустимы */**,

*///**, *//*/*///**.

Vт = {/,*} Vn = {A, I}

Начнем с простого:

A будет обозначать любую непустую последовательность наклонных.

R = { I  *A**,	- правило 1
A/,	- правило 2
A  A/}	- правило 3

Чтобы получить произвольное количество цепочек из наклонных, введем нетерминальный символ B, который означает цепочку из наклонных, разделенных *, при этом надо добавить два правила (B  A, B  B * A) и изменить первоначальное правило (I  *B**). Тогда:

R = { I  *B**,	- правило 1
B  A,	- правило 2
B  B * A,	- правило 3
A/,	- правило 4
A  A/}	- правило 5

Пример:

I1=>*B**3=>*B*A**3=>*B*A*A**2=>*A*A*A**4=>*/*A*A**5=>*/*A/*A**=>…4=>*/*///*////**.

Примеры грамматик, используемых при определении языков программирования

Терминальный словарь – множество основных символов языка. Нетерминальный словарь – множество синтаксических понятия языка.

При формальном описании языка программирования используется так называемый метаязык (язык, используемый для описания другого языка).

Для описания правил языка будем использовать язык Бекуса (Бекусовская нормальная форма). Пример. <целое без знака> ::= - “это есть”.

Влевой части Бекусовского правила пишется определяемое понятие, а в правой цепочка состоящая из основных символов и синтаксических понятий.

Вправой части может стоять вертикальная черта | (понятие “ИЛИ”).

Пример.

Бекусовское правило:

<целое без знака>::=<цифра>|<целое без знака><цифра> <цифра>::=0| 1|2 … | 9.

Грамматика (формальная):

Vт = {0,1,2…9}

Vn = {I,A} I

R = {IIA , IA , A0 , A1…A9}

Это контекстно-свободная грамматика (типа 2).

Пример.

Грамматика для идентификатора (цепочка из символов, букв, цифр, или символов подчеркивания, начинающихся с буквы для простоты):

Бекусовское правило: <идентификатор>::=<буква>|<идентификатор><буква>|<идентификатор><цифра> <цифра>::=0| 1| 2…|9

<буква>::=_|a|b|c…|z

Грамматика (формальная):

Vт = {0, 1, 2, …, 9, a, b, …, z} Vn = {I, B, C}

R = {IB, IIB, IIС, B_, Ba, B…z, C0…C9}

Порождение: I3=>IC3=>I9=>B85=>a9

Контекстно-свободные грамматики типа 2

<идентификатор>::=<буква><конец идентификатора> <буква>::=a|b…|z

<конец идентификатора>::=<буква><конец идентификатора>|<цифра><конец идентификатора>| <пусто>

Предполагается, что идентификатор заканчивается символом <пустой символ> - обозначим его как e.

Vт = {0, 1…9, a, b, c…, z, e}

Vn ={I , B , C , E} I

R = {IBE, EBE, ECE, Ee, Ba..z, C0..9}

Сделаем ее автоматной:

I=>aE, E=>aE, E=>0E, E->a, E=>0

…

I=>zE, E=>zE, E=>9E, E->z, E=>9

Пример.

Построить грамматику, порождающую десятичные числа с точкой и знаком: +23.5; 0.5; -1.5; .01

<десятичное число с(.)>::=+<десятичное число с (.)>|<десятичное число с (.)>|- <десятичное число с (.)> < десятичное число с (.)>::=<целое число>.<целое число> |.<целое число>.

<целое число>::= <цифра>|<целое число><цифра> <цифра>::=0|1…|9

Vт ={0,1…9, +, -, .} Vn = {P, Q, N, D}

P – начальный символ грамматики.

P – десятичное число с(.) и со знаком

Q - десятичное целое число с(.).

N – целое число.

D – цифры.

R = {P+Q, PQ, P-Q, QN.N, Q.N , ND, NND, D0, D1…D9}

Переведем эту грамматику в автоматную:

R = {N0N,…, N9N, N0 ,…, N9, A.N, Q1D, …, Q9D , P+Q , P-Q, PQ}

Грамматика для выполнения арифметических операций.

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

Vт = {i, X, +, *, (, )} Vn ={ E }

E
R = { Ei+E;	- правило 1
Ei;	- правило 2
Ei*E;	- правило 3
E(E)}	- правило 4

E1=> i+E3=> i+i*E4=> i+i*(E)1=> i+i*(i+E)2=>i+i*(i+i)

Набор данных правил не обеспечивает скобки для первых операндов, то есть нельзя построить (i+i)+i.

Пример.

Vт = {i, X, +, *, (, )}

Vn ={ E }
E
R = { EE*E;	- правило 1
EE+E;	- правило 2
E(E);	- правило 3
Ei }	- правило 4

E2=>E+E1=>E+E*E4=>i+i*i

E1=>E*E4=>E*i2=>E+E*i4=>i+i*i

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

Недостаток - грамматика не обеспечивает приоритет операций сложения и умножения.

Чтобы обеспечить приоритеты операций мы можем операции суммирования сделать в

скобках, тогда:
R = ( E(E*E);	- правило 1
E(E+E);	- правило 2
Ei)	- правило 3

E 2=> (E+E) 1=> (E+(E*E)) 3=> (i+(i*i))

E 1=> (E*E) 2=> ((E+E)*E) 3=> ((i+i)*i)

Грамматика получилась неоднозначной, однако каждая операция оказалась в своей скобке.

Приоритетность операции * по отношению к операции + обеспечивается благодаря скобкам.

Недостаток – слишком много скобок.

Vт = {I, *, +, (, )} Vn ={ E,T, P}

E – арифметическое выражение. Т – слагаемое (или терм).

Р – произведение или сам множитель. R={ EE+T,

ET, TT*P, TP, P(E), Pi}

Нужно получить : (i+i) + i * i E1=>E+T2=>T+T4=>P+T5=>(E)+T1=>(E+T)+T3=>(E+T)+T*P2=>(T+T)+T*P4=>(P+P)+P*P6=

>(i+i)+i*i

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

При распознавании цепочки в процессе трансляции осуществляется ее сворачивание.

Пример. i+i*i<=666P+P*P<=44T+T*P<=3T+T<=2E+T<=1E

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

Соответствие конечных автоматов и автоматных грамматик.

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

Множество допустимых цепочек автомата называется языком, который допустим данным автоматом.

Утверждение:

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

Этапы для заданной автоматной грамматики.

1.Преобразование автоматной грамматики.

Пример. Пусть задана автоматная грамматика. Для ее преобразования:

a)Добавим нетерминальный символ Z VN.

b)Все правила вида Ax, где A VN, x VT преобразуем к виду: AxZ (правосторонняя грамматика), AZx (левосторонняя грамматика), в зависимости от того, какая грамматика.

c)Добавляем правило ZE, где E VN – пустой символ.

2.Построение графа автомата и его разметка.

Сопоставим каждому нетерминальному символу вершину графа, помеченную этим символом.

Для каждого правила AxB, где A,B VN, x VT ставится в соответствие дуга между

вершинами A и B, которые помечаются символом x:

x

A B

Этапы:

1.Начальному символу грамматики сопоставляется начальное состояние автомата.

2.Алфавиту нетерминальных символов – алфавит состояний.

3.Алфавиту терминальных символов – алфавит входных слов.

4.Операции ZE соответствует конечная вершина автомата.

5.Правилам грамматики соответствует функции перехода автомата.

Пример.
Vт = {с, d}
Vn ={I}
I
R = {Ic;	- правило 1
IIc;	- правило 2

IId} - правило 3

I2=>Ic3=>Idс3=>Iddc1=>cddc

Цепочка росла справа налево, так как грамматика левосторонняя.

Построим автомат:

Vт = {с, d}
Vn ={I, Z}
I
R = {IZc,	- правило 1
IIc,	- правило 2

IId,	- правило 3
ZE}	- правило 4
	d

I

Z

c

c

Z - конечная вершина

Это левосторонняя грамматика.

Автомат является недетерминированным, так как из I под воздействием с у нас два перехода - из IZ; II.

Переведем в правостороннюю грамматику:

Vт = {с, d} Vn ={I, Z}

I
R = {IсZ,	- правило 1
ZсZ,	- правило 2
ZZd,	- правило 3
ZE}	- правило 4

d

I

Z

c

c

Утверждение.

Для каждой левосторонней автоматной грамматики можно построить эквивалентную ей правостороннюю автоматную грамматику.

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

Построение грамматики по заданному конечному автомату

Пусть задан автомат в виде формировании предыстории, без выходного преобразователя.

A=<P, S, s0, φ>

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

Vт = P - поставить в соответствие алфавиту терминальных символов входного алфавита. Vn = S - алфавит нетерминальных символов – алфавит состояний.

I = s0