Для любого языка, заданного контекстно-зависимой грамматикой, можно построить грамматику
(*ответ*) неукорачивающую
регулярную
постоянную
ограниченную
Для операции обращения справедливо следующее равенство α,β
(*ответ*) (αβ)R = βRαR
(αβ)R = αRβR
(αβ)R = (βα)R
(αβ)R = αβR
Для построения вывода по алгоритму Кока–Янгера–Касами грамматика должна быть в нормальной форме
(*ответ*) Хомского
Кока–Янгера–Касами
Кока–Янгера
Янгера–Касами
Для построения распознавателей LL(k)-грамматик используется множество терминальных цепочек, выводимых из α(VTVN)*, укороченных до k символов
(*ответ*) FIRST(k,α)
FOLLOW(k,A)
FR(k,α)
k(FIRST)
Для преобразования в нормальную форму Хомского, предварительно грамматику надо
(*ответ*) преобразовать в приведенный вид
преобразовать в нормальный вид
упростить
детерминировать
Для преобразования произвольной КС-грамматики к приведенному виду, необходимо удалить
(*ответ*) все бесплодные символы
(*ответ*) все недостижимые символы
(*ответ*) цепные правила
единичные символы;
Для проверки принадлежности заданного языка классу КС-языков служит лемма о
(*ответ*) разрастании
правдоподобии
однозначности
объединении
Для работы алгоритма удаления недостижимых состояний используются множества состояний
(*ответ*) достижимых
(*ответ*) текущих активных
недостижимых
текущих пассивных
Для распознавателя на основе алгоритма «сдвиг-свертка» естественным является построение дерева вывода
(*ответ*) снизу вверх
сверху вниз
слева направо
справа налево
Для регулярных языков распознавателями являют (ет)ся
(*ответ*) конечные автоматы
двусторонние недетерминированные автоматы
односторонние недетерминированные автоматы
машина Тьюринга
Для языков с фразовой структурой распознавателем являет (ют)ся
(*ответ*) машина Тьюринга
двусторонние недетерминированные автоматы
односторонние недетерминированные автоматы
конечные автоматы
Если α = «2334» то αR =
(*ответ*) «4332»
«23342334»
«4»
«2334»
Если α = β, то
(*ответ*) |α| = |β|
|α| = β
α = |β|
α =|α +β|