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


 

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

40984. Конфлікти в колективі 40.5 KB
  Тому проблема здебільшого полягає не в наявності самого факту конфлікту а в тому який характер він носить – деструктивний чи конструктивний – і яким чином розв’язується. Конструктивна та деструктивна суть конфліктів Деструктивний конфлікт переводить причини що призвели до конфлікту на “особистостіâ€. Дана установка не веде до вирішення конфлікту а навпаки його загострює зростає упередженість проти партнера напруга у взаємостосунках посилюються неприємні почуття та переживання виникають стреси та ін. Прикладом деструктивного...
40985. Трудові спори і порядок розв’язання 183.5 KB
  Поняття трудових спорів та їх класифікація При здійсненні відносин людей під час трудової діяльності між працівниками і власниками підприємств або уповноваженими ними органами можуть виникати й часто виникають різного роду непорозуміння. Перебудова виробничих і трудових відносин нові форми застосування і використання праці істотно вплинули не тільки на індивідуальні трудові відносини а й на структуру і зміст організаційноуправлінських відносин що виникають між власником підприємства або уповноваженою ним особою з одного боку і трудовим...
40986. 4-х комнатный жилой дом мансардного типа 103.5 KB
  Расширился ассортимент, и повысилось качество применяемых в отечественном строительстве отделочных материалов — всех видов керамической плитки, покрытий для пола и стен, а также керамических санитарных и санитарно-технических изделий.
40987. Мова і культура 148.5 KB
  Однак з іншого боку у самій матерії мови у ряду істотних характеристик мовної структури позначилася біологічна природа людини. Психофізіологічні можливості знакової діяльності людини зумовили багаторівневу організацію мови визначили кількісні параметри окремих рівнів наприклад обсяг фонологічної системи що коливається в різних мовах в інтервалі від 10 до 100 одиниць; обсяг словника в інтервалі від 10 тисяч до півмільйона слів; вияв надмірності в мові. Культура визначає план змісту мови. У молекулярній біології і семіотиці був виявлений...
40988. Стратегии позиционирования в маркетинге, стратегия эффективного позиционирования, проблемы разработки стратегии позиционирования 233 KB
  Целью данной работы является детальное изучение понятия позиционирования в маркетинге и рассмотрение стратегий позиционирования. Для достижения поставленной цели мною решались следующие задачи: раскрытие понятия позиционирования, выявления ключевых концепций и идей позиционирования
40989. ПОЛІТИЧНА ЛІНГВІСТИКА. МОВНА ПОЛІТИКА 115.5 KB
  Потрыбно постійно пам’ятати що будьяке рішення щодо мови – це політичне рішення яке має прийматися при одночасному врахуванні об’єктивних комунікативних потреб й механізму групової ідентифікації. Крисін– ставлять перед собою і таке завдання: регулювати розвиток і функціонування мови мов не покладаючись цілком на самоплин мовного життяâ€. На нашу думку не самі соціолінгвісти регулюють розвиток і функціонування мови чи мов у суспільстві а держава – її владні інститути. Сьогодні вже можна говорити про чітко окреслену...
40990. Психологія стресу та його наслідки 80.5 KB
  Функції природа та фази стресу. Методи подолання стресу. Стан стресу може виникати під впливом найрізноманітніших життєвих умов починаючи із повсякденних турбот і закінчуючи екстремальними ситуаціями так званими ударами долі .
40991. Проектирование 2-х этажного пятикомнатного жилого дома 121 KB
  Однако на сегодняшний день ситуация на рынке малоэтажного строительства еще весьма неоднозначна. С одной стороны, есть огромный неудовлетворенный потенциальный спрос на загородное жилье у горожан, уставших от городского шума, плохой экологии и тесноты. С другой стороны, наблюдается явное несоответствие спроса и предложения на рынке.
40992. ПЛАНУВАННЯ НАВЧАЛЬНОГО ПРОЦЕСУ З ІНОЗЕМНОЇ МОВИ 153 KB
  Система планування в середній школі охоплює послідовне планування в межах усього курсу навчання чвертей циклу уроків та окремого уроку виходячи з конкретних цілей кожного відрізка навчального процесу. Вчитель повинен усвідомити призначення кожного елемента уроку його взаємодію з іншими елементами уроку. Підготовча робота вчителя до уроку здійснюється послідовно і включає: аналіз змісту матеріалу визначення типу уроку формулювання цілей уроку поетапний розподіл навчального матеріалу визначення часу на його опрацювання розробку...