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

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

Номер 1

Какой язык L является конкатенацией двух языков:
L1= {a, ab, abba} и L2= { ε, a, b, ba}?

Ответ:

(1) L = {a, ab, abba, aa, aab, aba, abbaa, abb, abbab, abbaba}

(2) L = {a, ab, abba, aa, aba, abbaa, abb, abbab, abbaba}

(3) L = {aa, aba, abbaa, ab, abb, abbab, abbaba}

(4) L = {aa, aba, abbaa, ab, abb, abbab, abbaba}

(5) L = {aa, aba, abbaa, ab, abb, abbab, abbaba}

Номер 2

Какой язык L является конкатенацией двух языков:
L1= {ε, b, ab, abba} и L2= { a, b, ba}?

Ответ:

(1) L = {a, b, ba, bb, ab, abba, aab, aba, abbaa, abb, abbab, abbaba}

(2) L = {a, ab, abba, aa, aba, abbaa, abb, abbab, abbaba}

(3) L = {ε, bb, ba, aba, abbaa, ab, abb, abbab, abbaba}

(4) L = {a, b, ba, bb, bba, aba, abb, abbab, abbaa, abbaba}

(5) L = {a, b, ba, bb, bba, aba, abbaa, ab, abb, abbab, abbaba}

Номер 3

Какой язык L является конкатенацией двух языков:
L1= {ε, b, ab, ba} и L2= {ε, a, b, ba}?

Ответ:

(1) L = {ε, a, b, ba, bb, ab, bab, aba, abba, abb, abba, abbb}

(2) L = {a, ab, abba, aa, aba, abbaa, abb, abbab, abbaba}

(3) L = {ε, a, b, ba, bb, bba, ab, aba, abba , baa, bab, baba}

(4) L = {a, b, ba, bb, bba, aba, abb, abba, abba, abab}

(5) L = {ε, a, b, ba, bb, bba, aba, abbaa, ab, abb, abbab, abbaba}

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

Номер 1

Пусть S={aaa, aab, aba, abb, baa, bab, bba, bbb}  Какая из следующих фраз описывает итерацию S*  этого языка?

Ответ:

(1) все слова в алфавите {a, b} длины не меньше 3 и пустое слово

(2) все слова над {a, b}, которые начинаются и кончаются одним и тем же символом

(3) все слова четной длины, состоящие из символов {a, b}

(4) все слова над {a, b} , длина которых делится на 3, включая слово длины 0

(5) все слова длины не меньше 24, состоящие из символов {a, b}

Номер 2

Пусть S={aa, ab, ba, bb}  Какая из следующих фраз описывает итерацию S*  этого языка?

Ответ:

(1) все слова в алфавите {a, b} длины не меньше 2 и пустое слово

(2) все слова над {a, b}, которые начинаются и кончаются одним и тем же символом

(3) все слова нечетной длины, состоящие из символов {a, b}

(4) Ответ 4. Все слова длины не меньше 8, состоящие из символов {a, b}

(5) все слова над {a, b} , длина которых делится на 2, включая слово длины 0

Номер 3

Пусть S={aaa, aba, baa, bba}  Какая из следующих фраз описывает итерацию S*  этого языка?

Ответ:

(1) все слова над {a, b} , длина которых делится на 3 и каждая третья буква есть a , и слово длины 0

(2) все слова в алфавите {a, b} длины не меньше 3, которые заканчиваются на a, и пустое слово

(3) все слова над {a, b}, длина которых делится на 3 и которые заканчиваются на a

(4) все слова четной длины, состоящие из символов {a, b} , которые заканчиваются на a

(5) все слова длины не меньше 12, состоящие из символов {a, b}

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

Номер 1

Какое из следующих регулярных выражений задает все слова из 0-ей и 1-иц, в которых есть по крайней мере две подряд идущие 1-цы ?

Ответ:

(1) (0 + 10)*11(10 +0)*

(2) (0 +10)*11(0 +1)*

(3) (0 + 1)*10*1(0+1)*

(4) 0*11(0 + 10)*(0+1)*

(5) (0 +11)*

Номер 2

