Введение в схемы, автоматы и алгоритмы

<<- Назад к вопросам

Ниже приведена диаграмма конечного автомата A= <Σ ={a, b}, Q ={ q, p, r, s }, q, F={s}, Φ>,

Какой из следующих языков распознает автомат A ?

(Отметьте один правильный вариант ответа.)

Варианты ответа

все слова, начинающиеся на b и заканчивающиеся на a , в которых буквы b идут блоками четной длины

все слова, начинающиеся на b и заканчивающиеся на a

все слова, начинающиеся блоком букв b нечетной длины, после которого стоит буква a(Верный ответ)

все слова, в которых буквы b идут блоками нечетной длины

все слова, начинающиеся на b и заканчивающиеся на a , в которых буквы b идут блоками нечетной длины

Похожие вопросы

Ниже приведена диаграмма конечного автомата A= <Σ ={a, b}, Q ={ q, p, r, s }, q, F={s}, Φ>,

Какой из следующих языков распознает автомат A ?

Ниже приведена диаграмма конечного автомата A= <Σ ={a, b}, Q ={ q, p, r, s }, q, F={s}, Φ>,

Какой из следующих языков распознает автомат A ?

Заданы два НКА:

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

Какие из следующих трех НКА С₁ , С₂ , С₃ распознают конкатенацию L_A? L_B языков, распознаваемых автоматами A и B?С₁ = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F₁={ q2}, Φ₁>, С₂ = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F₂={ q2}, Φ₂>, С₃ = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F₃={ q2}, Φ₃>, где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода).

Заданы два НКА:

A =< {a, b}, {0, 1, 2, 3}, 0, {2}, Φ_A > с программой Φ_A: 0 a → 1, 0 b → 3, 1 a → 2, 1 b → 1, 2 a → 1, 2 b → 3, 3 a → 3, 3b → 3 и

B =< {a, b}, {q0, q1, q2}, q0, {q2}, Φ_B > с программой Φ_B: q0 b → q0, q0 b → q1, q1 a → q1, q1 a → q2, q2 b → q0

Какие из следующих трех НКА С₁ , С₂ , С₃ распознают конкатенацию L_A? L_B языков, распознаваемых автоматами A и B?

С₁ = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F₁={ q2},Φ₁> ,

С₂ = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F₂={ q2},Φ₂> ,

С₃ = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F₃={ q2}, Φ₃> , где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода).

Заданы два НКА:

A =< {a, b}, {0, 1, 2, 3}, 0, {2}, Φ_A > с программой Φ_A: 0 a → 1, 0 b → 3, 1 a → 3 1 b → 2, 2 a → 3, 2 b → 2, 3 a → 3, 3b → 3 и

B =< {a, b}, {q0, q1, q2}, q0, {q2}, Φ_B > с программой Φ_B: q0 a → q0, q0 b → q1, q1 a → q1, q1 a → q2

Какие из следующих трех НКА С₁ , С₂ , С₃ распознают конкатенацию L_A? L_B языков, распознаваемых автоматами A и B?С₁ = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F₁={ q2}, Φ₁>, С₂ = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F₂={ q2}, Φ₂>, С₃ = < {a,b}, {0, 1, 2, 3, q1, q2}, 0, F₃={ q2}, Φ₃>, где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода).

На следующем рисунке представлены диаграммы двух конечных автоматов A =< {a,b}, {q,p}, q, {p}, Φ_A> и B =< {a,b}, {1, 2, 3}, 1, {1, 2}, Φ_B>,

распознающих языки L_A и L_B, соответственно. Какой из следующих автоматов является произведением A × B и какой язык он реализует?

C = <{a,b}, { (q, 1), (q,2), (q,3), (p, 1), (p,2), (p,3)}, (q,0), F={(q, 1), (q, 2)}, Φ_C >,

D = <{a,b}, { (q, 1), (q,2), (q,3), (p, 1), (p,2) , (p,3)}, (q,0), F={(p,3)}, Φ_D >,

C = <{a,b}, { (q, 1), (q,2), (q,3), (p, 1), (p,2), (p,3)}, (q,0), F={(p,3)}, Φ_C >,

D = <{a,b}, { (q, 1), (q,2), (q,3), (p, 1), (p,2) , (p,3)}, (q,0), F={(p,1), (p,2)}, Φ_D >,

C = <{a,b}, { (q, 1), (q,2), (q,3), (p, 1), (p,2), (p,3)}, (q,0), F={(q, 1), (q, 2)}, Φ_C >,

D = <{a,b}, { (q, 1), (q,2), (q,3), (p, 1), (p,2) , (p,3)}, (q,0), F={(p,1), (p,2)}, Φ_D >,

Ниже приведен конечный автомат - распознаватель A= <Σ ={a, b}, Q ={ 0, 1, 2, 3, 4, 5 }, 0, F={ 3, 4}, Φ>,где

Какие из следующих трех слов распознаются автоматом A?W= aaabaabab, V= abababaab, U= bbabbbababa

Ниже приведен конечный автомат - распознаватель A= <Σ ={a, b}, Q ={ 0, 1, 2, 3, 4, 5 }, 0, F={ 3, 4}, Φ>,где

Какие из следующих трех слов распознаются автоматом A?W= aaabbabab, V= babbbabba, U= ababaaab