![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Виды формальных грамматикСтр 1 из 2Следующая ⇒
Методы и системы искусственного интеллекта
Лекция 3
Формальные грамматики и семантические сети. Фреймы
Основные определения теории формальных грамматик
Словарь (алфавит) (V) – конечное непустое множество символов (элементов). Элементы – буквы, слова, образы, математические знаки и др. Морфема – элементарная единица слова. Цепочка w (предложение) – конечная последовательность символов. Цепочки образуются с помощью конкатенаций (объединений). |w| - длина цепочки. Язык над данным алфавитом – произвольное (возможно, бесконечное) множество предложений в этом алфавите. Формальная грамматика – это четверка G = (VT, VN, P, S), где: VT – алфавит терминальных (основных) символов, из этих символов строятся языковые цепочки; VN – алфавит нетерминальных (вспомогательных) символов, конечное непустое множество, вспомогательные символы обозначают классы слов или словосочетаний, причем VN ∩ VT = Æ; VN È VT = V – алфавит грамматики G; P – множество правил подстановки (или продукций); S – начальный/корневой символ (цель грамматики, аксиома), выделенный нетерминальный символ, который означает класс языковых объектов, для которых предназначена данная грамматика, SÎ VN. Длина вывода – число применений правил вывода. Законченный вывод цепочки – не существуют никакой другой, выводимой из неё.
Основные определения теории формальных грамматик (продолжение)
V* – все возможные цепочки символов (предложения) алфавита V. V+ – множество V*\{Λ, где Λ – пустая цепочка).
Правило подстановки (элемент множества P) будет иметь вид: α → β, где α Î V+, β Î V*, причем хотя бы один символ предложения α должен быть нетерминальным.
В любом предложении вхождение цепочки символов α может быть заменено цепочкой β: (" γ, δ Î V*) γ α δ Þ γ β δ В этом случае говорят, что β выводима из α.
Символ «→» применяется при записи правил вывода. Символ «Þ» используется для обозначения возможности вывода одного предложения из другого в результате применения некоторого количества (одного или нескольких) правил грамматики. Вывод в грамматике начинается с корневого символа S и заключается в последовательном применении правил подстановки. Предложение называется терминальным, если оно состоит только из терминальных символов.
Γ (G) – язык, порождаемый грамматикой G и содержащий все терминальные предложения (и только их), выводимые из начального символа S: Γ (G) = {α | (α Î VT*) & (S Þ α)}
Виды формальных грамматик
Распознающие – для любой распознаваемой цепочки она решает, является ли эта цепочка правильной с точки зрения конкретного языка. Порождающие – может построить любую правильную цепочку. Преобразующие – для любой правильной цепочки строит её отображение в виде правильной цепочки.
Пример 1. Дано: алфавиты VT = {a, b}, VN = {S, A, В}; правила подстановки P = {S → AS, S → SB, S → Λ, A → ab, B → ba}.
В грамматике с такими компонентами могут быть выведены любые цепочки вида (ab)n (ba)m. Например: S Þ AS Þ AAS Þ AASB Þ AAB Þ abAB Þ ababB Þ ababba.
Выводы: • На каждом шаге вывода может существовать выбор из нескольких возможностей применения грамматических правил. Смысл грамматики - символьное представление, задающее пространство структурированных объектов. • Конечный набор правил может порождать язык, содержащий бесконечное количество предложений. • Различные грамматики могут порождать одинаковые языки (такие грамматики называются слабо эквивалентными). Например, грамматика, состоящая из элементов VT = {a, b}, VN = {S}, P = {S → abS, S → Sba, S → Λ }, порождает тот же язык, что и грамматика, рассмотренная выше.
|