Контекстно-свободный язык

Cтраница 2

Поскольку известно, что все контекстно-свободные языки являются контекстно-связанными и существуют контекстно-свободные языки, не являющиеся языками сетей Петри, приходим к выводу, что существуют контекстно-связанные языки, не являющиеся языками сетей Петри. [16]

Нужно подчеркнуть, что иерархии контекстно-свободных языков, определяемые четырьмя моделями машин, различны. Языки, легко разрешимые на машинах одного типа, могут быть трудно разрешимыми машинами другого типа, и наоборот. [17]

Такая эффективность стимулирует дальнейшие поиски контекстно-свободных языков, пригодных для практического программирования. [18]

Этот метод применим ко всем контекстно-свободным языкам [3], так как любую КС грамматику с помощью эквивалентного преобразования можно сделать грамматикой предшествования. Эффективность названного метода повышается, если матрицу отношений предшествования заменить функциями предшествования, также введенными Флойдом. Однако не всякая грамматика предшествования обладает функциями предшествования. В данной работе показывается, что каждую грамматику, не обладающую функциями предшествования, можно преобразовать в эквивалентную грамматику, обладающую такими функциями. [19]

Остается открытым вопрос, существуют ли контекстно-свободные языки, требующие больше чем L ( n) ogn на двусторонних машинах Тьюринга. Мы предполагаем, что такие языки существуют и что ( log n) 2 - настоящая граница. [20]

Гинзбург и Спейнер подробно исследовали подсемейство контекстно-свободных языков - ограниченные контекстно-свободные языки, которые много лучше ведут себя по. Для подробного знакомства с этими языками мы отсылаем читателя к гл. [21]

Существование и регулярных множеств, и ограниченных контекстно-свободных языков в качестве подмножеств класса языков сетей Петри оказывается полезным, поскольку оба класса языков имеют желательные свойства и некоторые благоприятные для анализа характеристики. [22]

Остается только показать, что L7 - контекстно-свободный язык. [23]

Класс левоконтекстных языков не совпадает с классом контекстно-свободных языков. [24]

Класс правоконтекстных языков не совпадает с классом контекстно-свободных языков. [25]

Мы покажем, что L4 и L5 суть контекстно-свободные языки, разрешимые односторонней магазинной машиной. [26]

Детерминант рекурсивной схемы может быть задан в виде контекстно-свободного языка ( см. Грамматика бесконтекстная), однако вопрос о разрешимости соответствующей формальной эквивалентности остается пока ( 1983) открытым. [27]

Контекстно-связанный язык сети Петри, не являющийся контекстно-свободным. [28]

В отличие от случая с регулярными языками существуют также контекстно-свободные языки, не являющиеся языками сетей Петри. Примером такого языка служит контекстно-свободный язык WWR W. На основе этого доказывается следующее утверждение. [29]

Теперь, когда мы показали, что не все контекстно-свободные языки являются языками сетей Петри и не все языки сетей Петри являются контекстно-свободными, естественно возникает вопрос: что из себя представляет класс языков, являющихся одновременно контекстно-свободными и языками сетей Петри. В настоящее время мы не в состоянии дать полный ответ на этот вопрос, но известна некоторая информация о языках, входящих в пересечение упомянутых классов. Одним подмножеством класса контекстно-свободных языков сетей Петри является класс регулярных языков. [30]

Страницы: 1 2 3 4