Конечные автоматы и тупики

Question

Это моя проблема

Я знаю следы двух конечных автоматов, которые свободны от тупиков.

Я хочу знать с помощью трассировок (я не знаю структуры), если композиция тупиковаябесплатно.

Любая теорема, чтобы узнать, это можно узнать?

Answer 1

Если вы действительно имеете дело с композицией (запустите машину A с начальными параметрами, а затем машину B, используя конечные параметры A в качестве начальных параметров), то тупик в композиции обязательно произойдет либо в A, либо в B.

Это не может произойти в A (потому что тогда это также произойдет, если B не присутствует), и это не может произойти в B (потому что тогда это также произойдет, если A не было, и вы использовали те же исходные параметры дляБ).Таким образом, исходя из первоначальных предположений о том, что A и B не имеют тупиков, так же как и их состав.