formal_languages_translation_theory (Формальные грамматики), страница 2

PDF-файл formal_languages_translation_theory (Формальные грамматики), страница 2 Программное обеспечение систем автоматизированного проектирования (ПО САПР) (112565): Книга - 3 семестрformal_languages_translation_theory (Формальные грамматики) - PDF, страница 2 (112565) - СтудИзба2021-10-05СтудИзба

Описание файла

PDF-файл из архива "Формальные грамматики", который расположен в категории "". Всё это находится в предмете "программное обеспечение систем автоматизированного проектирования (по сапр)" из 3 семестр, которые можно найти в файловом архиве МГТУ им. Н.Э.Баумана. Не смотря на прямую связь этого архива с МГТУ им. Н.Э.Баумана, его также можно найти и в других разделах. .

Просмотр PDF-файла онлайн

Текст 2 страницы из PDF

Однако до сих пор открыт вопрос, существует ли для любого ЛОА эквивалентный ему детерминированный ЛОА.5Элементы теории формальных языков и грамматик / Основные понятия и определенияS→ 0A10A → 00A1A → *Определение: цепочка   ( T  N ) непосредственно выводима из цепочки  ( T  N ) в грамматике G   T, N, P, S  (обозначается  →G ), если   12,   12, где*1, 2,   (T  N ) ,   (T  N ) и правило вывода  →  содержится в P. Индекс G в обозначении →G обычно опускают, если понятно, о какой грамматике идет речь.Например, цепочка 00A11 непосредственно выводима из 0A1 в грамматике Gexample :0A1 → 00A11.

Здесь цепочка 0A, подчеркнутая двойной чертой, играет роль подцепочки  изопределения, цепочка 00A1 играет роль подцепочки , 1  , 2  1.*Определение:цепочка  (T  N )выводимаизцепочки  (T  N) в грамматике G  T, N, P, S  (обозначается  G ), если существуют цепочки 0, 1, ..., n (n  0), такие, что   0 → 1 → ... → n  . Последовательность0, 1, ..., n называется выводом длины n. Индекс G в обозначении G опускают, если понятно, какая грамматика подразумевается.Например, S  000A111 в грамматике Gexample (см. пример выше), т.к. существует вывод S → 0A1 → 00A11 → 000A111.

Длина вывода равна 3.Определение: языком, порождаемым грамматикой G   T, N, P, S , называетсямножество L(G)  {  T * | S  }.Другими словами, L(G) — это все цепочки в алфавите T, которые выводимы из S сn nпомощью правил P. Например, L(Gexample)  {0 1 | n  0}.Определение: цепочка   (T  N)*, для которой S  , называется сентенциальнойформой в грамматике G   T, N, P, S .Таким образом, язык, порождаемый грамматикой, можно определить как множествотерминальных сентенциальных форм.Определение: грамматики G1 и G2 называются эквивалентными, еслиL(G1)  L(G2).Пример. Грамматики G1  {0,1}, {A,S}, P1, S  и G2  {0,1}, {S}, P2, S  с правиламиP1:P2:S → 0A1S → 0S1 | 010A → 00A1A → n nэквивалентны, т.

к. обе порождают язык L(G1)  L(G2)  {0 1 | n  0}.Определение:грамматикиG1иG2почтиэквивалентны,еслиL(G1)  {}  L(G2)  {}.Другими словами, грамматики почти эквивалентны, если языки, ими порождаемые,отличаются не более, чем на .Например, почти эквивалентны грамматикиG1  {0,1}, {A, S}, P1, S 6иG2  {0, 1}, {S}, P2, S  с правиламиЭлементы теории формальных языков и грамматик / Классификация грамматик и языков по ХомскомуP1:P2:S → 0A10A → 00A1A →n nS → 0S1 | ,n nтак как L(G1)  {0 1 | n  0}, а L(G2)  {0 1 | n  0}, т.

е. L(G2) состоит из всех цепочек языка L(G1) и пустой цепочки, которая в L(G1) не входит.Классификация грамматик и языков по ХомскомуОпределим с помощью ограничений на вид правил вывода четыре типа грамматик:тип 0, тип 1, тип 2, тип 3. Каждому типу грамматик соответствует свой класс 3) языков. Еслиязык порождается грамматикой типа i (для i  0, 1, 2, 3), то он является языком типа i.Тип 0Любая порождающая грамматика является грамматикой типа 0. На вид правил грамматик этого типа не накладывается никаких дополнительных ограничений. Класс языков типа 0 совпадает с классом рекурсивно перечислимых языков.Грамматики с ограничениями на вид правил выводаТип 1Грамматика G   T, N, P, S  называется неукорачивающей, если правая часть каждогоправила из P не короче левой части (т.

е. для любого правила  →   P выполняется неравенство |  |  |  | ). В виде исключения в неукорачивающей грамматике допускается наличие правила S → , при условии, что S (начальный символ) не встречается в правых частяхправил.Грамматикой типа 1 будем называть неукорачивающую грамматику.Тип 1 в некоторых источниках определяют с помощью так называемых контекстнозависимых грамматик.Грамматика G   T, N, P, S  называется контекстно-зависимой (КЗ), если каждое*правило из P имеет вид  → , где   1A2,   12, A  N,   (T  N ), 1, 2  (T  N) .В виде исключения в КЗ-грамматике допускается наличие правила с пустой правой частьюS → , при условии, что S (начальный символ) не встречается в правых частях правил.Цепочку 1 называют левым контекстом, цепочку 2 называют правым контекстом.

