29371

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

Доклад

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

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

Английский

2013-08-21

47 KB

9 чел.

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


 

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

53481. Діяльність Гая Юлія Цезаря та її значення для історії Рима 238.5 KB
  Римський диктатор Юлій Цезар (12 липня 100 р. — 15 березня 44 р.) став одним з найбільш відомих діячів усесвітньої історії, чиє імя зазвичай повязують з поняттями про велику людину, полководця і політика. Військово-політична і літературна діяльність Цезаря, його неабиякі здібності, нарешті, його яскрава персона притягали і притягають істориків. Історична роль Юлія Цезаря велика і багатогранна
53482. Природні умови Італії та виникнення міста Рима 50.5 KB
  Природні умови Італії та виникнення міста Рима. Виникнення міста Рима та правління царів. Найважливішими містами були Тарент Кротон Фурії. У результаті грецькі міста виявилися беззахисними перед місцевими племенами.
53483. ИТОГИ И УРОКИ ВЕЛИКОЙ ОТЕЧЕСТВЕННОЙ ВОЙНЫ 32 KB
  Залогом победы было единство фронта и тыла сделавшее реальным лозунг военных лет: Все для фронта все для победы Трагическое начало войны поставило перед руководством страны чрезвычайно сложную задачу: переместить в глубокий тыл промышленные предприятия оборудование материальные ценности. На военное положение были переведены все рабочие и служащие: они объявлялись мобилизованными на период войны рабочий день устанавливался в 11 часов при шестидневной рабочей неделе сверхурочные становились обязательными отпуска...
53484. Зарубіжний досвід соціального страхування 84 KB
  Державне соціальне страхування є невідємною складовою соціальної системи будь-який економічно розвиненої країни. Будь-яке держава зацікавлена в тому, щоб у суспільстві не відбувалися соціальні потрясіння, а розвиток країни йшло стабільно і планомірно.
53485. Московське царство за Івана ІV 58 KB
  Московське царство за Івана ІV Мета: ознайомити учнів зі змінами в житті Московського царства в період завершення централізації країни; розглянути основні напрямки внутрішньої і зовнішньої політики Івана ІV; удосконалювати вміння учнів встановлювати причиннонаслідкові зв`язки працювати з історичною картою характеризувати роль історичних діячів. Правління Івана ІV Васильовича 15331584: а прихід Івана ІV до влади; б держава і церква; в реформи Вибраної ради; г зовнішня політика; д опричнина; 1. Перш ніж перейти до розгляду питання...
53486. Процедура правого поворота для AVL дерева и ее особенности 41.46 KB
  В 1962 году советские математики Адельсон-Вельский Г.М. и Ландис Е.А. предложили метод балансировки, требующий после включения или исключения узла лишь локальные изменения вдоль пути от корня к данному узлу, то есть времени не более O(log2n)
53488. Процедура вставки вершин в AVL дерева и ее особенности 19.29 KB
  Показатель сбалансированности в дальнейшем будем интерпретировать как разность между высотой левого и правого поддерева, а алгоритм будет основаться на типе TAVLTree, описанном выше. Непосредственно при вставке (листу) присваивается нулевой баланс
53489. УРОКИ МАТЕМАТИКИ В НАЧАЛЬНОЙ ШКОЛЕ 415 KB
  Издание содержит основные требования к урокам математики в начальной школе нормы оценок устных и письменных работ учащихся схемы анализа уроков и контрольных работ. Предложены типы уроков математики раскрыты особенности их построения приведены типичные причины затруднений практикантов на уроках. Содержание Введение 4 Этапы планирования и подготовки урока студентом 5 Действия практиканта при планировании и конкретизации задач урока. 9 Примерное содержание комбинированного урока 11 Образцы оформления конспектов...