Построение распознавателей.

Пример : построить распознаватель из множества слов двоичного алфавита длиной в три буквы, слова с двумя единицами, т.е. цепочек из «0» и «1» длиной три.

V_t = {0 , 1}

L = {011 , 101 , 110}

V_n = {I , A , C , Z , B , D , e}

I 01 A1C1Z

I 1 B 0 D 1 Z

I 1 B 1 E 0 Z

R = {I0A , I1B , A1C , B0D , B1e , C1Z , D1Z , e0Z , Ze}

Пример 2:

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

Введем два конечных состояния Z₁для допустимых слов иZ₂для недопустимых слов.

I 0 A 1 C 1 Z₁

I 1 B 0 D 1 Z₁

I 0 A 0 F 0 Z₂

I 0 A 0 F 1 Z₂

I 0 A 1 C 0 Z₂

I 1 B 0 D 0 Z₂

I 1 B 1 E 1 Z₂

P = {0 , 1}

V_n = {I , A , C , Z_{1 ,} Z₂ , B , D , e , F } = S

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