Язык, порождаемый контекстно-зависимой грамматикой, называется контекстнозависимым языком.ЗамечаниеИз определений следует, что если язык, порождаемый контекстно-зависимой или неукорачивающей грамматикой G   T, N, P, S , содержит пустую цепочку, то эта цепочка выводится в G заодин шаг с помощью правила S → . Других выводов для  не существует. Если среди правил Pнет правила S → , то порождаемый контекстно-зависимой или неукорачивающей грамматикойG язык не содержит пустую цепочку .3)Классом обычно называют множество, элементы которого сами являются множествами.7Элементы теории формальных языков и грамматик / Классификация грамматик и языков по ХомскомуУтверждение 1.

Пусть L — формальный язык. Следующие утверждения эквивалентны:1) существует контекстно-зависимая грамматика G1, такая что L  L(G1);2) существует неукорачивающая грамматика G2, такая что L  L(G2).Очевидно, что из (1) следует (2): любая контекстно-зависимая грамматика удовлетворяет ограничениям неукорачивающей грамматики (см. определения). Доказательство в обратную сторону основывается на том, что можно каждое неукорачивающее правило заменить эквивалентной серией контекстно-зависимых правил.Из утверждения 1 следует, что язык, порождаемый неукорачивающей грамматикой,контекстно-зависим.

Таким образом, неукорачивающие и КЗ-грамматики определяют один итот же класс языков.Тип 2Грамматика G   T, N, P, S  называется контекстно-свободной (КС), если каждое*правило из Р имеет вид A → , где A  N,   ( T  N ) .Заметим, что в КС-грамматиках допускаются правила с пустыми правыми частями.Язык, порождаемый контекстно-свободной грамматикой, называется контекстносвободным языком.Грамматикой типа 2 будем называть контекстно-свободную грамматику.КС-грамматика может являться неукорачивающей, т.е. удовлетворять ограничениямнеукорачивающей грамматики.Утверждение 2. Для любой КС-грамматики G существует неукорачивающая КСграмматика G', такая что L(G)  L(G').Согласно утверждению 2, любой контекстно-свободный язык порождается неукорачивающей контекстно-свободной грамматикой.

Как следует из определений, такая КСграмматика может содержать не более одного правила с пустой правой частью, причем этоправило имеет вид S → , где S — начальный символ, и при этом никакое правило из P несодержит S в своей правой части.В разделе «Преобразования грамматик» будет приведен алгоритм, позволяющийустранить из любой КС-грамматики все правила с пустыми правыми частями (в получившейся грамматике может быть правило S →  в случае, если пустая цепочка принадлежитязыку, при этом начальный символ S не будет входить в правые части правил).Тип 3Грамматика G   T, N, P, S  называется праволинейной, если каждое правило из Р*имеет вид A → wB либо A → w, где A, B  N, w  T .Грамматика G   T, N, P, S  называется леволинейной, если каждое правило из Р име*ет вид A → Bw либо A → w, где A, B  N, w  T .Утверждение 3.

Пусть L — формальный язык. Следующие два утверждения эквивалентны: существует праволинейная грамматика G1, такая что L  L(G1); существует леволинейная грамматика G2, такая что L  L(G2).8Элементы теории формальных языков и грамматик / Классификация грамматик и языков по ХомскомуИз утверждения 3 следует, что праволинейные и леволинейные грамматики определяют один и тот же класс языков. Такие языки называются регулярными. Право- и леволинейные грамматики также будем называть регулярными.Регулярная грамматика является грамматикой типа 3.Автоматной грамматикой называется праволинейная (леволинейная) грамматика,такая, что каждое правило с непустой правой частью имеет вид: A → a либо A → aB (длялеволинейной, соответственно, A → a либо A → Ba), где A, B  N, a  T.

4)Автоматная грамматика является более простой формой регулярной грамматики. Существует алгоритм, позволяющий по регулярной (право- или леволинейной) грамматике построить соответствующую автоматную грамматику. Таким образом, любой регулярный языкможет быть порожден автоматной грамматикой. Кроме того, существует алгоритм, позволяющий устранить из регулярной (автоматной) грамматики все -правила (кроме S →  в случае, если пустая цепочка принадлежит языку; при этом S не будет встречаться в правых частях правил) 5). Поэтому справедливо:Утверждение 4. Для любой регулярной (автоматной) грамматики G существует неукорачивающая регулярная (автоматная) грамматика G′, такая что L(G)  L(G′).Иерархия ХомскогоУтверждение 5.

Свежие статьи
Популярно сейчас
Зачем заказывать выполнение своего задания, если оно уже было выполнено много много раз? Его можно просто купить или даже скачать бесплатно на СтудИзбе. Найдите нужный учебный материал у нас!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
5288
Авторов
на СтудИзбе
417
Средний доход
с одного платного файла
Обучение Подробнее