LibRar.Org.Ua — Бібліотека українських авторефератів

Загрузка...

Головна Електроніка. Обчислювальна техніка → Формалізоване проектування природно-мовних діалогових комп'ютерних систем

після чого транслювати цей вираз в польску нотацію. Далі в процесі сканування польського запису виразу Кліні конструюється необхідний автомат. Автомат, що ми отримали, не тільки розпізнає фрази данної граматики, але й транслює ці фрази у відповідні командні рядки.

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

: make {Act1} {Act2} {Act3};

: line;

: character;

: red;

: blue,

де Act1, Act2, Act3 - символи вихідної (інтерпретаційної) граматики.

Приклад граматики задає такі фрази:

make line red,

make line blue,

make character red,

make character blue.

Записуємо вираз граматики в алгебрі Кліні:

make{Act1}*(line+character){Act2}*(red+blue){Act3}

Перетворимо вираз алгебри Кліні в польський запис:

make{Act1} line character + {Act2} red blue + {Act3} * *

За цим польським записом будуємо автомати:


+ S0 S1

Line S1

Character S1

3 Ok {Act2}


+ S0 S1

Red S1

Blue S1

3 Ok {Act3}


Знаходимо композицію попередніх автоматів:


S0 S1 S2

Line S1

Character S1

Red {Act2}S2

Blue {Act2 S2

3 {Act3}Ok


У результаті маємо:


S0 S1 S2 S3

Make S1

Line {Act1} S2

Character {Act1} S2

Red {Act2} S3

Blue {Act2} S3

3 {Act3} Ok



До переваг такого підходу можна віднести ефективність за часом роботи, можливість реалізувати необхідну діагностику розпізнаних фраз.

Недоліком такого підходу є деяка обмеженість сфери його застосування. Він може бути використаний лише для випадку регулярних граматик.


В третьому розділі розглянуто підхід до проектування природно-мовного діалогового інтерфейсу, опціональну логіку, алгоритми генерації вихідної мови, природно-мовних відповідей системи та ходу діалогу.

Нехай задана деяка множина Х та її власна підмножина X0 (X0 М X). Множину Х будемо називати множиною задач, а її підмножину X0 – множиною тривіальних задач. Будемо вважати також, що на множині Х визначене відображення a зі значеннями у множині підмножин множини Х: .

Це відображення будемо називати відображенням переходу до підзадач або просто переходом до підзадач.

Нехай х О Х, тоді множину a (х) будемо називати множиною підзадач задачі х, а її елементи – підзадачами задачі х.

Будемо вимагати, щоб відображення a задовольняло наведеним нижче аксіомам.

Аксіома 1. Тривіальні задачі не мають підзадач: Ж.

Будь-яка нетривіальна задача має хоча б одну підзадачу: Ж.

Аксіома 2.

В множині Х будемо вважати виділеним елемент, який будемо називати цільовою задачею. Цільова задача не є підзадачею жодної задачі з Х:

~ .

Аксіома 3.

Будь-яка задача, яка не є цільовою, є підзадачею деякої задачі:

.

Аксіома 4 (антисиметричності).

Якщо х є підзадачею y, то у не може бути підзадачею х:

у О a(х) Ю х a(у).

Означення.

Нехай

Тоді послідовність: будемо називати ланцюгом підзадач задачі , чи просто ланцюгом підзадач.

Будемо вимагати також виконання такої аксіоми.

Аксіома 5.

Нехай - довільний ланцюг підзадач.

Тоді усі підзадачі цього ланцюга різні, тобто: . На множині задач Х визначимо два відображення: відображення визначення статусу задачі і відображення визначення стану задачі.

Нехай завдана двоелементна множина: S = {n, un}і відображення s : X ® S.

Це відображення будемо називати визначенням статуса задачі.

Якщо s(х) = n, то задачу х будемо називати необхідною (neсessary) для розв'язання цільової задачі . Якщо ж s(х) = un, то задачу х будемо називати не необхідною (чи опціональною) для розв'язання цілоьвої задачі .

Розглянемо також множину T = {t, i, f} і відображення t : Х ® Т.

Це відображення будемо називати відображенням визначення стану задачі, а множину Т будемо називати множиною логічних значень або множиною станів.

Якщо t(х) = t, то задачу х будемо вважати розв'язаною в позитивному сенсі (true–стан).

Якщо t(х) = f, то задачу будемо вважати розв'язаною в негативному сенсі (false–стан). Елементи множини Т будемо називати значеннями вірності задач.

Нижче наведені правила виконання операцій кон'юкції та диз'юнкції в тризначній логіці, які знадобляться нам в подальшому.

Аксіома 6.

Мають місце співвідношення:

Щ.1. t Щ t = t Ъ. 1. t Ъ t = t

Щ. 2. t Щ f = f Ъ. 2. t Ъ f = t

Щ. 3. t Щ i = I Ъ. 3. t Ъ i = t

Щ. 4. f Щ f =f Ъ. 4. f Ъ f = f

Щ. 5. f Щ i = f Ъ. 5. f Ъ i = i

Щ. 6. i Щ i = i Ъ. 6. i Ъ i = i


Крім того, ми постулюємо комутативність цих операцій. Ці операції природним чином розповсюджуються на довільну кількість операндів.

Сформулюємо деякі додаткові аксіоми.

Аксіома 7.

Нехай х ОХ, a(х) = {x1, …, xk} та s(хi) = n для i = 1, …, k,

тоді Щ Щ ... Щ . Аксіома 8.

Нехай х ОХ, a(х) = {x1, …, xk} та s(хi) = un для i = 1, …, k, тоді

Ъ Ъ ... Ъ .

Аксіома 9.

Нехай х ОХ, a(х) = {x1, …, xm, xm+1, …, xk } та s(хi) = n для i = 1, …, m,

s(хi) = un для i = m+1, …, k,

тоді

Щ Щ ... Щ .

Дамо тепер означення цільової структури.

Означення.

Кортеж B =

де

Х – множина, яка називається множиною задач,

Х0 – власне підмножина Х, яка називається множиною тривіальних задач,

{u, un} – множина значень статуса задач,

{t, i, f} – множина станів задач,

- елемент Х, який називається цільовою задачею,

a - відображення множини Х в множину його підмножин, який називається переходом до підзадач,

t - відображення Х в {t, i, f},

s - відображення Х в {n, un}.

Будемо називати цільовою структурою, якщо виконуються наведені вище аксіоми 1 – 10.

Для цільових структур зі скінченною множиною задач має місце лема, яка називається лемою обриву ланцюгів.

Лема 1.

Якщо В – цільова структура зі скінченною множиною задач Х, то довільний ланцюг підзадач обривається на деякій тривіальній задачі. Іншими словами, довільний ланцюг задач скінченний, а останнім елементом цього ланцюга є тривіальна задача.


Теорема 1.

Система аксіом 1 –10 несуперечлива.

Будемо розглядати змінні двох типів S1, S2, …, Sn, …, які