03.12.2012, 06:16
общий
это ответ
Здравствуйте, Aleksandrkib!
а) автомат существует
[table]
[row][col] [/col][col] q1[/col][col] q2[/col][col]q3 [/col][col]q4 [/col][/row]
[row][col] 1[/col][col] q2[/col][col]q2 [/col][col] q4(K)[/col][col]q4(K) [/col][/row]
[row][col] 2[/col][col] q3[/col][col] q2[/col][col] q3[/col][col]q3 [/col][/row]
[/table]
б) язык является объединением полученного в пункте а с аналогичным (слова, начинающиеся на 1 и кончающиеся на 2), поэтому распознаваем
[table]
[row][col] [/col][col] q1[/col][col] q2[/col][col]q3 [/col][col]q4 [/col][col]q5 [/col][/row]
[row][col] 1[/col][col] q2[/col][col]q2 [/col][col] q4(K)[/col][col]q4(K) [/col][col]q2 [/col][/row]
[row][col] 2[/col][col] q3[/col][col] q5(K)[/col][col] q3[/col][col]q3 [/col][col]q5(K) [/col][/row]
[/table]
в) не распознаваемый язык. Грамматика, определяющая этот язык, не регулярна.