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


 

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

36476. Древняя Персия 27 KB
  За помощь в осуществлении контроля над обществом им предоставлялась наибольшая политическая самостоятельность Частный интерес работает на общественный Внешняя политика Восточное побережье Эгейского моря Греция – колонии господство над торговлей в средиземном море Внешняя политика обусловлена экономической структурой: цель – экономически важные регионы.
36477. Древние Шумеры 30.5 KB
  долина рек Тигр и Ефрат Неблагоприятные условия сухой климат мало полезных ископаемых Тростник и рыба – самые доступные ресурсы Население сосредоточено в предморье и не углублялось во влажные равнины Увеличение численности населения перенаселение Технологии Сельскохозяйственные культуры ячмень эммера Одомашнен ряд животных быки овцы козы свиньи и ослы Примитивные технологии обработки меди Колесо Первые постройки из сырого глиняного кирпича Шумеры пытаются вести с х на новых землях строят системы очищения почвы....
36478. Понятия «цивилизация». Подходы к толкованию термина. Цивилизационная теория 93.5 KB
  Понятия цивилизация впервые употребил Виктор Мирабо в 1757 году в значении общего уровня культурного развития. Среди деятелей просвещения цивилизация ассоциировалась с концепцией прогресса стала идеалом интеллектуального и социального развития человечества. Отсюда ясно что цивилизация носила отрицательный оттенок.
36479. Структура цивилизация, ее основные элементы 73 KB
  технологический способ производства: орудия труда источники энергии предметы труда природные ресурсы технологии организация производства в плане технологий экономический способ производства структура воспроизводства обмен распределение экономическое управление социальнополитические отношения: социальные отношения национальные отношения политические отношения государственные отношения правовые духовный мир: наука культура образование мораль идеология или религия Все элементы цивилизационной...
36480. Динамика развития цивилизации, этапы ее развития на историческом примере 46.5 KB
  В истории человечества выделяют следующие глобальные цивилизации: неолитическую раннеклассовую античную средневековую индустриальную и наконец постиндустриальную цивилизации. Условия формирования античной цивилизации. Безусловно их наследие оказало определенное влияние на становление античной цивилизации тем не менее античный период в истории человечества дал рождение совершенно новым экономическим политическим и духовным институтам.
36481. Переходный период (смена цивилизаций): основные этапы и итоги 35 KB
  Механизм смены цивилизации Основные причины: внутренние противоречия в которых центральное место занимают потребности человека. Для производства материальных и духовных благ цивилизации приходится привлекать новые ресурсы средства труда источники энергии реализовывать новые экономические и политические схемы подавлять социальные конфликты и предлагать новый духовный продукт. Попытки удовлетворения потребностей нарушают сложившийся в цивилизации баланс и она не может удовлетворить потребности всех. Духовный мир чутко реагирует на эти...
36482. Переходный этап в развитии цивилизации на историческом примере перехода от раннеклассовой к античной 27.5 KB
  Переход между цивилизациями происходит в четыре этапа: латентный этап обвального хаоса патовая ситуация завершающий этап. На первом этапе происходит падение эффективности старого общества: возникают социальные противоречия разногласия между управленцами и исполнителями экономической функции и непрерывные войны которые с одной стороны истощали материальные ресурсы а с другой обогащали правящую элиту. Происходит возращение к родоплеменному типу отношений формирование общинного строя предполагающего управление общества вождем советом...
36483. Основные особенности и достижения неолитической цивилизации 32 KB
  Начало неолитической цивилизации связывают с неолитической революцией. Достижения неолитической цивилизации: Возникла первая форма собственности общинная собственность на землю; Появляется объекты собственности сельскохозяйственные земли пастбища охотничьи и рыболовные угодья; Возникает частная собственность при необходимости – защита частной собственности; Формирование первых политических институтов крупные межобщинные объединения; Духовный мир выходит на новый уровень возрастает уровень познания окружающего мира;...
36484. Основные особенности и достижения раннеклассовой цивилизации 32.5 KB
  Если в неолитическую эпоху основные изменения были связаны с технологиями то для раннеклассовой цивилизации характеры значительные изменения в экономическом способе производства и социальнополитические отношения. Происходит городская революция создания центров локальной цивилизации в сети крупных городов. Города не только служили центрами ремесла но и позволяли сконцентрировать материальные и духовные ресурсы цивилизации для ее развития.