Специальная математика

Вид материала

Конспект

Содержание 7.2. Деревья вывода 7.3. Классификация языков по Хомскому 7.4. Распознающие автоматы

Подобный материал:

• Направления работы семинара, 152.43kb.
• «Математика. Прикладная математика», 366.03kb.
• Программа подраздела «Философские проблемы математики», 94.9kb.
• Рабочая программа по курсу «Специальная педагогика и специальная психология» на 5 курсе, 94.48kb.
• Специальная обработка, 1624.5kb.
• Расшифровка : Математика, 146.94kb.
• Abramson Family Cancer Research Institute University of Pennsylvania (usa) Роль апоптоза, 15.2kb.
• Программа дисциплины "Математика и информатика" (раздел «Математика») (специальность:, 399.2kb.
• Пангеометризм и математическая мифология, 956.71kb.
• Строительство. Система производственного контроля. Часть, 84.92kb.

7.2. Деревья вывода

Порождение и свертывание можно также представлять с помощью деревьев вывода.

Пусть дана грамматика.

I  T

I  I + T

I I - T

T  M

T  T*M

T  T/M

M  (I)

M  K

K  a

K  b

K  c

Построим дерево вывода.

Для предложения a * b + c дерево вывода будет:


I


I T

T M




T * M K




M K c




a b


Этот же результат можно получить и другим способом:

I  I + I

I  I - I I

I  I*I

I  I/I I + I

I  (I)

I  a I * I c
I  b

I  c a b

7.3. Классификация языков по Хомскому

Н. Хомский предложил подразделять формальные грамматики, как и порождаемые ими языки на четыре типа.


Тип 0 - формальная грамматика, на правила которой не накладывается никаких ограничений. Для исследования они интереса не представляют – поскольку режим «делай, что хочешь» для математики и для практики редко представляют интерес.


Тип 1 . К этому типу относятся грамматики, правила которых имеют вид:

vw ::= vw, где

v, w  V^* - произвольные цепочки символов, возможно пустые;

  V_N - нетерминальный символ;

  V^*\{} [ иногда   V^* ].

[   V^* ].

Эти грамматики еще называют контекстно-зависимыми или КЗ-грамматиками.

Здесь строка  заменяется на строку  в рамках какого-то контекста. Часто используется на практике подмножество таких грамматик, называемое грамматиками непосредственных составляющих:

vAw ::= vw, где v,w, V^* , AV_N

При этом часто рассматриваются неукорачивающиеся грамматики (что обеспечивается непустой цепочкой ).


Тип 2 . К этому типу относятся грамматики, правила которых имеют вид:

 ::= 

  V_N - нетерминальный символ;

  V^*\{}:

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


Такие грамматики называются контекстно-свободными грамматиками или КС-грамматиками.

Языки программирования большей частью описываются грамматиками этого типа.


Тип 3 . К этому типу относятся грамматики, правила которых имеют один из двух видов:

 A := Bc

 A := b 

где A, B, C V_N ; b,c  V_T ;

Это так называемый леворекурсивный вариант. В качестве альтернативы возможен и праворекурсивный вариант:

 A := сB

 A := b 

Такие грамматики называют регулярными или автоматными грамматиками. Лексический анализ в компиляторе обычно наиболее целесообразно описывать с помощью этих грамматик.

7.4. Распознающие автоматы

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

Пример: Автомат, распознающий слова содержащие попарное вхождение букв а

и b, вроде aabbbbaa. f1, f2 - конечные состояния


2 a

a

b f1

a,b a a



4 1

b

a b

b f2



3

b

.

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


B

a,b b


A b F


a a

C

	0	0	0	1
	A	B	C	F
a	B,C		F
b	B	С,F

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


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

A  aB | bB | aC

B  bC | b

C  a

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