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

Упражнение 1:

Номер 1

 Пусть задан конечный автомат - преобразователь 
A = <Σ_X ={0, 1} Σ_Y= { А, Р, Т}, Q ={ 0, 1, 2, 3 }, 0, Φ, Ψ>, где

 
Какое входное слово автомат А перерабатывает в выходное слово АРАРАТ?

Ответ:

(1) 100101

(2) 000001

(3) 100011

(4) 100001

(5) никакое

Номер 2

 Пусть задан конечный автомат - преобразователь 
A = <Σ_X ={0, 1} Σ_Y= { А, Р, Т}, Q ={ 0, 1, 2, 3 }, 0, Φ, Ψ>,
где

Какое входное слово автомат А перерабатывает в выходное слово ТАРАРА?

Ответ:

(1) 010001

(2) 010000

(3) 100011

(4) 000001

(5) никакое

Номер 3

 Пусть задан конечный автомат - преобразователь 
A = <Σ_X ={0, 1} Σ_Y= { А, Р, Т}, Q ={ 0, 1, 2, 3 }, 0, Φ, Ψ>,
где

Какое входное слово автомат А перерабатывает в выходное слово ТАРТАР?

Ответ:

(1) 010100

(2) 010000

(3) 100011

(4) 000001

(5) никакое

Упражнение 2:

Номер 1

 Следующий конечный автомат - преобразователь 
MINUS= <Σ_X ={0, 1} Σ_Y= { 0, 1}, Q ={ 0, 1, 2, 3 }, 0, Φ, Ψ>,
где

 
вычитает из входного двоичного числа x некоторую константу c и выдает при c ≤ x выходное двоичное число y = x – c Чему равна эта константа c?

Ответ:

(1) 1

(2) 2

(3) 3

(4) 4

(5) 5

Номер 2

 Следующий конечный автомат - преобразователь 
MINUS= <Σ_X ={0, 1} Σ_Y= { 0, 1}, Q ={ 0, 1, 2, 3 }, 0, Φ, Ψ>,
где

 
вычитает из входного двоичного числа x некоторую константу c и выдает при c ≤ x выходное двоичное число y = x –c Чему равна эта константа c?

Ответ:

(1) 1

(2) 2

(3) 3

(4) 4

(5) 5

Номер 3

 Следующий конечный автомат - преобразователь 
MINUS= <Σ_X ={0, 1} Σ_Y= { 0, 1}, Q ={ 0, 1, 2 }, 0, Φ, Ψ>,
где


вычитает из входного двоичного числа x некоторую константу c и выдает при c ≤ x выходное двоичное число y = x –c Чему равна эта константа c?

Ответ:

(1) 1

(2) 2

(3) 3

(4) 4

(5) 5

Упражнение 3:

Номер 1

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

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

Ответ:

(1) только W

(2) только V

(3) только U

(4) W и V

(5) V и U

(6) W и U

(7) все

Номер 2

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

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

Ответ:

(1) только W

(2) только V

(3) только U

(4) W и V

(5) V и U

(6) W и U

(7) все

Номер 3

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

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

Ответ:

(1) только W

(2) только V

(3) только U

(4) W и V

(5) V и U

(6) W и U

(7) все

Упражнение 4:

Номер 1

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

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

Ответ:

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

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

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

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

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

Номер 2

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


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

Ответ:

(1) все слова, начинающиеся с a

(2) все слова из букв a , начинающиеся с aa

(3) все слова из букв a , длина которых при делении на 3 дает остаток 2

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

(5) все слова из букв a , начинающиеся с aa или aaa

Номер 3

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

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

Ответ:

(1) все слова, начинающиеся на ab и заканчивающиеся на a

(2) все слова вида (ab)ⁿaa при n=0, 1, 2, 3, …

(3) все слова вида (ab)ⁿa при n=0, 1, 2, 3, …

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

(5) все слова вида (aba)ⁿa при n= 1, 2, 3, …

Упражнение 5:

Номер 1

 Какие из следующих трех конечных автоматов
A_i = < {a,b}, {0, 1, 2, 3}, 0, F={1}, Φ_i> (i= 1, 2, 3) распознают язык L, состоящий из всех слов, которые начинаются на a и содержат четное число букв b ?

Ответ:

(1) только A₁

(2) только A₂

(3) только A₃

(4) A₁ и A₂

(5) A₁ и A₃

(6) A₂ и A₃

Номер 2

 Какие из следующих трех конечных автоматов
