Лекция 5 Классификация грамматик по Хомскому Линейные грамматики Определение 1




НазваниеЛекция 5 Классификация грамматик по Хомскому Линейные грамматики Определение 1
Дата конвертации13.02.2013
Размер445 b.
ТипЛекция


Лекция 5

  • Классификация грамматик по Хомскому


Линейные грамматики



Определение 5.1

  • Грамматика G = (N, , P, S) называется линейной, если все ее правила имеют вид  либо , где   N,  N,   *,   *.



Определение 5.3

  • Грамматика G = (N, , P, S) называется лево линейной, если все ее правила имеют вид  либо , где N,   N,   *.

  • Пример 5.1.

  • G=({<цифра>}, {0, 1, …, 9}, {<цифра>0, <цифра>1, …, <цифра>9},<цифра>)

  • Здесь <цифра> рассматривается как единственный нетерминальный символ.

  • L(G) – это множество, состоящее из 10 цифр. L(G) – конечное множество. Здесь грамматика является как праволинейной, так и леволинейной.

  • Частным случаем праволинейной грамматики является правоавтоматная грамматика.



Определение 5.4

  • Грамматика G = (N, , P, S) называется правоавтоматной, если все ее правила имеют вид  либо , где   N,   N,  , и допускается правило S  .

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

  • Частным случаем леволинейной грамматики является левоавтоматная грамматика.



Определение 5.5

  • Грамматика G = (N, , P, S) называется левоавтоматной, если все ее правила имеют вид  либо , где  N,  N, , и допускается правило S  .



Контекстно-свободные грамматики



Определение 5.6

  • Грамматика G = (N, , P, S) называется контекстно-свободной (или бесконтекстной) (КС-грамматикой), если все ее правила имеют вид , где  N, а   (N)*.



Пример 5.2.

  • Пример 5.2.

  • Пусть G0 = ({E, T, F}, {a, +, *, (, )}, P, E), где P состоит из правил

  • E  E+T | T

  • T  T*F | F

  • F  (E) | a



Пример вывода в этой грамматике:

  • Пример вывода в этой грамматике:

  • E  E+T

  •  T+T

  •  F+T

  •  a+T

  •  a+T*F

  •  a+F*F

  •  a+a*F

  •  a+a*a

  • Язык L(G0) представляет собой множество арифметических выражений, построенных из символов a, +, *, (, ).



Задание 7

  • Построить пример контекстно-свободной грамматики. Описать порождаемый ею язык.



Контекстно-зависимые грамматики

  • грамматики непосредственных составляющих



Определение 5.8

  • Грамматика G = (N, , P, S) называется грамматикой непосредственных составляющих, если все ее правила имеют вид , где   N,   (N)*,   (N)* а   (N)*. Здесь цепочки  и  называются левым и правым контекстом (соответственно).



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

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



Пример 5.3.

  • Пример 5.3.

  • Пусть G определяется правилами:

  • (1) S  aSBC

  • (2) S  aBC

  • (3) bCBC  bBCBC

  • (4) aB  ab

  • (5) bB  bb

  • (6) bC  bc

  • (7) cC  cc

  • (8) cBC cсC



В грамматике G возможен вывод

  • В грамматике G возможен вывод

  • S  aSBC применяется правило (1)

  •  aaBCBC применяется правило (2)

  •  aabCBC применяется правило (4)

  •  aabBCBC применяется правило (3)

  •  aabbCBC применяется правило (5)

  •  aabbcBC применяется правило (6)

  •  aabbccC применяется правило (8)

  •  aabbccc применяется правило (7)



Задание 8

  • Построить пример контекстно-зависимой грамматики, описать порождаемый ею язык.



Грамматики без ограничений

  • грамматики общего вида



Грамматики общего вида (или просто грамматики) – это грамматики, правила в которых имеют вид AX, где A  (N)*N(N)*, X  (N)*.

  • Грамматики общего вида (или просто грамматики) – это грамматики, правила в которых имеют вид AX, где A  (N)*N(N)*, X  (N)*.



Пример 5.4.

  • Пример 5.4.

  • Пусть G — грамматика с правилами

  • (1) S  CD

  • (2) C  aCA

  • (3) C  bCB

  • (4) AD  aD

  • (5) BD  bD

  • (6) Aa  aA

  • (7) Ab  bA

  • (8) Ba  aB

  • (9) Bb  bB

  • (10) C 

  • (11) D 



