Cтраница 1
Линейные грамматики и соответствующие КС-языки играют важную роль в теории формальных языков. Во многом это связано с тем, что линейные грамматики адекватно моделируют автоматные отображения. При этом необходимо учитывать, что если автомат с выходом задает частичное отображение вида ВХОД - ВЫХОД, то соответствующая моделирующая линейная грамматика порождает слова вида ВХОД о ВЫХОД, где ВХОД и ВЫХОД - входное и выходное слово автомата, а верхний индекс R означает зеркальное отображение слова ВЫХОД. [1]
Односторонние линейные грамматики - такие грамматики, правые части правил которых содержат терминальные символы, только с одной - стороны от нетерминального символа. [2]
Язык, порождаемый линейными грамматиками, называется линейным языком. [3]
Подклассом линейных КС-грамматик являются односторонние линейные грамматики. [4]
КС-грамматика называется металинейной, если правые части ее правил не содержат цели грамматики и все правила, левые части которых отличны от цели, имеют такой же вид, как правило линейной грамматики. [5]
Линейные грамматики и соответствующие КС-языки играют важную роль в теории формальных языков. Во многом это связано с тем, что линейные грамматики адекватно моделируют автоматные отображения. При этом необходимо учитывать, что если автомат с выходом задает частичное отображение вида ВХОД - ВЫХОД, то соответствующая моделирующая линейная грамматика порождает слова вида ВХОД о ВЫХОД, где ВХОД и ВЫХОД - входное и выходное слово автомата, а верхний индекс R означает зеркальное отображение слова ВЫХОД. [6]
Напомним, что грамматика называется линейной, если все ее правила имеют вид а - - иру или а - - ш, где а, 3 е VA, a. Язык называется линейным, если он может быть порожден линейной грамматикой. [7]
Алгоритм Эрли, тщательно прослеживая все варианты параллельно, получает представление всех возможных вариантов анализа цепочки по отношению к КС-грамматике за время, которое может быть ограничено величиной / ( я3, где п - длина цепочки, а Д - константа, зависящая только от грамматики и не зависящая от входной цепочки. Более того, для некоторых подклассов КС-грамматик можно показать, что граница требуемого времени может быть снижена до п2 для линейных грамматик и некоторых других и до п для LR ( k) - грамматик со считыванием вперед k символов ( Кнут [17]) и некоторых других. [8]
Лемма очевидным образом справедлива, если G содержит только одну переменную. Предположим теперь, что лемма выполняется для всех линейных грамматик с не более чем k - l переменными. L ( Gt) может быть получен из языков а: а е 2 U а, В ( J е посредством конечного числа операций U, , а-итерации и В-ите-рации. [9]
Линейные грамматики и соответствующие КС-языки играют важную роль в теории формальных языков. Во многом это связано с тем, что линейные грамматики адекватно моделируют автоматные отображения. При этом необходимо учитывать, что если автомат с выходом задает частичное отображение вида ВХОД - ВЫХОД, то соответствующая моделирующая линейная грамматика порождает слова вида ВХОД о ВЫХОД, где ВХОД и ВЫХОД - входное и выходное слово автомата, а верхний индекс R означает зеркальное отображение слова ВЫХОД. [10]