A_i = < {a,b}, {0, 1, 2, 3, 4}, 0, F={1}, Φ_i> (i= 1, 2, 3) распознают язык L, состоящий из всех слов, которые начинаются на b и содержат число букв a , кратное 3 ?

Ответ:

(1) только A₁

(2) только A₂

(3) только A₃

(4) A₁ и A₂

(5) A₁ и A₃

(6) A₂ и A₃

Номер 3

 Какие из следующих трех конечных автоматов
A_i = < {a,b}, {0, 1, 2, 3, 4}, 0, F={1}, Φ_i> (i= 1, 2, 3) распознают язык L, состоящий из всех слов, которые заканчиваются на b и содержат число букв a , кратное 3 ?

Ответ:

(1) только A₁

(2) только A₂

(3) только A₃

(4) A₁ и A₂

(5) A₁ и A₃

(6) A₂ и A₃

Упражнение 6:

Номер 1

 На следующем рисунке представлены диаграммы двух конечных автоматов 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={(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 >,

Ответ:

(1) C, L_C = L_A \ L_B

(2) C, L_C= L_A ∩ L_B

(3) C, L_C = L_B \ L_A

(4) D, L_D = L_A \ L_B

(5) D, L_D = L_A ∩ L_B

(6) D, L_D = L_A ∪ L_B

Номер 2

 На следующем рисунке представлены диаграммы двух конечных автоматов 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,1), (p,2)}, Φ_D >,

Ответ:

(1) C, L_C = L_A \ L_B

(2) C, L_C= L_A ∩ L_B

(3) C, L_C = L_B \ L_A

(4) D, L_D = L_A \ L_B

(5) D, L_D = L_A ∩ L_B

(6) D, L_D = L_A ∪ L_B

Номер 3

 На следующем рисунке представлены диаграммы двух конечных автоматов 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 >,

Ответ:

(1) C, L_C = L_A \ L_B

(2) C, L_C= L_A ∩ L_B

(3) C, L_C = L_B \ L_A

(4) D, L_D = L_A \ L_B

(5) D, L_D = L_A ∩ L_B

(6) D, L_D = L_A ∪ L_B

Упражнение 7:

Номер 1

 Пусть задан недетерминированный конечный автомат 
M = < {a, b}, {0, 1, 2, 3, 4 ,5}, 0, F={4, 5}, Φ> с программой
Φ: 0 b → 1, 0 → 2, 1 a → 2, 1 b → 4, 2 → 3, 2 → 5, 3 a → 4, 3 b → 2, 4 → 5
Какой из следующих НКА получится из M после применения процедуры устранения пустых переходов?

Ответ:

(1)

M1 = < {a, b}, {0, 1, 2, 4 ,5}, 0, F1={0, 2, 4, 5}, Φ1> с программой Φ1: 0 b → 1, 0 b → 2, 0 a → 4, 0 a → 5, 1 a → 2, 1 a → 5,1 b → 4, 2 a → 4, 2 b → 2

(2)

M2 = < {a, b}, {0, 1, 2, 4 }, 0, F2={0, 2, 4}, Φ2> с программой
Φ2: 0 b → 1, 0 b → 2, 0 a → 4, 1 a → 2, 1 b → 4, 2 a → 4, 2 b → 2

(3)

M3 = < {a, b}, {0, 1, 2, 3, 4 }, 0, F3={0, 2, 4}, Φ3> с программой
Φ3: 0 b → 1, 0 b → 2, 0 a → 4, 1 a → 2, 1 b → 4, 2 a → 4, 2 b → 2, 3 a → 4, 3 b → 2

(4)

M4 = < {a, b}, {0, 1, 2, 4 }, 0, F4={0, 2, 4}, Φ4> с программой
Φ4: 0 b → 1, 0 b → 2, 1 a → 2, 1 b → 4, 2 a → 4, 2 b → 2

(5) ни один из выше приведенных автоматов M1, M2, M3, M4

Номер 2

 Пусть задан недетерминированный конечный автомат 
M = < {a, b}, {0, 1, 2, 3, 4 ,5}, 0, F={4, 5}, Φ> с программой
Φ: 0 b → 1, 1 a → 2, 1 b → 3, 2 a → 3, 2 b → 1, 3 → 4, 4 a → 5, 4 → 5, 5 → 2
Какой из следующих НКА получится из M после применения процедуры устранения пустых переходов?

Ответ:

