29371

Классы формальных грамматик

Доклад

Информатика, кибернетика и программирование

В теории формальных языков выделяются 4 типа грамматик которым соответствуют 4 типа языков. Эти грамматики выделяются путем наложения усиливающихся ограничений на правила грамматики Грамматики типа 0 Грамматики типа 0 которые называют грамматиками общего вида не имеют никаких ограничений на правила порождения. Грамматики типа 1 Грамматики типа 1 которые называют также контекстнозависимыми грамматиками не допускают использования любых правил. Грамматики типа 1 значительно удобнее на практике чем грамматики типа 0 поскольку в левой части...

Английский

2013-08-21

47 KB

10 чел.

4) Классы формальных грамматик.

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

Грамматики типа 0

Грамматики типа 0, которые называют грамматиками общего вида, не имеют никаких ограничений на правила порождения. Эти грамматики порождают естественные языки.

Любое правило

a B

может быть построено с использованием произвольных цепочек a , B  (NT)*.

Грамматики типа 1

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

χ1<A>χ2  χ1 ω χ2,

где χ1, χ2 - цепочки, возможно пустые, из множества (N T)*, символ <А>  VА и цепочка ω  (N T)*. Цепочки χ1 и χ2 остаются неизменными при применении правила, поэтому их называют контекстом (соответственно левым и правым), а грамматику - контекстно-зависимой.

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

Грамматики типа 2

Грамматики типа 2 называют контектно-свободными и бесконтекстными грамматиками (КС-грамматики или Б-грамматики).

Правила вывода таких грамматик имеют вид:

<A>  α,

где <A>  VА и α  (N  T)*.

Очевидно, что эти правила получаются из правил грамматики типа 1 при условии χ1 = χ2 = $. Поскольку контекстные условия отсутствуют, то правила КС-грамматик получаются проще, чем правила грамматик типа 1. Именно такие грамматики используются для описания языков программирования.

Эта грамматика порождает язык, который состоит из цепочек, каждая из которых в свою очередь состоит из двух частей, цепочки β  N* и зеркального отображения этой цепочки β'.

L( Г5 ) = { bb' | b  N+},

гдеN + - это множество N* без пустой цепочки. С помощью правил этой грамматики может быть построена, например, следующая цепочка:

<I>  a<I>a  ab<I>ba  aba<I>aba  ababbaba

Грамматики типа 3

Грамматики типа 3 называют автоматными грамматиками (А - грамматиками). Правила вывода в таких грамматиках имеют вид:

<A>  a или <A>  a<B> или <A>  <B>a,

где a  Vт, <A>, <B>  VА, причем грамматика может иметь только правила вида <A>  a<B> - правосторонние правила, либо только вида <A>  <B>a - левосторонние правила. Примерами автоматных грамматик могут служить правосторонняя грамматика Г1. 6 и левосторонняя грамматика Г1. 7.

Доказано, что существуют языки типа 0, не являющиеся языками типа 1, языки типа 2, не являющиеся языками типа 1, и языки типа 3, не являющиея языками типа 2.

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


 

А также другие работы, которые могут Вас заинтересовать

5580. Подшипники качения 113.5 KB
  Отличие подшипников качения от подшипников скольжения. В любом механизме или машине различают два типа подвижных опор: опоры с трением скольжения и опоры с трением качения. В первом случае происходит взаимное перемещение и взаимодействие рабочих пов...
5581. Изучение свойств памяти 55 KB
  Изучение свойств памяти Цель работы:исследование динамики процессов запоминания выявление преобладающего вида образной памяти (зрительная, слуховая). Материалы:Методики для исследования памяти: Динамический тест памяти Таблицы с образам...
5582. Обоснование и расчет искусственного освещения помещения здания закусочной 98 KB
  Обоснование и расчет искусственного освещения помещения здания закусочной Задание 1. Требования руководящих документов по вопросам производственной санитарии и гигиены труда 2. Анализ опасных и вредных факторов при строительстве и эксплуатации здани...
5583. Уголовная статистика и изучение преступности 93.5 KB
  Правовая статистика охватывает широкий круг проблем, связанных с негативными явлениями в обществе. Изучает различного рода преступления и правонарушения, такие как: бандитизм, ограбление, изнасилование, проституция...
5584. Материалы и изделия, получаемые спеканием и плавлением. Керамика 207 KB
  Материалы и изделия, получаемые спеканием и плавлением 1. Керамические материалы. Общие сведения Керамика - собирательное название широкой группы искусственных каменных материалов, получаемых формованием из глиняных смесей с минеральными и ...
5585. Магнитное поле в вакууме 30 KB
  Магнитное поле в вакууме: Взаимодействие токов осуществляется через поле, называемое магнитным. Из опытов следует, что оно имеет направленный характер и должно характеризоваться векторной величиной, называемой магнитной индукцией (В), аналогич...
5586. Строительное материаловедение. Курс лекций 906.5 KB
  Строительное материаловедение Лекция. Строение атома Уважаемые слушатели мы приступаем к изучению курса Строительное материаловедение. Лекции, которые будут прочитаны в течение данного семестра, помогут Вам разобраться в физико-химической сущност...
5587. Проблема выбора хозяйственных решений в условиях ограниченности ресурсов 193.5 KB
  Центральная проблема экономики - проблема выбора хозяйственных решений в условиях ограниченности ресурсов. Простейшая модель функционирования экономики - Граница производственных возможностей - позволяет проиллюстрировать решение основных з...
5588. Закон сохранения импульса 36.5 KB
  Закон сохранения импульса Для простоты рассмотрим движение системы, состоящей из трех точек, на каждую из которых действуют внутренние силы fik и внешние - Fi , где индекс i представляет номер точки. Уравнения движения для каждой точки имеют в...