Пусть регулярное выражение (ab)*a определяет некоторый язык над алфавитом S={a, b} . Другим регулярным выражением для этого языка может быть:

Правильный ответ:

• # Следующий конечный автомат - преобразователь MINUS= <ΣX ={0, 1} ΣY= { 0, 1}, Q ={ 0, 1, 2, 3 }, 0, Φ, Ψ>, где [Большая Картинка] вычитает из входного двоичного числа x некоторую константу c и выдает при c ≤ x выходное двоичное число y = x –c Чему равна эта константа c?
• # Заданы два НКА: A =< {a, b}, {0, 1, 2, 3}, 0, {2}, ΦA > с программой ΦA: 0 a →​ 1, 0 a →​ 2, 0 b →​ 0, 1 a →​ 2, 1 b →​ 1, 2 a →​ 3, 2 b →​ 2, 3 a →​ 3, 3b →​ 3 и B =< {a, b}, {q0, q1, q2}, q0, {q2}, ΦB > с программой ΦB: q0 a →​ q1, q1 b →​ q0, q1 a →​ q2, q2 b →​ q1 Какие из следующих трех НКА С1 , С2 , С3 распознают конкатенацию LA? LB языков, распознаваемых автоматами A и B? С1 = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F1={ q2}, Φ1>, С2 = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F2={ q2}, Φ2>, С3 = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F3={ q2}, Φ3>, где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода). [Большая Картинка]
• # Используя теорему о разрастании, установите, какие из следующих трех языков в алфавите {a, b} не являются автоматными. L1 = { wbw | w = an , n > 0 }, L2 = { bwwb | w = an , n > 0 }, L3 = { (ab)nam | n, m > 0 }.
• # Пусть машина Тьюринга M построена из следующих простых машин Тьюринга: Копa –копирует вход после разделительного символа a : w ⇐ w a w; Зам(a, b) – заменяет первое слева вхождение символа a на b: w1a w2 ⇐ w1 b w2 ( a ∉ w1 ); Сум - складывает два аргумента в унарной системе: |x * |y ⇐ |x+y ; Умн - умножает два аргумента в унарной системе: |x * |y ⇐ |xy; с помощью операций последовательного и параллельного применения следующим образом: M = Коп# ; par#( Коп* , Коп* ); par#( Умн, Сум); Зам(#, *); Сум Какую из следующих арифметических функций f(x) (при унарном кодировании аргумента и результата) вычисляет M?
• # Пусть машина Тьюринга M построена из простых машин Тьюринга Копa , Зам(a, b), Сум, Умн и Пуст, описанных в задаче 4, и машин Выбin – выбирает i-ый аргумент из n аргументов: x1*…*xi*…*xn ⇐ xi ,Большеij - выдает 0, если в аргументе вида |x1 *…*|xi *…*|xj *…*|xn i-ый аргумент xi больше j-ого аргумента xj , иначе выдает 1, с помощью операций последовательного и параллельного применения и конструкции условного оператора следующим образом: M = Коп# ; par#( par* (Коп*, Пуст ); Зам(*, |), Пуст ); if Больше21 then par#( Пуст, Сум ) else par#( Пуст, Умн ) endif; Зам(#, *); Выб33. Какие результаты она получит на входных данных вида |x1 * |x2 при x1 = 2, x2 = 7 и при x1 = 3, x2 = 5, соответственно?