Материалы (3) (1115030)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

34(1)Примеры грамматик и языковS  ABCSBA  AB| ABcCA  ACCB  BCCc  ccBc  bcBb  bbAb  abAa  aaТип 1. Неукорачивающая, но не КЗ{a nbn c n | n  0}Язык:35Примеры грамматик и языков(2)S  aSb | abЯзык:{a n b n | n  0}(3)S  aS | aЯзык:{a n | n  0}36Иерархия классов Хомского{an bn | n>0}{an | n>0}{an bn cn| n>0}Язык записей самоприменимых алгоритмов37Задача распознаванияДаны грамматика G и цепочка xxL(G) ?Для грамматик типа 1 (а также типов 2 и 3) по классификацииХомского задача распознавания разрешима, т.е. существуетобщий алгоритм, отвечающий на вопрос: x  L(G) ?38Контекстно-свободные грамматики и языки39КС-грамматики позволяют выразить такие свойства языковпрограммирования, как скобочные структуры, последовательностьописаний и операторов и др.

Но не могут задавать контекстнозависимые свойства, например, соответствие числа формальных ифактических параметров при вызове функции. Для КС-грамматиксуществуют эффективные алгоритмы анализа, поэтому ониприменяются в трансляции, контекстные условия проверяются наэтапе семантического анализа40Левый (левосторонний) вывод цепочки   T* из S  N в КСграмматике G = (T, N, P, S) :в этом выводе каждая очередная сентенциальная форма получаетсяиз предыдущей заменой самого левого нетерминала.Правый (правосторонний) вывод цепочки   T* из S  N в КСграмматике G = (T, N, P, S ):в этом выводе каждая очередная сентенциальная форма получаетсяиз предыдущей заменой самого правого нетерминала.41Рассмотрим пример грамматики:G = ({a,b,+}, {S,T}, {S  T | T+S; T  a | b}, S)можно построить выводы для цепочки a+b+a :(1)ST+S  T+T+S  T+T+T  a+T+T  a+b+T  a+b+a(2)S  T+S  a+S  a+T+S  a+b+S  a+b+T  a+b+a(3)S  T+S  T+T+S  T+T+T  T+T+a  T+b+a a+b+aЗдесь (2) - левосторонний вывод, (3) - правосторонний, а (1) не являетсяни левосторонним, ни правосторонним42Определение: упорядоченное ориентированное деревоназывается деревом вывода (или деревом разбора) в КСграмматике G = (T, N, P, S), если выполнены следующиеусловия:(1) каждая вершина дерева помечена символом из множестваNT{}, при этом корень дерева помечен символом S; листья символами из T{};(2) если вершина дерева помечена символом A , а еенепосредственные потомки - символами a1, a2, ...

, an, гдекаждое ai  TN, то A  a1a2...an - правило вывода в этойграмматике;(3) если вершина дерева помечена символом A , а ее единственныйнепосредственный потомок помечен символом , то A   —правило вывода в этой грамматике.43Пример дерева вывода для цепочки a+b+a в грамматике G =({a,b,+}, {S,T}, {S  T | T+S; T  a | b}, S) :STS+SaT+Tba(1)ST+S  T+T+S  T+T+T  a+T+T  a+b+T  a+b+a(2)S  T+S  a+S  a+T+S  a+b+S  a+b+T  a+b+a(3)S  T+S  T+T+S  T+T+T  T+T+a  T+b+a a+b+a44КС-грамматика G называется неоднозначной,если существует хотя бы одна цепочка   L(G), для которойможет быть построено два или более различных деревьеввывода.Это утверждение эквивалентно тому, что цепочка  имеет дваили более разных левосторонних (или правосторонних)выводов.В противном случае грамматика называется однозначной.45Утв.

Проблема определения, является ли заданная КСграмматика однозначной, является алгоритмическинеразрешимой.Язык, порождаемый грамматикой, называется неоднозначным,если он не может быть порожден никакой однозначнойграмматикой.Утв. Проблема определения, порождает ли данная КСграмматика однозначный язык (т.е. существует лиэквивалентная ей однозначная грамматика), являетсяалгоритмически неразрешимой.•Пример неоднозначного языка:L= {an bn cm| n>0, m>0}  {an bm cm| n>0,m>0}.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов учебной работы