Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


Классификация грамматик по Хомскому осуществляется по структуре их правил вывода. Выделяется четыре типа грамматик.




Определение Цепочка b Î (VTÈVN)* выводима из цепочки в грамматике (обозначается aÞ*b), если существует последовательность цепочек (n³0) такая, что .

ПримерВ грамматике G1 SÞ*000111, т.к. существует вывод .

ОпределениеЯзыком, порожденным грамматикой ,называется множество всех цепочек в алфавите VT, которые выводимы из начального символа грамматики S c помощью правил множества Р, т.е. множество .

ПримерДля грамматики G1 язык L(G1)={0n1n | n³0}.

Определение Цепочка , для которой существует вывод SÞ*a, называется сентенциальной формой или сентенцией в грамматике .

ОпределениеЯзыком, порожденным грамматикой G называется множество терминальных сентенциальных форм грамматики.

 

2.Классификация грамматик и языков по Хомскому

Классификация грамматик по Хомскому осуществляется по структуре их правил вывода. Выделяется четыре типа грамматик.


Поделиться:

Дата добавления: 2015-08-05; просмотров: 110; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.006 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты