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


 

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

36451. АНАЛИТИЧЕСКАЯ ХИМИЯ 252.91 KB
  Реальные потенциалы необходимы при определении хода потенциометрического титрования. Реальные потенциалы необходимы для решения вопроса о направлении окислительновосстановительного процесса и хода потенциометрического титрования. Опредся точка конечная и точка титрования.Алкелидиметрия HCl NOH Окислительновосстановительная аОх1вRed2=Ox2bRed1 Редоксиметрия Перманганометрия Дихроматометрия Иодометрия Вонадатометрия Цериметрия KMnO4 K2Cr2O7 I2 KI NH4xVO3 CuSO42 nMnL=[ML] Комплексонометрия Меркуриметрия комплексонометрия...
36452. КОЛЛОИДНАЯ ХИМИЯ 475.42 KB
  Удельная геометрическая поверхность Sуд = S V м2 м3 м2 кгВ общем случае: Sуд = kD Размеры частиц дисперсной фазы: Грунты: песчаные больше 50 мкм пылеватые 150 мкм Эритроциты крови человека 7 мкм Кишечная палочка 3 мкм Вирус гриппа 01 мкм – 10 нм Дым древесный уголь 30 – 40 мкм Тонкие поры угля 110 нм...
36453. НЕОРГАНИЧЕСКАЯ ХИМИЯ 79.4 KB
  Активность возрастает отLi к Сs в данном ряду. растёт радиус атома а притяжение последнего электрона к ядру ослабевает поэтому самый активный в данном ряду Цезий. По отношению к воде: 2R2H2O=2ROHH2 где Rлюбой металл из семейства щелочных только литий растворяется спокойно натрий может загореться на поверхности воды а калий взрывоопасен с водой очень бурно реагирует Объясните кажущуюся аномалию положения Li в ряду электродных потенциалов Eo процесса Э 1е → Э в растворе представленных в таблице по сравнению с положением в...
36454. Сущность, значение и место управления персоналом в организации 171 KB
  Персонал – это постоянные и временные сотрудники предприя представители квалифицированного и неквалифицго труда.цированного и неквалифицго труда в. зависит от: числа элементов разнообразия элов сложности элов числа и харра связей м у ними; в автоматизыция произвва – не только произвва но и управления возрастание интеллектой составляющей персонала и требования к нему; г повсеместное распространение коллективных форм оргции труда – труд людей усложняется → они должны свободно работать → стремление к самостоятельности; д рост...
36455. ТАКТИКО-СПЕЦІАЛЬНА ПІДГОТОВКА 14.51 MB
  Основні завдання зв’язку. Засоби та види зв’язку. Основні вимоги до зв’язку. Основними задачами зв'язку є: забезпечення стійкого зв'язку з вищим штабом та своєчасного приймання сигналів бойового управління; забезпечення управління підлеглими військами в будь яких умовах обстановки; забезпечення передач i сигналів та своєчасне попередження та повідомлення військ про безпосередню загрозу застосування противником ЗМЗ та повітряного противника; забезпечення обміну інформацією між взаємодіючими з’єднаннями частинами підрозділами;...
36456. Основные характеристики и достижения Древнего Рима 38 KB
  переход от патриархального к классическому рабству на территории Италии произошел в греческих городахколониях Южной Италии и Сицилии. Сельское хозяйство Италии переживало подъем. Одним из важных показателей прогресса в сельском хозяйстве Италии является выделение новых отраслей: животноводства и приусадебного птицеводства. Скот и птицу разводили в Италии с незапамятных времен но лишь во III вв.
36457. Основные пути перехода античных обществ к феодализму 34 KB
  Византийский путь. Итальянский путь. ЗФранцузский путь Фр. Самый быстрый путь из которого возникли госва Европы Скандинавскорусский путь.
36458. Переход античных обществ к феодализму (один из вариантов на историческом примере) 26.5 KB
  Римская империя = Византия Как и любой переход между цивилизациями данный переход проходил в четыре этапа. Однако неравномерность развития регионов мира приводила к большим различиям в развитии процесса переходного периода. Однако латентный этап перехода начался раннее сформировав ряд важных тенденций ставших впоследствии элементами феодальной цивилизации. Переход по византийскому пути был наименее болезненным но проходило очень медленно.
36459. Основные особенности и достижения Византии 27.5 KB
  Большая роль городов. Высокая роль государства в экономич. Основные достижения: 1 большая роль городов 2развитие торговли 3Высокая роль государства в экономике 4развитие архитектуры 5 использование религии в политических целях 6культурная экспансия 7развита централизация 8социальная мобильность 9Византии удавалось сдерживать натиск с Востока 10 Система подготовки кадров 11иерархическая система правления.