Cтраница 2
Часто называется контекстно-свободной грамматикой или КС-грамматикой. [16]
Следующая ступень - контекстно-свободные грамматики, соответствующие автоматам с магазинной памятью. Наконец, появляются контекстно-связанные грамматики, реализуемые на машинах Тьюринга и потому, можно думать, характерные для процессов символической логики. [17]
Рассмотрим применение формализма контекстно-свободных грамматик для построения языка, с помощью которого можно описывать сценарии развития энергетической отрасли. [18]
Легко доказывается, что контекстно-свободная грамматика G нетерминально ограничена тогда и только тогда, когда каждый грамматический уровень грамматики G является линейным. [19]
Синтаксический анализ выражений в контекстно-свободных грамматиках на первый взгляд кажется требующим дорогостоящих возвратных вычислений. Коэффициент при / г3 зависит от грамматики. Долгое время этот результат оставался наилучшим, хотя для специальных классов контекстно-свободных грамматик были получены и лучшие оценки. [20]
Для каких задач могут применяться контекстно-свободные грамматики. [21]
Еще одна полезная редукция для контекстно-свободных грамматик использует понятие связности. [22]
Многие алгоритмы для разрешимых проблем контекстно-свободных грамматик вполне аналогичны алгоритму, который строится в следующем доказательстве. [23]
Равенство у 1 о для контекстно-свободных грамматик Хомского принадлежит Ингве. [24]
Язык, синтаксис которого описывается контекстно-свободной грамматикой. [25]
Однако ни автоматная грамматика, ни контекстно-свободная грамматика не позволяют порождать трансформационные преобразования фраз, о которых речь шла в гл. Расширенные сети переходов обладают такой возможностью. Именно поэтому они нашли такое широкое применение в наиболее продвинутых диалоговых системах. [26]
Предложение 3.2. Существуют алгоритмы, позволяющие для произвольной контекстно-свободной грамматики T ( V, А, я) определить, будет ли язык L ( F а) пуст, конечен или бесконечен. [27]
Этот словарь, вообще говоря, шире словаря контекстно-свободной грамматики, из которой получена данная нормальная грамматика. Добавились символы двух типов: те, которые позволяют заменить правило А - Вс правилами Л - БС и С - - с, и те, с помощью которых правило Л - гр, где i) имеет длину / 2, заменяется / - 1 двойным правилом. [28]
Большинство результатов о тьюринговой эквивалентности неразрешимых проблем, о списках контекстно-свободных грамматик выпадают из рассмотрений такого типа, и существующие различия легко объясняются видом последовательности кванторов, описывающих рассматриваемые множества. [29]
К данной проблеме нетрудно свести проблему равенства языков, порожденных контекстно-свободными грамматиками. Однако известен более сильный результат: проблема слабой эквивалентности неразрешима в классе унарных рекурсивных схем. [30]