Cтраница 1
Контекстно-свободные языки часто изучаются совместно с магазинными машинами из-за следующих обстоятельств. [1]
Существуют контекстно-свободные языки, не являющиеся автоматными языками. [2]
Все нерегулярные контекстно-свободные языки, которые можно разрешить на односторонней магазинной машине, требуют по крайней мере L ( n) ogn для своего разрешения на двусторонней машине Тьюринга. [3]
Класс контекстно-свободных языков является собственным подклассом класса контекстно-зависимых языков. Контекстно-свободные языки порождаются магазинными автоматами [5] и играют важную роль как синтаксические модели современных языков программирования. [4]
Класс контекстно-свободных языков особенно интересен, так как включает АЛГОЛ и другие языки программирования. [5]
Аналогично, контекстно-свободные языки являются носителями алгебраических степенных рядов ( см. ниже определение 4.5); поэтому мы называем их алгебраическими языками. Поскольку имеется несколько превосходных изложений теории контекстно-свободных языков ( С. Гинзбург [1966], Бут [1967], Гросс, Лан-тен [1967], Арбиб [1969], Хопкрофт, Ульман [1969] 1)), мы не пытались дать ее общий обзор в этой главе. Всюду в этой главе нашей главной задачей является дальнейший анализ рациональных языков в рамках более общих иерархий. [6]
Существуют ли контекстно-свободные языки, являющиеся языками сетей Петри, но не являющиеся ограниченными. Гинзбург показал, что регулярное выражение ( а Ь) не является ограниченным контекстно-свободным языком. Так как этот язык - контекстно-свободный язык сети Петри, очевидно, что ограниченные контекстно-свободные языки являются лишь собственным подмножеством семейства контекстно-свободных языков сетей Петри. Кроме того, язык ( а b) anbn n 1, являющийся контекстно-свободным, не ограничен и не регулярен. Для полной характеризации множества контекстно-свободных языков сетей Петри необходимы дальнейшие исследования. [7]
В классе контекстно-свободных языков разрешимы проблемы принадлежности, пустоты и конечности, но не разрешима проблема эквивалентности контекстно-свободных грамматик. В этом параграфе рассматриваются соответствующие проблемы для введенных выше классов языков сетей Петри. [8]
Типы формальных грамматик. [9] |
Особый подкласс контекстно-свободных языков, называемый языками с ограниченным контекстом, играет важную роль при реализации компиляторов. [10]
Контекстно-связанный язык сети Петри, не являющийся контекстно-свободным. [11] |
Теорема 6.9. Существуют контекстно-свободные языки, не являющиеся языками сетей Петри. [12]
Теорема 3.6. Существует контекстно-свободный язык, не порождаемый ни одной ( помеченной) сетью Петри. [13]
Множество предложений является контекстно-свободным языком тогда и только тогда, когда его можно разрешить недетерминированной односторонней магазинной машиной. [14]
Необходимо подчеркнуть, что контекстно-свободные языки представляют собой лишь формальную математическую модель, приближенно описывающую естественные языки. Тем не менее в 1960 г. было обнаружено, что весь Алгол можно трактовать как контекстно-свободный язык. Полученные в этом направлении результаты вызвали большой интерес к контекстно-свободным языкам как к моделям языков программирования - части теории обработки данных. Математическая лингвистика играет большую роль в исследовании машинных языков, доставляет основополагающие идеи для их изучения, вводит важные понятия, но не дает эффективных методов измерения, позволяющих сравнивать различные машинные языки. [15]