7. Цепочки вывода и дерево вывода

На основе заданной грамматики построить множество цепочек вывода. Если число без знака (допустим 575), то начинаем разбор по правилу с крайнего правого символа, если число со знаком (+ или -, т.е. -9856 или +9856), то начинаем разбор с крайнего левого символа.

S=>*575 S=>*-9856

P: S→T¹|+T²|-T³

T→F⁴|TF⁵

F→0⁶|1⁷|2⁸|3⁹|4¹⁰|5¹¹|6¹²|7¹³|8¹⁴|9¹⁵

S T TF T5 TF5 T75 F75 575

S=>⁷575 – 7 это то количество шагов, за которые мы получили 575

-T -TF -TFF -TFFF -FFFF -9FFF -9F5F -985F -9856

S=>⁸-9856

8. Преобразование конечного автомата (ка) в детерминированный конечный автомат (дка)

Задан КА M({H,A,B,S},{a,b,c}, ,H,{S})

: (a,H)=A (c,A)=B (c,H)=B (b,B)=A (a,A)=B (b,B)=S

Необходимо построить эквивалентный ему ДКА

M’(Q’,V’, ’,q₀’,F’)

1. Находим множество состояний эквивалентного ДКА

Поскольку в КА 4 состояния (n=4), то в ДКА будет m=2ⁿ-1=15

Q’={H,A,B,S,HA,HB,HS,AB,AS,BS,HAB,HAS,HBS,ABS,HABS}

2. Строим функцию переходов эквивалентного ДКА по таблице. Если в скобках в самой верхней строке, после запятой (т.е. допустим на месте, где написано «Н» в (a,H)=A), есть искомая буква из столбца, написанная также в скобках после запятой (т.е.допустим «Н» в H (*,H)), то пишем плюс. Если у нас две, три и более искомых букв, то, найдя в самой верхней строке в скобках после запятой любую из них, также ставим плюс.

	(a,H)=A	(c,H)=B	(a,A)=B	(c,A)=B	(b,B)=A	(b,B)=S
H (*,H)	+	+
A (*,A)			+	+
B (*,B)					+	+
S (*,S)
HA (*,HA)	+	+	+	+
HB (*,HB)	+	+			+	+
HS (*,HS)	+	+
AB (*,AB)			+	+	+	+
AS (*,AS)			+	+
BS (*,BS)					+	+
HAB (*,HAB)	+	+	+	+	+	+
HAS (*,HAS)	+	+	+	+
HBS (*,HBS)	+	+			+	+
ABS (*,ABS)			+	+	+	+
HABS (*,HABS)	+	+	+	+	+	+

Как заполнять ’:

1) Из самой верхней строки переписываем те значения, под которыми стоит знак плюса.

2) Заменяем значение после запятой на то, которое указано в столбце, т.е. например в 11 строке (a,H)=A заменим на (a,HAB)=A, (c,H)=B на (c,HAB)=B и т.д.

3) Если после такой замены у нас получается, например, (b,HAB)=A и (b,HAB)=S, то, в связи с тем, что первая маленькая буква у них совпадает, объединяем в (b,HAB)=AS.

’:

(a,H)=A (c,H)=B

2) (a,A)=B (c,A)=B

3) (b,B)=AS

4) -

5) (a,HA)=AB (c,HA)=B

6) (a,HB)=A (c,HB)=B (b,HB)=AS

7) (a,HS)=A (c,HS)=B

8) (a,AB)=B (c,AB)=B (b,AB)=AS

9) (a,AS)=B (c,AS)=B

10) (b,BS)=AS

11) (a,HAB)=AB (c,HAB)=B (b,HAB)=AS

12) (a,HAS)=AB (c,HAS)=B

13) (a,HBS)=A (c,HBS)=B (b,HBS)=AS

14) (a,ABS)=B (c,ABS)=B (b,ABS)=AS

15) (a,HABS)=AB (c,HABS)=B (b,HABS)=AS

3. Строим ДКА

4. Начальное состояние ДКА q₀’=H

Множество конечных состояний

F={S,HS,AS,BS,HAS,HBS,ABS,HABS}

8 конечных состояний

Исключим недостижимые состояния (получим граф переходов полностью определенного ДКА). Как это делать: смотрим по получившемуся графику. Из «Н» по стрелке мы можем переместиться только в «А» и «В». Из «А» можем только в «В», из «В» только в «AS», из «AS» только в «В». Дописываем состояние конца «S» и состояние ошибки «E».

Розовым обозначены недостающие a, b или c. Из каждого состояния обязательно должно выходить и a, и b, и c. И если какого либо из них не хватает, то мы дорисовываем стрелку до ошибки (error, состояние «E») и надписываем недостающие буквы (a, b, c).