Теорема о разрешимости для информативного представления

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

Теорема о неразрешимости для текстуального представления грамматик

(метод восстановления грамматик перечислением):

Пускай произвольное множество грамматик, содержащее все грамматики, каковые порождают конечные я зыки + одна грамматика порождает нескончаемый язык, тогда при текстуальном представлении задача восстановления грамматики неразрешима для произвольной грамматики из этого мн-ва.

Приведенные теоремы серьёзны по следующим обстоятельствам:

1.они показывают ограничения на решение задачи распознавания лингвистических образов.

2.они показывают вероятный метод ответа задачи распознавания линг.образов, в частности: перечисление грамматик в определенном порядке.

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

Существуем множество видов перебора грамматик. Одним из них есть оккамовское перечисление, при котором грамматики рассматриваются в порядке повышения сложности.

Вывод цепочечных грамматик:

К сожалению, ни одна из известных схем не в состоянии решить эту задачу в общем виде, представленном на рис. Вместо этого предлагаются бессчётные методы для вывода ограниченных грамматик.

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

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

Метод Фельдмана.

1. Постановка задачи:

Дано: множество выборочных цепочек {xi}.

Требуется: подвергнуть {xi} обработке посредством адаптивного (Адаптивный метод — метод, что пробует выдать отличных показателей путём постоянной подстройки под входные эти). обучающегося метода, на выходе которого воспроизводится грамматика G, согласованная с данными цепочками.

Иными словами, множество цепочек {xi} есть подмножеством языка L(G), порождаемого грамматикой G.

2.Сущность способа:

§ сперва выстроить нерекурсивную грамматику, порождающую в точности заданные цепочки,

§ после этого, сращивая нетерминальные элементы, взять более несложную рекурсивную грамматику, порождающую нескончаемое число цепочек.

3. Метод + пример, дабы понятнее было.

Сам метод:

Метод возможно поделить на три части.

Первая часть формирует нерекурсивную грамматику.

Вторая часть преобразует её в рекурсивную грамматику.

После этого, в третьей части, происходит упрощение данной грамматики.

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

Часть 1.

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

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

Предполагается, что остаток каждой цепочки большой длины есть суффиксом (хвостовым финишем) некоей более маленькой цепочки. В случае если какой-либо остаток не отвечает этому условию, цепочка, равная остатку, добавляется к обучающей выборке.

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

В отечественном примере первой цепочкой большой длины в обучающей выборке есть цепочка . Для порождения данной цепочки строятся следующие правила подстановки:

,

где —правило остатка.

Вторая цепочка — . Для порождения данной цепочки к грамматике добавляются следующие правила:

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

Но в первой части мы занимаемся только определением множества правил подстановки, которое способно в точности порождать обучающую выборку, и не касаемся вопроса избыточности. В непростых обстановках тяжело выполнять исполнение этого условия и в один момент уменьшать число нужных правил подстановки. Намного проще просматривать введенные правила слева направо, дабы выяснить, будут ли они порождать новую цепочку, не стремясь наряду с этим минимизировать число правил подстановки. Об устранении избыточности обращение отправится в третьей части метода.

Для порождения третьей цепочки требуется добавление к грамматике лишь одного правила: .

Для порождения четвертой цепочки требуется добавление к грамматике лишь одного правила: .

Для порождения пятой цепочки требуется добавление к грамматике лишь одного правила: .

Для порождения шестой цепочки требуется добавление к грамматике лишь одного правила: .

Для порождения седьмой цепочки требуется добавление к грамматике лишь одного правила: .

Для порождения восьмой цепочки требуется добавление к грамматике лишь одного правила: .

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

Часть 2.

В данной части, соединяя каждое правило остатка длины 2 с другим (неостаточным) правилом грамматики, приобретаем рекурсивную автоматную грамматику. Это происходит в следствии (потом эврестическое правило)слияния каждого нетерминального элемента правила остатка с нетерминальным элементом неостаточного правила, что может порождать остаток. Так, к примеру, в случае если — остаточный нетерминал вида и — неостаточный нетерминал вида , где , все видящиеся заменяются на , а правило подстановки отбрасывается.

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

В разглядываемом примере выделим остаточные правила:

Для правила совершим поиск кандидата на слияние. Это правила вида . Тут подходят следующие правила:

Так, мы сливаем нетерминал с нетерминалом и удаляем правило (и повторяющиеся правила):

Было

стало

Для правила совершим поиск кандидата на слияние. Это правила вида . Тут подходят следующие правила:

Так, мы сливаем нетерминал с нетерминалом и удаляем правило (и повторяющиеся правила):

.

Рекурсивными правилами являются и .

Замечание. В случае если в следствии соединения правил остатка с другими правилами грамматики остались несоединенные правила остатка (каковые при длине остатка, хорошей от единицы, недопустимы в автоматной грамматике), то направляться разбить эти правила остатка по следующей схеме: правило остатка удаляется, добавляются правила