(1) M1 = < {a, b}, {0, 1, 2, 3, 4 ,5}, 0, F1={3, 4, 5}, Φ1> с программой

Φ1: 0 b → 1, 1 a → 2, 1 b → 3, 1 b → 4, 2 a → 3, 2 b → 1, 3 a → 5, 3 a → 3, 3 b → 1, 
4 a → 5, 5 a → 3, 5 b → 1

(2) M2 = < {a, b}, {0, 1, 3, 5 }, 0, F2={3, 5}, Φ2> с программой Φ2: 0 b → 1, 1 a → 2, 1 b → 3, 2 a → 3, 2 b → 1, 3 a → 5, 3 a → 3, 5 a → 3

(3) M3 = < {a, b}, {0, 1, 2, 3, 5 }, 0, F3={5}, Φ3> с программой Φ3: 0 b → 1, 1 a → 2, 1 b → 3, 2 a → 3, 2 b → 1, 3 a → 5, 3 b → 1, 5 a → 3, 5 b → 1

(4) M4 = < {a, b}, {0, 1, 2, 3, 5}, 0, F4={3, 5}, Φ4> с программой

Φ4: 0 b → 1, 1 a → 2, 1 b → 3, 2 a → 3, 2 b → 1, 3 a → 5, 3 a → 3, 3 b → 1, 5 a → 3,
5 b → 1

(5) ни один из выше приведенных автоматов M1, M2, M3, M4

Номер 3

 Пусть задан недетерминированный конечный автомат 
M = < {a, b}, {0, 1, 2, 3, 4 ,5}, 0, F={3, 5}, Φ> с программой
Φ: 0 b → 1, 0 → 2, 1 → 2, 2 → 3, 2 a → 1, 3 a → 1, 3 b → 4, 4 a → 5, 5 → 3.
Какой из следующих НКА получится из M после применения процедуры устранения пустых переходов?

Ответ:

(1) M1 = < {a, b}, {0, 1, 4 ,5}, 0, F1={0, 1, 5}, Φ1> с программой Φ1: 0 a → 1, 0 b → 1, 1 a → 1, 1 b → 4, 4 a → 5, 5 a → 1, 5 b → 4

(2) M2 = < {a, b}, {0, 1, 2, 5 }, 0, F2={1, 5}, Φ2> с программой Φ2: 0 a → 1, 0 b → 1, 0 b → 4, 1 a → 1, 1 b → 4, 4 a → 5, 5 a → 1, 5 b → 4

(3) M3 = < {a, b}, {0, 1, 4, 5 }, 0, F3={0, 1, 5}, Φ3> с программой Φ3: 0 a → 1, 0 b → 1, 0 b → 4, 1 a → 1, 1 b → 4, 4 a → 5, 5 a → 1, 5 b → 4

(4) M4 = < {a, b}, {0, 1, 3, 4, 5 }, 0, F4={0, 1, 3, 5}, Φ4> с программой Φ4: 0 a → 1, 0 b → 1, 0 b → 4, 1 a → 1, 1 b → 4, 3 a → 1, 3 b → 4, 4 a → 5, 5 a → 1, 5 b → 4

(5) ни один из выше приведенных автоматов M1, M2, M3, M4

Упражнение 8:

Номер 1

 Пусть задан недетерминированный конечный автомат 
(без пустых переходов)
M = < {0, 1}, {q, p, s}, q, F={p}, Φ> с программой
Φ: q 0 → p, q 0 → s, p 0 → q, p 0 → s, p 1 → p, s 1 → p
Какие из следующих трех ДКА эквивалентны M?

M1 = < {0, 1}, {q, p, ps, qs}, q, F1={p, ps}, Φ1> с программой
Φ1: q 0 → ps, q 1 → p, p 0 → qs, p 1 → p, ps 0 → qs, ps 1 → p, qs 0 → ps, qs 1 → p

M2 = < {0, 1}, {q, p, s, ps, qs, pq, qps, ∅}, q, F2={p, ps, pq, qps}, Φ2> с программой
Φ2: q 0 → ps, q 1 → p, p 0 → qs, p 1 → p, s 0→ ∅, s 1→ p, ps 0 → qs, ps 1 → p, qs 0 → ps, qs 1 → p, qp 0 → ps, qp 1 → p, qps 0 → qps, qps 1 → p, ∅ 0 →∅, ∅ 1 →∅.

M3 = < {0, 1}, { q, p, s, ps, qs, pq, qps, ∅}, q, F3={ p, ps, pq, qps }, Φ3> с программой
Φ3: q 0 → ps, q 1 → p, p 0 → qs, p 1 → p, s 1→ p, ps 0 → qs, ps 1 → p, qs 0 → qps, 
qs 1 →qps, qp 0 → ps, qp 1 → p, qps 0 → qps, qps 1 → p. ∅ 0 →∅, ∅ 1 → ∅

Ответ:

(1) только M1

(2) только M2

(3) только M3

(4) M1 и M2

(5) M1 и M3

(6) M2 и M3

(7) ни один

Номер 2

 Пусть задан недетерминированный конечный автомат 
(без пустых переходов)
M = < {0, 1}, {q, p, s}, q, F={p}, Φ> с программой
Φ: q 0 → p, q 0 → s, q 1→ q, p 0 → q, p 0 → p, s 1 → q, s 1 → p
Какие из следующих трех ДКА эквивалентны M?

M1 = < {0, 1}, {q, ps, pq, pqs}, q, F1={ ps, pq, pqs }, Φ1> с программой Φ1:
q 0 → ps, q 1 → q, ps 0 → pq, ps 1 → pq, pq 0 → pqs, pq 1 → q, pqs 0 → pqs, pqs 1 → pq

M2 = < {0, 1}, {q, p, s, ps, qs, pq, qps, ∅}, q, F2={p, ps, pq, pqs }, Φ2> с программой Φ2:
q 0 → ps, q 1 → q, p 0 → pq, p 1 → q, ps 0 → qs, ps 1 → pq, pq 0 → pqs, pq 1 → q, 
qs 0 → ps, qs 1 →q, pqs 0 → pqs, pqs 1 → pq, ∅ 0 →∅, ∅ 1 →∅

M3 = < {0, 1}, { q, p, s, ps, qs, pq, qps, ∅}, q, F3={ p, ps, pq, pqs }, Φ3> с программой Φ3:
q 0 → ps, q 1 → q, p 0 → pq, p 1 → q, s 0 →∅, s 1 →pq, ps 0 → pq, ps 1 → pq, pq 0 → pqs, pq 1 → q, qs 0 → ps, qs 1 →q, pqs 0 → pqs, pqs 1 → pq, ∅ 0 →∅, ∅ 1 →∅

Ответ:

(1) только M1

(2) только M2

(3) только M3

(4) M1 и M2

(5) M1 и M3

(6) M2 и M3

(7) ни один

Номер 3

 Пусть задан недетерминированный конечный автомат 
(без пустых переходов)
M = < {0, 1}, {q, p, s}, q, F={p}, Φ> с программой
Φ: q 0 → q, q 1 → s, q 1→ p, p 0 → q, p 0 → p, s 0 → q, s 1 → p
Какие из следующих трех ДКА эквивалентны M?

M1 = < {0, 1}, {q, p, s, ps, qs, pq, qps, ∅}, q, F1={p, ps, pq, pqs }, Φ1> с программой Φ1:
q 0 → q, q 1 → ps, p 0 → pq, p 1 → ∅, s 0 → q, s 1 → pq, ps 0 → pq, ps 1 → p, pq 0 → pq, pq 1 → p, qs 0 → q, qs 1 →pq, pqs 0 → pq, pqs 1 → ps, ∅ 0 →∅, ∅ 1 →∅

M2 = < {0, 1}, { q, p, s, ps, qs, pq, qps, ∅}, q, F2={ p, ps, pq, pqs }, Φ2> с программой Φ2:
q 0 → q, q 1 → ps, p 0 → pq, p 1 → q, s 0 → q, s 1 → pq, ps 0 → pq, ps 1 → p, pq 0 → pq, pq 1 → ps, qs 0 → q, qs 1 →pq, pqs 0 → pq, pqs 1 → ps, ∅ 0 →∅, ∅ 1 →∅

M3 = < {0, 1}, {q, p, ps, pq, ∅ }, q, F3={ ps, pq, p }, Φ3> с программой Φ3:
q 0 → q, q 1 → ps, ps 0 → pq, ps 1 → p, pq 0 → pq, pq 1 → ps, p 0 → pq, p 1 → ∅, ∅ 0 →∅, ∅ 1 →∅

Ответ:

(1) только M1

(2) только M2

(3) только M3

(4) M1 и M2

(5) M1 и M3

(6) M2 и M3

(7) ни один

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