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

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

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

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

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

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

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

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

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

vaw ::= vbw, где

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

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

b Î V^*\{e} [ иногда b Î V^* ].

[ b Î V^* ].

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

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

vAw ::= vaw, где v,w, aÎV^* , AÎV_N

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

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

a ::= b

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

b Î V^*\{e}:

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

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

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

æ A := Bcö

è A := b ø

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

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

æ A := сBö

è A := b ø

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

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

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

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

2 a

a

b f1

a,b a a

4 1

b

a b

b f2

b

.

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

B

a,b b

A b F

a a

C

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

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

A ® aB | bB | aC

B ® bC | b

C ® a

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