Где новые нетерминалы для грамматики, разные для каждого удаляемого правила остатка.

Часть 3.

Тут грамматика, полученная во второй части, упрощается объединением эквивалентных правил подстановки.

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

Формально два правила подстановки эквивалентны, в случае если , где обозначает, что цепочка порождается из нетерминала соответствующим применением правил подстановки.

В приведенном примере эквивалентны правила с левыми частями и .

Было на втором шаге

.

По окончании слияния и приобретаем следующий комплект правил:

,

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

,

,

,

.

Легко проверить, что эта грамматика может порождать обучающую выборку, использованную в ходе ее вывода.

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

4. Метод Фельдмана и автоматные грамматики:

Разглядим следующую автоматную грамматику :

,

,

Для восстановления грамматики выберем следующие цепочки .

Метод Фельдмана при длине остатка конструирует следующую грамматику:

Как видно, язык грамматики таков . Разумеется, он не сходится с языком исходной автоматной грамматикой (к примеру в случае если подставить abacc).

Для получения исходной автоматной грамматики потребуется применять следующий комплект цепочек . Тогда методом будет сконструирована грамматика:

.

Легко убедиться, что эта грамматика есть эквивалентной исходной грамматике , другими словами порождает такой же язык. Подобного вывода возможно достигнуть, в случае если применять длины остатка .

Так, на итог восстановления грамматики воздействует длина остатка и размер выборки

5. Метод Фельдмана и контекстно-свободные грамматики:

Модификация метода Фельдмана для конструирования контекстно-свободных грамматик может трудиться следующим образом.

Первоначально метод выделяет из цепочек выборки фрагменты, каковые могли быть образованы правилами КС-грамматик. Такие фрагменты в большинстве случаев находятся во многих цепочках и содержат более чем два знака.

На базе выделенных фрагментов создаются правила КС-грамматики, каковые их порождают. Правила имеют вид где ; их множество . В цепочках выборки мы заменяем выбранные фрагменты некоторыми неиспользуемыми терминалами .

Для модифицированных цепочек по методу Фельдмана строится автоматная грамматика (метод сейчас используется на модифицированных «автоматных» цепочках, что и дает возможность приобрести действенную грамматику). В следствии мы приобретаем автоматную грамматику с комплектом «контекстных» правил.

Остается:

§ заменить введенные терминалы на соответствующие нетерминалы из правил ;

§ каждое конечное правило из связать с выстроенной грамматикой переходом на кое-какие терминалы либо нетерминалы.

Пример

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

Увидим тут конструкцию , которая возможно выстроена КС-грамматикой посредством правила из . Вместо во множестве цепочек будем применять терминал .

Модифицируем исходное множество цепочек: . Используем для него уникальный метод Фельдмана.

Приобретаем грамматику , где

Затем введем конструкции правил КС-грамматики :

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

В следствии грамматика есть контекстно-свободной.

ДЛЯ ЛЮБОЗНАТЕЛЬНЫХ

Постановка задачи:

Предположим, у нас имеются два класса образов w1 и w2 и пускай образы образы этих классов смогут быть выстроены из показателей, которыми владел некоему конечному множеству. Назовем эти признакитерминалами и обозначим множество терминалов знаком Vт .

В синтаксическом распознавании образов терминалы именуются кроме этого непроизводными знаками (элементами). Любой образ может рассматриваться как цепочка либо предложение, потому, что он составлен из терминалов множества VT. Допустим, что существует грамматика G, такая, что порождаемый ею язык складывается из предложений (образов), принадлежащих только одному из классов, скажем w1. Разумеется, что эта грамматика возможно использована в целях классификации образов, поскольку заданный образ малоизвестной природы возможно отнесен к w1 если он есть предложением языка L(G).В другом случае образ приписывается классу w2.

К примеру, бесконтекстная грамматика G = (Vn, Vт, P, S) при Vn= {S}, Vt= {a, b) и

множестве правил подстановки Р= {S-aaSb, S-aab} владеет свойством порождать только предложения, которые содержат в два раза больше знаков а, чем Ь. В случае если мы сформулируем гипотетическую задачу разбиения образов на два класса, причем объекты класса w1 — это цепочки вида aab, aaaabb и т. д., а объекты класса w2 содержат однообразное число знаков а и Ь (т. е. ab, aabb и т. д.), то разумеется, что классификация заданной цепочки производится несложным определением того, может ли разрешённая цепочка порождаться грамматикой G, рассмотренной выше. В случае если может, то объект в собственности w1, в случае если нет — он машинально приписывается классу w2. Процедура, применяемая для определения, есть либо не есть цепочка предложением, грамматически верным для данного языка, именуется грамматическим разбором.

Постановка задачи по Фельдману возможно сформулировать как:

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

Теорема о гомоморфизме колец. Поле частных


Также читать:

Понравилась статья? Поделиться с друзьями: