Семейство детерминированных конечных автоматов степени n над алфавитом Σ с N ∩ Σ = ∅ состоит из множества M = {(Ki, Σ ∪ {1, ..., n}, δi, si,Fi): 1 ≤ i ≤ n} детерминированных конечных автоматов.Мы неявно фиксируем индексную функцию над M, чтобы мы могли ссылаться на «i-й автомат Mi = (Ki, Σ ∪ {1, ..., n}, δi, si, Fi) из M.»Семейство выполняет следующую обработку:
При заданном входе w ∈ Σ ∗ автомат M1 начинает обрабатывать ввод как обычно, следуя переходам в δ1, пока не достигнет перехода вида δ1 (q, i)= p, где i ∈ {1,.,,, n}.Затем он дает управление автомату Mi.Автомат Mi обрабатывает еще не использованный ввод, пока не достигнет конечного состояния.Когда такое состояние достигнуто, Mi завершается и возвращает управление M1, который возобновляет свою работу из состояния p.M1 принимает ввод, если он находится в конечном состоянии, когда достигнут конец ввода.
В более общем случае любой автомат Mi может «вызвать» какой-либо другой автомат Mj, что происходит всякий раз, когда Mi выполняет переход формыδi (q, j) = p.Когда такое случается, Mi дает контроль над Mj.Когда операция Mj достигает конечного состояния, Mi возвращает управление и возобновляет свою работу, начиная с состояния p.
Назовите всю систему детерминированным конечным автоматом с рекурсивными вызовами.На самом деле это обычный конечный автомат с добавленной функциональностью, что некоторые ребра представляют вызов другого автомата вместо принятия одного входного символа.
Показать, что любой язык, принятыйдетерминированный конечный автомат с рекурсивными вызовами не зависит от контекста.
Являются ли все языки, принятые детерминированными конечными автоматами с рекурсивными вызовами, детерминированным контекстом свободными?Обоснуйте свой ответ.