Представлення за допомогою символів

Щоб будувати інтелектуальні системи, мова представлень повинна відповідати наступним вимогам.

Бути досить виразною, щоб дозволяти представлення всіх реальних станів.

Бути стислою настільки, щоб обчислення піддавались управлінню.

Мати форму, відповідну для міркувань, щоб модель реальності могла міняти свій стан.

Мал.2. Цикл продукційної системи

Логіка використовується математиками для того, щоб доводити правильність, або неправильність тверджень. Всі головні умови представлень, включаючи Rules, Semantic nets і Frames, можуть бути переведені у форму логіки, відому як числення предикатів першого порядку. Коротке обговорення числення предикатів першого порядку дається відразу після розгляду більш простої форми логіки, названої пропозиційним численням або численням висловів.

Числення висловів

Висловом є пропозиція, якій може бути привласнене значення ІСТИНА або ХИБНІСТЬ. Наприклад, "Сьогодні йде дощ" або "Мідь є метал" є або правильними, або помилковими твердженнями. В рамках числення висловів можна представляти пропозиції в символьному вигляді, створювати складні пропозиції з інших пропозицій, використовуючи зв'язки, і виводити висновки, щоб знайти значення пропозиції. Синтаксис числення висловів описує те, як створюються пропозиції (включаючи складні вирази), граматика визначає правила, по яких з'ясовується синтаксична коректність пропозиції. Семантика числення висловів визначає те, як визначити співвідношення між пропозицією і значеннями ІСТИНА або ХИБНІСТЬ.

Елементарною пропозицією є простий вислів типу "Сьогодні йде дощ", і такі пропозиції часто представляються прописними буквами, наприклад Р або Q. Складна пропозиція створюється за допомогою зв'язку, що сполучає два або декілька елементарних пропозицій. Круглі дужки використовуються для того, щоб вказати пріоритет операцій при комбінуванні елементарних пропозицій за допомогою зв'язків. У табл.1 дано пояснення зв'язку, а в табл.2 приведені правила граматики для логіки висловів. Граматика може використовуватися для аналізу речення і перевірки того, що воно синтаксично правильне. Наприклад, неформальний опис перевірки синтаксичної правильності виразу ( ( P /\ Q ) \/ R ) = > S пропонується в табл.3.

Таблиця 1. Логічні зв'язки

Зв'язка	Приклад
/\ (І) Звана кон'юнкцією	Сьогодні йде дощ І я промок Р/\Q, де Р позначає кон'юнкт "Сьогодні йде дощ”; а Q - кон'юнкт "Я промок"
\/ (АБО), Звана диз'юнкцією	Салі пішла в магазин АБО Том пішов в магазин Р\/Q, де Р позначає диз'юнкт "Салі пішла в магазин", а Q - диз'юнкт "Том пішов в магазин"
(НЕ) Звана запереченням	Слон НЕ розовий. Р, де Р позначає "Слон розовий"
=> (ВАБИТЬ) Звана імплікацією або твердженням "якщо..., то... "	ЯКЩО я на вулиці І йде дощ, ТО я промокну (P/\Q) =>R, де Р позначає "Я на вулиці",Q позначає "Йде дощ", а R - "Я промокну"
<=> (ЕКВІВАЛЕНТ) Еквівалентністю або подвійною імплікацією	Вирази по обидві сторони цього зв'язку повинні бути логічно еквівалентними

Таблиця 2. Правила граматики для логіки висловів

Привило граматики	Пояснення
Пропозиція→Елементарна- пропозиція \| Складна - пропозиція	Пропозиція є або елементарною або складною
Елементарна - пропозиція → Р \| Q \| R \|...	Елементарна пропозиція позначається прописною буквою, як правило з останньої третини алфавіту
Елементарна - пропозиція Істина \| Брехня	Елементарна пропозиція може представлятися також значеннями ІСТИНА або БРЕХНЯ
Складна - пропозиція Пропозиція Зв'язок Пропозиція Пропозиція \| (Пропозиція)	Складна пропозиція будується з двох інших пропозицій і зв'язку. Заперечення пропозиції теж є пропозицією, і поміщення пропозиції в дужки теж в результаті дає пропозицію
Зв'язок →/\ \| \/ \| \| => \| <=>	Зв'язком є будь-який з логічних символів, представлених в табл.1

Таблиця 3. Приклад синтаксичного аналізу

