29370

Определение формальной грамматики

Доклад

Информатика, кибернетика и программирование

Конечное множество символов неделимых в данном рассмотрении в теории формальных грамматик называется словарем или алфавитом а символы входящие в множество буквами алфавита. Последовательность букв алфавита называется словом или цепочкой в этом алфавите. Если задан алфавит A то обозначим A множество всевозможных цепочек которые могут быть построены из букв алфавита A. Формальной порождающей грамматикой Г называется следующая совокупность четырех объектов: Г = { Vт VA I VA R } где Vт терминальный алфавит словарь; буквы этого...

Английский

2013-08-21

49 KB

2 чел.

3) Определение формальной грамматики.

Определение. Конечное множество символов, неделимых в данном рассмотрении, в теории формальных грамматик называется словарем, или алфавитом, а символы, входящие в множество, - буквами алфавита.

Например, алфавит A = {a, b, c, +, !} содержит 5 букв, а алфавит B = {00, 01, 10, 11} содержит 4 буквы, каждая из которых состоит из двух символов.

Определение. Последовательность букв алфавита называется словом или цепочкой в этом алфавите. Число букв, входящих в слово, называется его длиной.

Например, слово в алфавите A a = ab++c имеет длину l(a) = 5, а слово в алфавите B b = 00110010 имеет длину l (b) = 4.

Если задан алфавит A, то обозначим A* множество всевозможных цепочек, которые могут быть построены из букв алфавита A. При этом предполагается, что пустая цепочка, которую обозначим знаком $, также входит в множество A*.

Определение. Формальной порождающей грамматикой Г называется следующая совокупность четырех объектов: Г = { Vт, VA, <I>  VA, R }, где

Vт - терминальный алфавит (словарь); буквы этого алфавита называются терминальными символами; из них строятся цепочки, порождаемые грамматикой;

VA - нетерминальный, вспомогательный алфавит (словарь); буквы этого алфавита (нетерминальные символы) используются при построении цепочек; они могут входить в промежуточные цепочки, но не должны входить в результат порождения;

<I> - начальный символ грамматики <I>  VA;

R - множество правил вывода, или порождающих правил вида α  β , где α и β - цепочки , построенные из букв алфавита Vт  VA, который называют полным алфавитом (словарем) грамматики Г.

В множество правил грамматики могут также входить правила с пустой правой частью вида <Е>  . Чтобы избежать неопределенности из-за отсутствия символа в правой части правила, условимся использовать символ пустой цепочки, записывая такое правило в виде <Е>  $.

Чтобы установить правила построения цепочек, порождаемых грамматикой , введем следующие понятия.

Определение. Пусть r = τ → ϒ - правило грамматики Г и α = χ' τ χ" - цепочка символов, причем χ', χ"  (Vт  VA) *. Тогда цепочкα β = χ'  χ " может быть получена из цепочки α путем применения правила r (т.е. заменой в цепочке α τ на ). В этом случае говорят, что цепочка β непосредственно выведена из цепочки α и обозначают α  β.

Определение. Множество конечных цепочек терминального алфавита Vт грамматики Г, выводимых из начального символа <I>, называется языком, порождаемым грамматикой Г и обозначается L(Г).

L( Г ) = {   Vт* | <I> * }

Определение. Если язык, порождаемый грамматикой Г, не содержит ни одной конечной цепочки (конечного слова), то он называется пустым.

Утверждение. Для того, чтобы язык L(Г) не был пустым, в множестве R должно быть хотя бы одно правило вида r = χ  ψ, где ψ  Vт* и должен существовать вывод

<I> * χ


 

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

63936. Совершенствование методов управления в ООО «Про-Сервис» 369 KB
  Цель данного исследования – на основе проведенного анализа стиля руководства и методов управления в ООО «Про-Сервис» разработать предложения по их совершенствованию. Для достижения цели данного исследования необходимо решить следующие задачи: Рассмотреть сущность стилей руководства и методов управления в организации...
63937. Оценка банковской деятельности ЗАО «Русский Стандарт» 267.5 KB
  Российские банки вынуждены работать в условиях повышенных рисков и чаще, чем их зарубежные партнеры оказываются в кризисных ситуациях. Прежде всего, это связано с недостаточной оценкой собственного финансового положения, привлеченных и размещенных средств, надежности и устойчивости обслуживаемых клиентов.
63940. Создание электронного учебника по предмету АИС 1.03 MB
  Чтобы создать свою страничку, вам необязательно знать даже основы html, т.к. программа возьмет на себя львиную долю работы по написанию html-кода. Можно порекомендовать Macromedia Dreamweaver и как своеобразный учебник
63941. Технологическиий процесс приготовления сложной кулинарной продукции в ресторане «Аляска» 772.02 KB
  Вспомним к примеру знаменитые пиры римских патрициев где подавались невообразимые блюда вроде соловьиных язычков куда быстроногие рабы-бегуны доставляли живых миног с побережья моря и лед с вершин гор. В ресторане Аляска реализуют смешанные алкогольные и безалкогольные напитки...
63942. Онлайн түрдө дисктерди сатуу жана фильмдерди көрүү веб-сайты 4.28 MB
  Долбоор сайт болгондуктан жана жогоруда айтылып кеткен баардык касиеттерин жогорку сапатта ишке ашырыш үчүн PHP – тилинде жазылды. Иштетилип чыгып жаткан учурда ар кандай технологиялар колдонулду. Алар жөнүндө маалымат дагы айтылат.
63943. Улучшение организации производства работ на ООО «Тугай Агро» 5.71 MB
  Важнейшей задачей лесного хозяйства является повышение надежности и улучшения эксплуатации лесозаготовительной техники. Благодаря конструктивному совершенствованию лесосечных, лесотранспортных машин и нижескладского оборудования...
63944. Технологія приготування виробів із дріжджового безопарного тіста 388.66 KB
  Організація робочого місця під час приготування виробів із дріжджового безопарного тіста. Охорона праці в кондитерському цеху правила санітарії та гігієни при приготуванні виробів із дріжджового безопарного тіста.