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


 

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

22468. Разновидности методов кодирования. Штриховое кодирование товаров. Правила и примеры штрихового кодирования 37.69 KB
  Целью кодирования является систематизация объектов путем их идентификации максимально коротким способом, то есть с помощью минимального числа знаков.
22469. Сущность, цели и функции стандартизации. Значение стандартизации в международной торговле. Национальный орган по стандартизации в РФ 20.65 KB
  Стандартизация — деятельность по установлению правил и характеристик в целях их добровольного многократного использования, направленная на достижение упорядоченности в сферах производства и обращения продукции и повышение конкурентоспособности продукции, работ и услуг.
22470. Категории стандартов. Общая характеристика стандартов разных категорий. Их объекты, разработка, обозначение и утверждение. Изменения в ГСС в свете закона «О техническом регулировании 19.24 KB
  Система стандартизации Российской Федерации — это совокупность организационно-технических, правовых и экономических мер, осуществляемых под управлением федерального органа исполнительной власти по стандартизации и направленных на разработку и применение нормативных документов в области стандартизации с целью защиты потребителей и государства
22471. Глобальная экология 327.41 KB
  Беспрецедентный рост возможностей человека вооруженного достижениями НТР подняло на качественно новую ступень возможности его по преобразованию окружающей природной среды и расширило сферы его воздействия на нее, выходящие за рамки БИОСФЕРЫ.
22473. ИНТЕРФЕЙСЫ, ТЕРМИНАЛЬНОЕ ОБОРУДОВАНИЕ, СТРУКТУРА TDMA КАДРОВ И ФОРМИРОВАНИЕ СИГНАЛОВ В СТАНДАРТЕ GSM 381.44 KB
  Цель работы Изучить интерфейсы структуру служб терминальное оборудование структуру TDMA кадров и формирование сигналов в стандарте GSM. Ознакомиться с внутренними интерфейсами используемыми для соединения между различным оборудованием сетей GSM. Ознакомиться со структурой служб и передачей данных в стандарте GSM.
22474. ОБОРУДОВАНИЕ ПОДВИЖНЫХ И БАЗОВЫХ СТАНЦИЙ, ЦЕНТРА КОММУТАЦИИ 124.5 KB
  Цель работы Изучить блоксхемы подвижной станции абонентского радиотелефонного аппарата базовой станции и центра коммутации. Задание Изучить блоксхему подвижной станции ПС. Изучить блоксхему базовой станции БС. Краткая теория вопроса Рассмотрение элементов системы сотовой связи начнем с подвижной станции наиболее простого по функциональному назначению устройства и к тому же единственного элемента системы который не только реально доступен пользователю но и находится у него в руках в буквальном смысле этого слово.
22475. ПРИНЦИПЫ ПОСТРОЕНИЯ И ТИПЫ ТРАНКИНГОВЫХ СИСТЕМ 1.62 MB
  Изучить основные типы транкинговых систем: Система ВОЛЕМОТ; Система АЛТАЙ; Системы стандарта SMARTRUNK; Системы стандарта МРТ 1327; Система IDEN; Система стандарта TETRA. Однако продолжают успешно развиваться сравнительно простые системы радиосвязи имеющие специальное ограниченное применение. Профессиональные системы подвижной радиосвязи создавались и развертывались в России в интересах обеспечения служебной деятельности различных государственных структур министерства обороны правоохранительных органов промышленных групп и...
22476. КЛАССИФИКАЦИЯ СИСТЕМ ПЕРСОНАЛЬНОГО РАДИОВЫЗОВА, ПЕЙДЖЕРЫ, РЕПИТЕРЫ, ОСНОВНЫЕ ПРОТОКОЛЫ ПЕРЕДАЧИ ИНФОРМАЦИИ. 1.21 MB
  КЛАССИФИКАЦИЯ СИСТЕМ ПЕРСОНАЛЬНОГО РАДИОВЫЗОВА ПЕЙДЖЕРЫ РЕПИТЕРЫ ОСНОВНЫЕ ПРОТОКОЛЫ ПЕРЕДАЧИ ИНФОРМАЦИИ. Цель работы Изучить классификацию систем персонального радиовызова пейджеры репитеры основные протоколы передачи информации. Ознакомиться с основными протоколами передачи информации в СПРВ. При этом для передачи вызова абоненту использовалось последовательное тональное кодирование адреса обеспечивающее возможность обслуживания до нескольких десятков тысяч пользователей.