Пример вывода в грамматике G:

  • Пример вывода в грамматике G:

  • S  CD применяется правило (1)

  •  aCAD применяется правило (2)

  •  abCBAD применяется правило (3)

  •  abBAD применяется правило (10)

  •  abBaD применяется правило (4)

  •  abaBD применяется правило (8)

  •  ababD применяется правило (5)

  •  abab применяется правило (11)

  • L(G) = {|{a,b}}, т.е. L(G) состоит из цепочек четной длины, составленных из букв a и b, причем первая половина каждой цепочки совпадает со второй половиной.



Пример 5.5.

  • Пример 5.5.

  • Пусть G определяется правилами:

  • (1) S  aSBC

  • (2) S  aBC

  • (3) CB  BC

  • (4) aB  ab

  • (5) bB  bb

  • (6) bC  bc

  • (7) cC  cc



В грамматике G возможен вывод

  • В грамматике G возможен вывод

  • S  aSBC применяется правило (1)

  •  aaBCBC применяется правило (2)

  •  aabCBC применяется правило (4)

  •  aabBCC применяется правило (3)

  •  aabbCC применяется правило (5)

  •  aabbcC применяется правило (6)

  •  aabbcc применяется правило (7)

  • Данная грамматика порождает язык anbncn (n 1).



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

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



По аналогии будем называть некоторый язык

  • По аналогии будем называть некоторый язык

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

  • левоавтоматным (правоавтоматным) языком, если существует хотя бы одна порождающая его левоавтоматная (правоавтоматная) грамматика,

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



Похожие:

Лекция 5 Классификация грамматик по Хомскому Линейные грамматики Определение 1 iconКлассификация соревновательных упражнений (видов спорта) содержание определение вида спорта
Классификация по Л. П. Матвееву (1977) Классификация по способу определения соревновательного результата (В. С. Келлер, 1986)
Лекция 5 Классификация грамматик по Хомскому Линейные грамматики Определение 1 iconЛекция 10 Левокурсивные и правокурсивные грамматики Определение 10. 1
Аналогично, если  = , то а называется праворекурсивным. Грамматика, имеющая хотя бы один леворекурсивный нетерминальный символ,...
Лекция 5 Классификация грамматик по Хомскому Линейные грамматики Определение 1 iconУрока: «Виды ядерного,химического и биологического оружия. Определение и классификация, способы защиты». Цель: Сформировать у учащихся знания о видах оружия
«Виды ядерного,химического и биологического оружия. Определение и классификация, способы защиты»
Лекция 5 Классификация грамматик по Хомскому Линейные грамматики Определение 1 iconЛекция 5 13 февраля 2012 года
Нелинейные относительно включенных в анализ объясняющих переменных, но линейные по оцениваемым параметрам
Лекция 5 Классификация грамматик по Хомскому Линейные грамматики Определение 1 iconСборник задач по аналитической геометрии Апатенок Р. Ф., Маркина А. М., Хейнман В. Б. Сборник задач по линейной алгебра и аналитической геометрии
I. Элементы линейной алгебры Линейная алгебра часть алгебры, изучающая линейные пространства и подпространства, линейные операторы,...
Лекция 5 Классификация грамматик по Хомскому Линейные грамматики Определение 1 iconПроект по теме «Линейные уравнения» Руководитель проекта Кудоспаева Надежда Николаевна
Донести до ребят что такое линейные уравнения и где они использовались в древности
Лекция 5 Классификация грамматик по Хомскому Линейные грамматики Определение 1 iconОксиды. Определение, состав, номенклатура, классификация и структурные формулы Оксиды. Определение, состав, номенклатура, классификация и структурные формулы

Лекция 5 Классификация грамматик по Хомскому Линейные грамматики Определение 1 iconЛекция 9 Отношения, графы Определения Определение. Пусть а и b объекты. Определение. Пусть а и b объекты. Через ( а, b )
Определение. Отношение {(b, а) | (а, b)  R} называется обратным к отношению r и часто обозначается через r-1
Лекция 5 Классификация грамматик по Хомскому Линейные грамматики Определение 1 iconЛекция Большой наркоманический синдром классификация психоактивных веществ (пав)

Лекция 5 Классификация грамматик по Хомскому Линейные грамматики Определение 1 iconЛекция : Классификация и основные характеристики моделей конечных стратегических игр
Тема Модели конечных стратегических игр Лекция : Классификация и основные характеристики моделей конечных стратегических игр
Разместите кнопку на своём сайте:
dok.opredelim.com


База данных защищена авторским правом ©dok.opredelim.com 2015
обратиться к администрации
dok.opredelim.com
Главная страница