Контекстно-свободный язык - Большая Энциклопедия Нефти и Газа, статья, страница 1
Если Вас уже третий рабочий день подряд клонит в сон, значит сегодня среда. Законы Мерфи (еще...)

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

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 Типы формальных грамматик. [9]

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

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

Теорема 6.9. Существуют контекстно-свободные языки, не являющиеся языками сетей Петри.  [12]

Теорема 3.6. Существует контекстно-свободный язык, не порождаемый ни одной ( помеченной) сетью Петри.  [13]

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

Необходимо подчеркнуть, что контекстно-свободные языки представляют собой лишь формальную математическую модель, приближенно описывающую естественные языки. Тем не менее в 1960 г. было обнаружено, что весь Алгол можно трактовать как контекстно-свободный язык. Полученные в этом направлении результаты вызвали большой интерес к контекстно-свободным языкам как к моделям языков программирования - части теории обработки данных. Математическая лингвистика играет большую роль в исследовании машинных языков, доставляет основополагающие идеи для их изучения, вводит важные понятия, но не дает эффективных методов измерения, позволяющих сравнивать различные машинные языки.  [15]



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