Какое из следующих регулярных выражений задает все слова из 0-ей и 1-иц, в которых есть по крайней мере два подряд идущих 0 ?

Ответ:

(1) (1 + 01)*00(01 +1)*

(2) (1 +00)*

(3) (0 + 1)*10*1(0+1)*

(4) 1*00(0 + 10)*(0+1)*

(5) (1 +01)*00(0 +1)*

Номер 3

Какое из следующих регулярных выражений задает все слова из 0-ей и 1-иц, в которых нет двух подряд идущих 0 ?

Ответ:

(1) (1 + 01)* (ε + 0)

(2) (1*01*)*

(3) (01 )*1*01*

(4) 1*01(1 + 01)*( ε + 0)

(5) (1 +01)*(0 +1)

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

Номер 1

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

Ответ:

(1) a(ba)*

(2) a*(ba)*

(3) a*ba

(4) подходит и 1, и 2

(5) для этого языка существует только одно регулярное выражение

Номер 2

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

Ответ:

(1) a(ba)*

(2) (ba)*b

(3) b*ab*

(4) подходит и 1, и 2

(5) для этого языка существует только одно регулярное выражение

Номер 3

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

Ответ:

(1) (b*+a)*

(2) (a +b)*

(3) b*ab*

(4) подходит и 1, и 2

(5) для этого языка существует только одно регулярное выражение

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

Номер 1

Заданы два НКА:
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}, Φ₃>, где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода).

Ответ:

(1) только C₁

(2) только C₂

(3) только C₃

(4) C₁ и C₂

(5) C₁ и C₃

(6) C₂ и C₃

(7) все

Номер 2

Заданы два НКА:
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}, Φ₃>, где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода).

Ответ:

(1) только C₁

(2) только C₂

(3) только C₃

(4) C₁ и C₂

(5) C₁ и C₃

(6) C₂ и C₃

(7) все

Номер 3

Заданы два НКА:
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}, Φ₃> , где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода).

Ответ:

(1) только C₁

(2) только C₂

(3) только C₃

(4) C₁ и C₂

(5) C₁ и C₃

(6) C₂ и C₃

(7) все

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

Номер 1

Какие из следующих трех автоматов С₁ , С₂ , С₃  распознают язык, представляемый регулярным выражением (00 + 1)*1?

С₁ = < {0,1}, {q, p, r, s, t}, q, F₁={ t }, Φ₁> ,
С₂ = < {0,1}, {q, p, r, s }, q, F₂={ s}, Φ₂> ,
С₃ = < {0,1}, {q, p, r, s, t}, q, F₃={ s}, Φ₃> ,
 где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода).

Ответ:

(1) только C₁

(2) только C₂

(3) только C₃

(4) C₁ и C₂

(5) C₁ и C₃

(6) C₂ и C₃

(7) все

Номер 2

Какие из следующих трех автоматов С₁ , С₂ , С₃  распознают язык, представляемый регулярным выражением 1 (01)*?
С₁ = < {0,1}, {q, p, r, s, t}, q, F₁={ t }, Φ₁>,
С₂ = < {0,1}, {q, p, r, s }, q, F₂={p, s}, Φ₂>,
С₃ = < {0,1}, {q, p, r, s, t}, q, F₃={ p, s}, Φ₃>, 
где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода).

Ответ:

(1) только C₁

(2) только C₂

(3) только C₃

(4) C₁ и C₂

(5) C₁ и C₃

(6) C₂ и C₃

(7) все

Номер 3

Какие из следующих трех автоматов С₁ , С₂ , С₃  распознают язык, представляемый регулярным выражением 0(10 +1)*?

С₁ = < {0,1}, {q, p, r, s, t}, q, F₁={ t }, Φ₁>,
С₂ = < {0,1}, {q, p, r, s }, q, F₂={p, r}, Φ₂>,
С₃ = < {0,1}, {q, p, r, s, t}, q, F₃={ p, r, s}, Φ₃>,
 где программы заданы в следующих таблицах (∅ означает отсутствие соответствующего перехода).

Ответ:

(1) только C₁

(2) только C₂

(3) только C₃

(4) C₁ и C₂

(5) C₁ и C₃

(6) C₂ и C₃

(7) все

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