Кроки	Пояснення
( (Р/\Q) /\R) =>S	Відповідно до першого правила пропозиція є або елементарною, або складною. Очевидно, що цей вираз не є елементарною пропозицією, тому ми повинні перевірити, чи воно є складною пропозицією
( (Р/\Q) /\R) =>S	Правою стороною виразу є S, а S є елементарною пропозицією відповідно до другого правила
( (Р/\Q) /\R)	Ми повинні показати, що (P/\Q) /\R є складною пропозицією
(Р/\Q) /\R	Порівнюючи з правилом "Пропозиція Зв'язок Пропозиція" робимо вивід, що R є пропозицією, оскільки воно є елементарним
(Р/\Q)	Ми повинні показати, що Р/\Q є складною пропозицією
Р/\Q	Знову порівнюючи з правилом "Пропозиція Зв'язок Пропозиція" робимо вивід, що і Р, і Q є пропозиціями

Семантика числення висловів визначається за допомогою таблиці істинності. Всі зв'язки, за винятком заперечення, є бінарними відносинами, тому у визначеннях потрібно використовувати два символи. Пропозиція може приймати значення ІСТИНА або ХИБНІСТЬ, тому для бінарних зв'язків є чотири можливі комбінації, як показано в табл.4.

Таблиця 4. Таблиця істинності

p	q	-р	р/\q	рvq	р=>q	p<=>q
істина	істина	хибність	істина	істина	істина	істина
істина	хибність	хибність	хибність	істина	хибність	хибність
хибність	істина	істина	хибність	істина	істина	хибність
хибність	хибність	істина	хибність	хибність	істина	істина

Здебільшого визначення зв'язків інтуїтивно зрозумілі. Наприклад, "Сьогодні йде дощ" І "Сьогодні НЕ йде дощ", очевидно, ХИБНІСТЬ, що підтверджується таблицею істинності, якщо знайти в ній можливі значення ІСТИНА /\ ХИБНІСТЬ або ХИБНІСТЬ /\ ІСТИНА. Знаходження імплікації часто викликає питання, оскільки ми інтуїтивно намагаємося застосувати інтерпретацію, засновану на нашому загальному розумінні мови. Наприклад, можна заявити, що пропозиція типу "Якщо число 5 парно, то мій автомобіль рожевий" (що має форму Р => С2) є брехнею, оскільки воно не має сенсу. Проте, відповідно до визначення імплікації, цей вираз виявляється істинним, незалежно від того, чи є ваш автомобіль рожевим чи ні: ми знаємо, "число 5 парно" є брехнею, так що відповідною комбінацією повинна бути або ХИБНІСТЬ => ІСТИНА (автомобіль рожевий) або ХИБНІСТЬ => ХИБНІСТЬ (автомобіль не рожевий). Ми прагнемо інтерпретувати вираз типу "якщо то..." як причинно-наслідкове, і тому пропозиція "Якщо число 5 парне, то мій автомобіль рожевий" виглядає безглуздим, оскільки визначення числа 5 не робить ніякого впливу на колір вашого автомобіля. Тут слід зрозуміти, що імплікація в численні виразів не вимагає, щоб був хоч якийсь смисловий зв'язок між пропозиціями по обидві сторони імплікації, що зв'язує їх. Знання того, що Р є ХИБНІСТЬ, не дає ніякої можливості зробити вивід про істинність Р. Наприклад, пропозиція "Якщо акумулятор розрядився, то автомобіль не заведеться" дає нам можливість припустити, що істиною є "автомобіль не заведеться", якщо істиною також є "акумулятор розрядився", але правило не говорить нам нічого про здатність автомобіля завестися, якщо ми не знаємо, що "акумулятор не розрядився" - автомобіль може не завестися з цілого ряду причин абсолютно іншого роду. Якщо цих пояснень вам все ще недостатньо, краще всього інтерпретувати Р ==> Q просто як пропозиція, що дозволяє зробити вивід про те, що Q є ІСТИНА, якщо ми знаємо, що Р є ІСТИНА.

Існує цілий ряд правил виведення логіки висловів, і вони представлені в табл.5.

Таблиця 5. Правила виведення логіки висказаного

Правило Пояснення

Приклад 1

Є наступна інформація.

Якщо акумулятор машини розряджений, то машина не заводиться. Якщо машина Джона не заводиться і поточний час виявляється пізнішим 8 годин ранку, то Джон запізниться на потяг. Одного разу вранці після 8 годин ранку акумулятор машини Джона виявився розрядженим.

Використовуючи логічні правила виводу, покажіть, що Джон запізнився на потяг.

