spoPresentation2

Построение регулярного выражения, соответствующего регулярной грамматике

3.1. i=1. Поскольку i=1, то подстановки не выполняются

3.2. X1 = X		n

3.3. X1 = E1D11* = X2n ( 0+n )*

3.1. i=2: k = 1. X1 отсутствует в уравнении X2

3.2. X2 = i[ + X3[ .

3.3. Уравнение вида X = E само по себе

является решением X2 = i[ + X3[

121

Построение регулярного выражения, соответствующего регулярной грамматике

3.1. i=3, k = 1, 2.

k=1: X3 = X1] = X2n ( 0+n )* ]

K=2: X3 = ( i[ + X [ ) n ( 0+n )* ]

3.2. X3 = X		0+n )* ]

3.3. X3 = E3D33* = i[ n ( 0+n )* ] ( [ n ( 0+n )* ] )*

3.4. Данное РВ и будет ответом

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

122

Построение регулярного выражения, соответствующего регулярной грамматике

3.5. i = n-1, n-2,…, 1; k = n, n-1, …, i+1

i=2, k=3: X2=i[+X3[ = i[ +i[n(0+n)*]([n(0+n)*])*[

i=1, k=3: X1=X2n ( 0+n )* Без подстановки

i=1, k=2:

X1=X2n(0+n)*=(i[+i[n(0+n)*]([n(0+n)*])*[) n ( 0+n )*

123

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

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

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

V – конечное множество допустимых входных символов (алфавит автомата)

G - функция переходов, отображающая декартово произведение множеств VuQ во множество подмножеств Q: G(a,q)=R, a V, q Q, R Q

q0 – начальное состояние автомата, q0 Q

F – непустое множество конечных состояний, F Q, Fz

124

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

КА полностью определен, если в каждом его состоянии существует функция перехода для всех возможных входных символов:

a V, q Q G(a,q)=R, R Q

В начале работы автомат всегда находится в состоянии q0

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

125

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

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

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

126

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

КА M (Q, V, G, q0, F) принимает цепочку символов ZV +, если получив на вход эту

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

Язык L(M), заданный КА – это множество всех цепочек символов, которые принимаются этим автоматом

Два КА эквивалентны, если они задают один и тот же язык

Все КА являются распознавателями для регулярных языков

127

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

Граф переходов КА – это ориентированный граф, в котором состояния КА соответствуют вершинам, а переходы

G(p,a)=q, a V, p,q Q - дугам (p,q),

помеченным символом а

Вершины, соответствующие начальному и конечным состояниям, выделяются

128

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

Пример

M ( {H,A,B,S}, {a,b}, G, H, {S} )

G: G(H,b)=B, G(B,a)=A, G(A,b)={B,S}

	b	a		b
H	B	b	A	S

129

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

Чтобы исключить ситуации, из которых нет

переходов по входным символам, в КА может быть

добавлено еще одно состояние, на которое

замыкают все неопределенные переходы,

преобразуя автомат в полностью определенный

Это дополнительное состояние соответствует

состоянию ошибки

		b	a		b
H		B	b	A	S
					a
	a	b	Е
					a, b

a, b	130