В информатике , грамматика неофициально называется рекурсивной грамматикой , если он содержит правило производства , которые являются рекурсивными , а это означает , что расширение не-терминал в соответствии с этими правилами может в конечном итоге привести к строке , которая снова включает в себя тот же нетерминал. В противном случае это называется нерекурсивной грамматикой . [1]
Например, грамматика для контекстно-свободного языка является леворекурсивным , если существует не-терминального символа А , который может быть положить через продукционных правил , чтобы произвести строку с A (как крайний левый символ). [2] [3] Все типы грамматик в иерархии Хомского могут быть рекурсивными, и именно рекурсия позволяет создавать бесконечные наборы слов. [1]
Свойства [ править ]
Безрекурсивная грамматика может создать только конечный язык; и каждый конечный язык может быть произведен с помощью нерекурсивной грамматики. [1] Например, прямолинейная грамматика дает всего одно слово.
Рекурсивная контекстно-свободная грамматика, не содержащая бесполезных правил, обязательно дает бесконечный язык. Это свойство формирует основу для алгоритма, который может эффективно проверять, создает ли контекстно-свободная грамматика конечный или бесконечный язык. [4]
Ссылки [ править ]
- ^ a b c Недерхоф, Марк-Ян; Сатта, Джорджио (2002), «Анализ нерекурсивных контекстно-свободных грамматик», Труды 40-го ежегодного собрания Ассоциации компьютерной лингвистики (ACL '02) , Страудсбург, Пенсильвания, США: Ассоциация компьютерной лингвистики, стр. 112– 119, DOI : 10,3115 / 1073083,1073104.
- ^ Заметки по теории формального языка и синтаксическому анализу , Джеймс Пауэр, факультет компьютерных наук Национального университета Ирландии, Мейнут Мейнут, графство Килдэр, Ирландия.
- ^ Мур, Роберт С. (2000), «Удаление левой рекурсии из контекстно-свободных грамматик», Труды 1-го Североамериканского отделения конференции Ассоциации компьютерной лингвистики (NAACL 2000) , Страудсбург, Пенсильвания, США: Ассоциация компьютерной лингвистики , стр. 249–255.
- ^ Флек, Артур Чарльз (2001), Формальные модели вычислений: конечные пределы вычислений , серия AMAST в вычислениях, 7 , World Scientific, теорема 6.3.1, с. 309, ISBN 9789810245009.
