АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Расширенная классификация грамматик Хомского

Читайте также:
  1. I. Назначение, классификация, устройство и принцип действия машины.
  2. I. Определение, классификация и свойства эмульсий
  3. II. Классификация С/А в зависимости от способности всасываться в кровь и длительности действия.
  4. LL(k) ЯЗЫКИ И ГРАММАТИКИ
  5. VI. ЕДИНАЯ ВСЕРОСИИЙСКАЯ СПОРТИВНАЯ КЛАССИФИКАЦИЯ ТУРИСТСКИХ МАРШРУТОВ (ЕВСКТМ) (КАТЕГОРИРОВАНИЕ МАРШУТА И ЕГО ОПРЕДЕЛЯЮЩИХ ПРЕПЯТСТВИЙ (ФАКТОРОВ)
  6. Акты официального толкования норм права: понятие, признаки, классификация.
  7. Акты применения норм права: понятие, классификация, эффектив-ность действия. Соотношение нормативно-правовых и правоприменительных актов.
  8. Алюминий. Классификация сплавов на основе алюминия, маркировка
  9. Аномалии развития органов и систем. Классификация аномалий развития.
  10. Антивирусные программы, классификация и назначение
  11. Артерии. Морфо-функциональная характеристика. Классификация, развитие, строение, функция артерий. Взаимосвязь структуры артерий и гемодинамических условий. Возрастные изменения.
  12. Аспект «Грамматика»

В зависимости от вида правил грамматики различают:

тип 0 –грамматики фразовой структуры или грамматики «без ограничений»:

α ® β, где α Î V +, β Î V *– в таких грамматиках допустимо наличие любых правил вывода, что свойственно грамматикам естественных языков;

тип 1 – контекстно-зависимые (неукорачивающие) грамматики:

α® β, где α Î V +, β Î V *, | α | £ | β | – в этих грамматиках для правил вида α X β ® α x β возможность подстановки строки х вместо символа X определяется присутствием подстрок α и β, т. е. контекста, что также свойственно грамматикам естественных языков;

(расширение допускает не более одного правила вида A ® e, где A Î VN);

тип 2 – контекстно-свободные грамматики:

A ® β, где A Î VN, βÎ V * – поскольку в левой части правила стоит нетерминал, подстановки не зависят от контекста;

тип 3 – регулярная грамматика:

A ® α, A ® α B,где A, В Î VN, α Î VT;

(расширение допускает не более одного правила вида S ® e, но в этом случае аксиома не должна появляться в правых частях правил).

Классификация построена по правилам иерархии, т. е. грамматики типа 3 являются частным случаем грамматик типа 2 и т. п. (см. рисунок 3).

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

Один и тот же язык может быть описан грамматиками различных типов, поэтому тип языка определяется максимально возможным для него типом грамматики. Так грамматика языка описания целых десятичных чисел, приведенная в примере выше, относится к типу 2, хотя этот язык можно описать грамматикой типа 3:

<целое>::= + <цбз>| - <цбз>|0<цбз>| 1<цбз>| 2<цбз>| 3<цбз>|4<цбз>|

5<цбз>| 6<цбз>| 7<цбз>|8<цбз>| 9<цбз>|0|1|2|3|4|5|6|7|8|9

<цбз>::= 0<цбз>| 1<цбз>| 2<цбз>| 3<цбз>|4<цбз>|

5<цбз>| 6<цбз>| 7<цбз>|8<цбз>| 9<цбз>|0|1|2|3|4|5|6|7|8|9.

Следовательно, язык описания целых десятичных чисел относится к типу 3.

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

Пример. Язык описания целых чисел. Из строки «+23» можно построить строки: 22222, 23232323 и т. д. того же языка.

Еще одно свойство языка позволяет сразу определить, что язык не относится к классу регулярных – это самовложение, т. е. наличие правил вида A Þ+ α1 A α2, где α1, α2 Î V +.

Пример. Язык скобок, описываемый правилами: S ® (S), S ® SS, S ® e. Грамматика этого языка является грамматикой с самовложением, принадлежит классу КС и не приводима к регулярной.

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

Пример. Язык скобок. Из строки «()» можно построить строку: ((())) и т. д. того же языка.

Проверка соответствия строк языку осуществляется специальной программой – распознавателем. Распознаватели могут использоваться для определения языка также как и грамматики. Чем шире класс распознаваемых грамматик, тем сложнее класс соответствующих распознавателей. Доказано, что:

грамматики типа 3 распознаются конечными автоматами;

грамматики типа 2 распознаются автоматами с магазинной памятью;

грамматики типа 1 распознаются линейными ограниченными автоматами;

грамматики типа 0 распознаются машинами Тьюринга.


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.004 сек.)