Розв ’ язання 1

У символьному вигляді інформація може бути представлена таким чином.

Р: акумулятор машини розряджений.

Q: машина не заводиться.

R: час після 8 ранку.

S: Джон запізнився на потяг.

Правило 1. Р => Q.

Правило 2. Q ^ R =>S

Відомо, що Р і R є ІСТИНА. Завданням є доказ S. Доказ будується таким чином.

1 Р Дано.

2 R Дано.

3 Q Виходить з кроку 1 і правила 1 за правилом modus ponens.

4 Q ^ RВиходить з кроків 3 і 2 за правилом інтродукції 1.

5 S Виходить з кроку 4 і правила 2 за правилом modus ponens.

Числення предикатів

Числення висловів припускає, що світ можна моделювати за допомогою фактів. Але для реальних застосувань числення висловів не підходить. Розглянемо, наприклад, число пропозицій, які будуть потрібні для моделювання запізнення на роботу, скажімо, 50 чоловік. Для цього потрібно допускати узагальнені вирази. Числення предикатів (або, точніше, числення предикатів першого порядку) розширює числення висловів так, що світ виявляється таким, що складається з об'єктів, відносин і властивостей. Ця метод допускає узагальнені твердження, вводячи в розгляд змінні, а також квантори, що дозволяють визначати властивості сукупності об'єктів. Розглянемо твердження "Якщо конем володіє Джон, то кінь є чистокровним". Це твердження посилається на сукупність об'єктів, а саме, на всіх коней, якими володіє Джон, у наслідок чого відпадає необхідність посилатися на кожен екземпляр (тобто накожного з коней Джона) окремо. Це твердження є узагальненим і позбавляє від необхідності формулювання відповідного твердження для кожного з коней Джона. Можна перефразовувати твердження і сказати "Всі коні, якими володіє Джон, є чистокровними". Тут для вказівки того, що властивість "чистокровний" застосовується до всієї сукупності коней Джона, використовується квантор (всі). Слово "володіти" є бінарним предикатом, що описує відношення між Джоном і конем, а слово "чистокровний" є унарним предикатом, що описує властивість коня. В термінах числення предикатів твердження "Всі коні, якими володіє Джон, є чистокровними" в символьному вигляді записується так:

х (Кінь (х) ^{^} Володіти (Джон, х)) => Чистокровний (х).

Символ називається квантором спільності і читається як "для всіх" або "кожен". У численні предикатів визначається і інший символ, а саме, символ , так званий квантор існування, який читається як "існує". Наприклад, коли ми говоримо "Джон має чистокровного коня", це означає, що існує принаймні один кінь (а можливо і більше) в колекції Джона, що є чистокровним. На мові предикатів це твердження виглядає таким чином:

х Кінь (х) ^{^} Володіти (Джон, х) ^{^} Чистокровний (х).

Числення предикатів пропонує запис який є більш стислим, ніж звичайна розмовна мова. У системі числення предикатів одна пропозиція відповідатиме безлічі пропозицій звичайної розмовної мови. Числення предикатів зменшує і неоднозначність. Наприклад, "Всі коні не є чистокровними" можна сплутати з "Не всі коні є чистокровними", і плутанина вирішується за допомогою знання того, що існують інші породи коней. Уявлення кожної з пропозицій в термінах предикатів показує їх різницю:

коні Чистокровний (кінь) і коні Чистокровний (кінь).

Перша пропозиція дійсно стверджує, що всі чистокровні вимерли (жодного екземпляра не існує), а друга пропозиція стверджує, що "то, що кожен кінь є чистокровним, невірно".

Інші символьні мови

Є багато мов уявлень, але вони мають багато спільного. Популярні мови типу FOPC, Frames або Semantic nets по суті еквівалентні і мають цілий ряд загальних ключових елементів:

об'єкти, такі як, наприклад, м'яч, персона, човен, велосипед або філософ;

відносини між об'єктами, такі як, наприклад, Джон є батьком Кім, або паровоз тягне склад;

властивості, такі як, наприклад, моя машина зеленого кольору, Девід має зріст шість футів.

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

Мова Ргоlog

Мова Рrоlog формально не є мовою уявлень, але її синтаксис використовується в наступному розділі, тому ми приведемо її опис.

