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


 

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

73458. МЕТОДИКО–ПРАКТИЧЕСКОЕ ИССЛЕДОВАНИЕ ОРГАНИЗАЦИИ ТВОРЧЕСКИХ ИНДУСТРИЙ В ПРОСТРАНСТВЕ СОВРЕМЕННОГО ГОРОДА 116 KB
  Наверно каждый город может похвастаться своими местными культурными мероприятиями которые проходят в рамках одного города или региона. Данный фестиваль проводится в разных городах России и в каждом городе проводится по своему.
73460. Основания для предоставления отсрочки и рассрочки по уплате налогов и сборов 102.5 KB
  Изменение срока уплаты налога и сбора осуществляется в форме отсрочки рассрочки инвестиционного налогового кредита. Ни для кого не секрет что рассчитаться по налогам с бюджетом компания должна в установленные сроки. В таких случаях законодатель предусмотрел возможность изменения срока уплаты налога.
73461. Роль монастырей в русской культуре 99.5 KB
  Сохранению национального самосознания, национальной культуры русского народа немало содействовали в тяжелые годы татаро-монгольского ига и западных влияний монастыри. Всего с ХIV до половины ХV века на Руси было основано до 180 новых монашеских обителей.
73462. Категории плательщиков налога и формирование налоговой базы при исчислении НДФЛ 98.5 KB
  Актуальность темы продиктована еще и тем, что в сфере исчисления налога на доходы физических лиц очень часто фиксируются грубые финансовые нарушения, влекущие за собой тяжелые последствия, как для отдельных предприятий и граждан, так и для всей страны в целом.
73463. Т. Парсонс, К. Гирц. Трактовка культуры в контексте теории социального действия 96 KB
  Социальная роль в понимании Т. Парсонса представляет собой набор функций, которые осуществляет каждое действующее лицо в силу занимаемой им социальной позиции при конкретных условиях. Ожидание от другого выполнения данной роли именуется «установкой».
73464. Система аграрного законодательства 84.5 KB
  Предметом аграрного права являются различные общественные отношения возникающие в процессе осуществления сельскохозяйственной деятельности а также непосредственно связанные с деятельностью субъектов аграрного права которые именуются аграрными отношениями.
73465. Сутність міжнародної торгівлі. Методи нетарифного регулювання 79.5 KB
  За допомогою міжнародної торгівлі країни можуть розвивати спеціалізацію підвищувати продуктивність своїх ресурсів і збільшувати загальний обсяг виробництва. У міжнародній торгівлі товар важливий не як продукт виробництва а як обєкт попиту і пропозиції.
73466. Формирование первоначального навыка письма в период обучения грамоте 79.5 KB
  Цель исследования: раскрыть специфику формирования навыка письма у первоклассников в период обучения грамоте. Предмет исследования: Система упражнений как метод формирования первоначального навыка письма у первоклассников.