29371

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

Доклад

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

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

Английский

2013-08-21

47 KB

11 чел.

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, дальнейшее изложение посвящается рассмотрению именно этих типов грамматик.


 

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

65928. ЖАНР В РУССКОМ МОНОСТИХЕ 25.5 KB
  Формальная трансформация близкого по объему жанра хайку. Влияние хайку на развитие русского моностиха по-видимому весьма велико: его отмечают говоря о своем обращении к минимальным поэтическим формам самые разные авторы. В 1990е годы делаются шаги в направлении более интенсивного сближения...
65929. Анализ существующего фонда жилой недвижимости г. Ижевска 34.36 KB
  Характеристика жилищного фонда города В жилом фонде города преобладают многоэтажные жилые дома 5 этажей и выше доля которых составила около 90. В таблице 1 приведены основные показатели характеризующие состояние жилого фонда и изменения за анализируемый период.
65930. СУДЬБА ЖАНРА ПОСЛАНИЯ В ЛИРИКЕ ХХ ВЕКА 169 KB
  Признаки послания подробно описаны но к сожалению не систематизированы и оттого не выявлена модель жанра. С этой точки зрения жанр послания эпохи классицизма может быть описан как система признаков находящихся в достаточно строгих иерархических отношениях...
65931. Факторы, определяющие цену объекта недвижимости 24.19 KB
  Рассмотрим теперь те факторы от которых зависит цена конкретного объекта недвижимости. Местоположение Для многих людей местоположение это одно из наиболее важных условий при выборе объекта недвижимости...
65932. ЭВОЛЮЦИЯ ЖАНРА «INTERACTIVE FICTION»: ОТ НЕЛИНЕЙНОГО РОМАНА К ТЕКСТОВОМУ КВЕСТУ 56 KB
  Классический роман отводит читателю весьма незавидную роль безмолвного соглядатая. Обратимся к трем интерактивного романа. Хулио Кортасар предлагает как известно два способа прочтения своего романа Игра в классики 1963. Произведение Гарри Гаррисона Стань стальной крысой...
65934. Управляющая система в сфере недвижимости 31.67 KB
  Управление недвижимостью включает: систему законодательного и нормативного регламентирования и контроля поведения всех субъектов рынка недвижимости осуществляемую государственными органами; оформление и регистрацию правоустанавливающих и других документов на объекты недвижимости...
65935. Понятие недвижимости в Российской Империи и современной России 21.58 KB
  Строение как принадлежность земли считается недвижимым имуществом; но если оно предназначено на слом или снос то получает характер движимого имущества. В составе недвижимого имущества русский закон отличает имущества раздельные и нераздельные.
65936. Технический паспорт объекта недвижимости. Бюро технической инвентаризации 67 KB
  Землеустройство оформление землеустроительной документации Услуга Результат проведения работ Кадастровые работы в отношении земельных участков: Включают полный цикл работ от полевых измерений до подачи в орган кадастрового учета необходимых документов...