Мова Ргоlog є мовою програмування штучного інтелекту, в якому дані представляються як безліч відносин між об'єктами. Програма на мові Ргоlog складається із списку фактів і правил, і ця мова є важливою завдяки тому, що вона має вбудований механізм виведення висновків, який дає можливість отримати відповіді на питання про запрограмовані знання. Синтаксис мови Рrоlog опирається на обчисленні предикатів. Відношення типу "Джон любить Мері" записується так:

любить (джон, мері).

Предикат (тобто відношення) і об'єкти відношення повинні починатися з букви нижнього регістру. Вказане вище відношення трактується як факт, іншими прикладами фактів є:

метал (мідь) - мідь є метал;

грають (джон, мері, теніс) - Джон і Мері грають в теніс.

Змінна повинна починатися з символу верхнього регістра. Коли змінна посилається на константу (тобто на конкретний екземпляр, такий як Джон), говорять, що змінна конкретизована. Змінна може бути конкретизована в результаті порівняння виразів. Наприклад, припустимо, що база даних містить любить (Джон, Мері). Тоді можуть бути поставлені наступні питання.

Хто любить мері?

любить (Х, мері)

відповідь X = джон

X конкретизована значенням Джон

Хто є тим, кого любить джон?

любить (джон, X)

відповідь X = мері

Хто кого любить?

любить (Х, V)

відповідь X = джон, У = мері

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

дядько (Х, У): - батько (Z. У), брат (Z, X).

Символ ": - " використовується замість ЯКЩО, а символ ","замість І. Таким чином вказане правило стверджує, що

X є дядько У, якщо Z є батько У і брат є X.

Приклад конкретизації цього правила показаний на мал.3.

Брат Джон

Девід

Дядько

Батько

Малкольм

дядько (джон, малкольм): - батько (девід, малкольм), брат (девід, джон).

Мал.3. Правило мови Prolog, конкретизоване семантичним уявленням, показаним у вигляді діаграми

Змінна є локальною по відношенню до виразу (тобто факту або правила): змінна з одним і тим же ім'ям, що з'являється в двох різних правилах, інтерпретуватиметься в мові Prolog якщо має різні імена.

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

мати одне і те ж відношення;

мати однакове число аргументів;

давати збіг по кожному аргументу.

Порівняння аргументів визначається таким чином.

1. Константи: дві константи дають збіг, якщо вони є ідентичними рядками.

2. Константа і змінна: якщо змінна не конкретизована, то вона даватиме збіг з будь-якою константою і буде конкретизована цією константою; конкретизована змінна даватиме збіг з константою у відповідності с п.1.

3. Змінні: дві довільні змінні (не конкретизовані) завжди дають збіг, а якщо надалі одна змінна стає конкретизованою деякою константою, то інша змінна також буде конкретизована тією ж константою.

Приклади збігів показані в табл.6

Таблиця 6. Порівняння зразків в мові Prolog
Вираз 1	Вираз 2	Збіг
любить (Х, Мері)	любить (Джон, Мері)	так
любить (Джон, X)	любить (Джон, Мері)	X = Мері
любить (Джон, Мері)	подобається (Джон, Мері)	Немає
любить (Х, У)	любить (Джон, Мері)	X = Джон У = Мері
любить (Джон, Мері)	любить (Х, X)	Немає
любить (Х, Мері) і X = Джон	любить (У, Мері)	У = X = Джон
штовхає (Джон, Кріс)	штовхає (Джон, Кріс, рука)	Немає

Приклад 2.

Нижче приведена програма на мові Prolog. Поясніть, як відповість Prolog на запит

? - дядько (джон, X)

де "? - " є запрошенням Prolog. Лістинг програми наступний.

Батько (девід, малкольм).

Дядько (грехим, малкольм).

Брат (девід, джон).

4 дядько (Х, Y ): - батько ( г, Y ), брат ( Z , X ).

Номери рядків показані для зручності.

Розв ’ язання 2.

Prolog шукатиме вираз з предикатом "дядько" і двома аргументами. Перший такий вираз знаходиться в рядку 2, але збігу не спостерігається, оскільки перший аргумент "Грехим" не відповідає аргументу "Джон". Другий вираз, що містить "дядько", знаходиться в рядку 4, але для того, щоб Prolog "досяг успіху" в досягненні мети (метою є показати, що Джон є чийсь дядько), повинна досягнути задоволена права сторона виразу: повинна збігатися з виразом - батько (Z, Y) і брат (Z, X). X в запиті і X в правилі вважаються різними, так що ми маємо наступне:

