Какие из следующих соотношений истинны для регулярных выражений в алфавите {a, b, c}?
Пусть p(n) - максимальная продуктивность Абак-программы, состоящей из n команд. Какие соотношения для функции p(n) истинны?
Какие из следующих регулярных выражений в алфавите {a, b, c} являются решениями уравнения X = Xα , где α = ab+aс?
Какие из следующих регулярных выражений в алфавите {a, b, c} являются решениями уравнения X =αX + β, где α = b+с, β = ab*?
Какие из следующих регулярных выражений в алфавите {a, b, c} являются решениями уравнения X = Xα + β, где α = b+с, β = ab*?
Пусть n[x] - количество узлов в поддереве с корнем х, а h[x] - высота узла х. Какие из перечисленных ниже утверждений истинны после выполнения любой последовательности операций типа СОЗДАТЬ, ОБЪЕДИНИТЬ, НАЙТИ для любого узла x?
Пусть P - трехместный предикатный символ; f , g - одноместные функциональные символы; x, y, u - переменные; b - константа. Какие из подстановок являются унификаторами атомарных формул P(b, y, f (g(y))) и P(x, f (x), f (u))?
Пусть P, Q и S - одноместные и R - двухместный предикатные символы; a, b - константы. Какие из перечисленных ниже формул могут быть выведены с помощью правила резолюции из формул P(x) ∨ Q(y) ∨ R(b, x) и P(b) ∨ S(y) ∨ R(y, a)?
Пусть P - трехместный предикатный символ; f , g - одноместные функциональные символы; x, y, z - переменные; b - константа. Какие из формул A= P(b, y, f (g(y))), B= P(x, f (z), f (z)) и C= P(x, f (x), f (z)) унифицируемы?
Пусть P Q и S- одноместные и R - двухместный предикатные символы, a, b - константы. Какие из перечисленных ниже формул могут быть выведены с помощью правила резолюции из формул P(x) ∨ Q(y) ∨ R(b, x) и P(b) ∨ S(y) ∨ R(y, a)?