Запит: дядько (джон, X1) повинен порівнюватися з дядько (Х2, Y), що є лівою частиною правила в рядку 4. Збіг виходить для Х2 = Джон і Y = Х1 (або Х1=Y). Тепер завдання є доказом батько (Z, X1) і брат (Z, Джон). Батько (Z, X1) співпадає з рядком 1 при Z = Девід і X1 = Малкольм. Тепер завдання є виконане і задовольняє рядок 3.

Prolog відповість що X = Малкольм.

Розуміння мови

Для людей спілкування за допомогою звичайної розмовної мови є, очевидно, нескладним завданням, а ось всі комп'ютерні системи, що моделюють цей процес, до цих пір мають можливості, істотно поступливі можливостям звичайного першокласника. Створені системи (тобто машинні моделі) розуміння мови, що довели свою виняткову практичну користь. Наприклад, можна побудувати комп'ютеризовану систему замовлення авіаквитків, яка буде вести діалог з користувачем на звичайній мові, така система правильно відповідатиме на більшість питань користувача. Необхідність в наявності систем розуміння мови стає очевидною, якщо пригадати про можливості, що виникають у зв'язку з прискоренням розвитку засобів телекомунікацій. Все більш звичними стають електронні банківські розрахунки в інтерактивному режимі, і постійно росте інтерес до розробки автоматизованих агентів, здатних здійснювати пошук і аналізувати величезні об'єми даних в Інтернеті. Проте всі такі застосування мають досить вузькі області застосування. Обмеження області застосування дозволяє понизити рівень складності розробки за рахунок скорочення розміру словника і спрощення завдання розуміння сенсу запиту. І хоча число вузькоспеціальних застосувань для розпізнання розмовної мови за останні декілька років помітно виросло, ми все ще не можемо сказати, коли ж машинні можливості розуміння мови наблизяться до того рівня розуміння, на якому знаходиться людина. Розмовна мова є дуже виразною формою комунікації, що ставить перед ученими і програмістами масу проблем. Декілька прикладів представлено в табл.7.

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

Таблиця 7. Деякі труднощі обробки розмовної мови

Тип проблеми	Приклад	Пояснення
Передача однакового сенсу за допомогою різних форм висловлювань	1. Стюарт розбив вазу 2. Ваза була розбита Стюартом	(1) виражено в активній формі (2) є пасивною формою (1)
Роль приводу "с"	1. Незнайомка штовхнула хлопчика з дівчинкою 2. Незнайомка штовхнула хлопчика з собакою	У (1) привід "с" означає об'єднання тих що постраждали, тоді як в (2) привід "с" додає опис хлопчика
Багато слів мають декілька значень	1. Догляд за дитиною 2. Відхід з сцени	У (1)"відхід" позначає постійний нагляд і турботу, тоді як в (2)"відхід" позначає одноразову конкретну дію
Смислове узгодження слів	1. Викрадення автомобіля є небезпекою 2. Викрадення автомобіля є небезпечним	У (1) мається на увазі небезпека для власника, тоді як в (2) мається на увазі небезпека для злочинця
Порядок слів	1. Музей зберіг дохід 2. Дохід зберіг музей	У (1) може матися на увазі, що був збережений дохід, а в (2) - що був збережений музей

Як і у разі більшості інших складних завдань, завдання реалізації системи розуміння мови на комп'ютері розбивається на декілька рівнів. Трьома рівнями, що розглядаються в дискусіях, присвячених системам розуміння мови, є синтаксичний рівень, семантичний рівень і прагматичний рівень. Синтаксичний рівень стосується того, як слова об'єднуються в структури, які називаються виразами, і як вирази об'єднуються в структури, які звуться пропозиціями. Для перевірки того, чи є деяка пропозиція допустимою (тобто граматично правильним) і для розбиття пропозиції на складові частини, зазвичай використовуються правила граматики. Семантичний і прагматичний рівні стосуються значення пропозицій. На семантичному рівні виділяється зміст (суть пропозиції), і для виразу змісту часто використовуються певні логічні форми. Наприклад, пропозиції

Джон ударив по м'ячу.

Чи ударив Джон по м'ячу?

мають один і той же зміст, який в мові Prolog може бути представлене у вигляді:

ударив (Джон, м'яч).

Маючи можливість автоматизувати синтаксичний і семантичний аналіз, ми можемо затверджувати:

Джон ударив по м'ячу. ударив (Джон, м'яч)

Потім ми можемо запитати:

Хто ударив по м'ячу? ударив (Х_, м'яч)

По чому ударив Джон? ударив (Джон, X)

Хто по чому ударив? ударив (Х, Y)

Прагматичний аналіз стосується інтерпретації пропозиції в контексті. Так, питання про інтерпретацію займенника "Він" в пропозиції він забив гол може бути вирішений тільки в контексті (тобто з використанням сусідніх пропозицій). Щоб відповісти на питання "Хто забив гол?", ми повинні вирішити, на кого саме указує займенник "Він".

Пропозиція.

Чи можете ви приготувати чай?

Часто означає прохання приготувати чай, але може мати і буквальний сенс: "Чи умієте ви готувати чай?". Контекст також використовується для того, щоб обмежити сенс певних слів. Слово "любити" в буденному використанні має сенс, що виражається у формі

любить (людина, об'єкт).

Цей сенс також мають такі подібні вирази як: "Джон любить Мері", "Джон любить роботу" і "Джон любить шоколад".

У контексті відносин між людьми "любить" може бути обмежено формою любить (людина, людина),і в цьому сенсі ми можемо припускати, що "Венера" в виразі - любить (джон, венера) є ім'ям жінки, а не назвою планети. В даному випадку обмеження вирішує потенційну неоднозначність тим часом, що може позначати "Венера" - ім'я людини або назва планети. Давайте тепер коротко розглянемо сам процес синтаксичного і семантичного аналізу.

Синтаксичний аналіз

Фрагмент тексту складається з пропозицій, а кожна пропозиція компонується з виразів, які можуть містити під вирази і, кінець кінцем, складаються із слів. Граматику визначає спосіб, відповідно до якого слова і вирази можуть об'єднуватися в пропозиції. Граматика може бути представлена з допомогою багатьох будь-яких мов уявлень, але найчастіше для цього використовують формат правил виводу. На мал.4 показана структура пропозиції “ The dog ran across the road ” англійської мови (у перекладі воно означає "собака біг через дорогу").

Мал.4 . Приклад граматики, вираженої правилами виводу. S - означає пропозицію, N - іменник, А - прикметник, Р - привід, D - визначник (артикль), V - дієслово, ІР - іменна група, V Р - дієслівна група, АР - група прикметника, РР - прийменникова група.

Мал.5. Дерево синтаксичного аналізу для пропозиції “ The dog ran across the road".

Речення аналізується з метою виділення вхідних в його структуру виразів і з метою його перевірки відповідно граматиці. Для аналізу речення потрібний також словник. Словник визначає категорії слів (N, V, Р, А, D). Такий аналіз може бути інтерпретований як пошук, при якому підтримується стек дублювання для резервного копіювання станів, щоб була можливість повернутися з тупикового стану.

Приклад 3. Ілюструйте те, як можна у вигляді пошуку провести синтаксичний аналіз пропозиції " The dog ran across the road ". Використовуйте наступну граматику:

S → NP VP

NP→ D AP ID N

PP → P NP

VP→ V PP

AP→ AN

і наступний словник:

D→ the N→ dog I road V →ran P→ across

Розв ’ язання 3. Процес показаний в табл.8, а стани, що генеруються при цьому, - на мал.6.

Таблиця 8. Синтаксичний аналіз пропозиції " The dog ran across the road ", то розглядається як пошук

Поточна спроба	Стек слів		Стек відвідування	Стек дублювання
S→NPVP	the dog ran across the road		NP VP
NP→ D АР	the dog ran across the road		DAP VP	NP→DN
D → the	dog ran across the road		APVP	NP→DN
AP→AN	dog ran across the road		VP	NP→DN
dog не відноситься до категорії А, тому повернення
NP→DN	the dog ran across the road		DN VP
D → the	dog ran across the road		NVP
N →dog	ran across the road		VP
VP →v PP	ran across the road		VPP
V → run	across the road		PP
PP → PNP	across the road		PNP
P → across	the road		NP
NP → D AP	the road		DAP	NP→DN
D → the	road		AP	NP→DN
AP→AN	road		AN	NP→DN
road не відноситься до категорії А, тому повернення
NP→DN	the road	DN
D → the	road	N
N road

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

Семантичний аналіз

Семантичний аналіз часто реалізується як етап синтаксичного аналізу в результаті додавання до правил граматики відповідних властивостей і використання порівняння зразків. Тут ми маємо можливість сказати тільки декілька слів про те, як виділяється суть пропозиції у формі мови Ргоlog. Граматика

SN→PVP

NP→N

N →name

VP → V NP

name → мери | джон

verb →любить