Тема 8. Рекуррентные уравнения

Эксперименты с автоматами

Эксперимент с автоматами — это способ получений информации о внутренней структуре автоматов по их поведению. Основная задача экспериментов — получить сведения о строении автомата путем наблюдения его реакции на внешние воздействия.

Рассмотрим автоматы, в которых не выделены начальные состояния. В этом случае автомат задается пятеркой (A,S,B,φ,). Множество всех конечных слов в алфавите обозначается. Пусть автомат (A,S,B,φ,) находится в состоянии и на вход подаётся слово. Тогда на выходе будет некоторое слово и после подачи всего слова автомат оказывается в состоянии. Раcширяя функции и, положим.

Определение 1. Два состояния и автомата (A,S,B,φ,) называются отличимыми, если существует входное слово такое, что. При этом слово называется экспериментом, отличающим от. Длину слова I () называют длиной эксперимента.

Теорема (Мура). Если в автомате состояния и отличимы и, то существует эксперимент, отличающий и, длина которого.

8.1. Определение рекуррентного уравнения/ Решение линейного однородного рекуррентного уравнения

Рекуррентным соотношением (уравнением, рекуррентной формулой) называется соотношение вида

,

которое позволяет вычислить все члены последовательности a₀, a_{1 ,} a₂,.., если заданы её первые k членов.

k – порядок рекуррентного уравнения.

Примеры. 1) a_n+1 = a_n + d -–арифметическая прогрессия.

2) a_n+1 = q ∙ a_n -–геометрическая прогрессия.

3) a_n+2 = a_n + a_n+1 -–последовательность чисел Фибоначчи.

В случае, когда рекуррентное уравнение линейно и однородно, то есть выполняется соотношение вида

Последовательность a₀, a_{1 ,} a₂,.., удовлетворяющая данному уравнению называется возвратной.

Многочлен

называется характеристическим многочленом для возвратной последовательности.

Корни этого многочлена называются характеристическими. Множество всех последовательностей, удовлетворяющих рекуррентному уравнению (1) называется его общим решением.

Общее решение однородного линейного рекуррентного уравнения имеет аналогию с решением линейного дифференциального уравнения. А именно, справедливы теоремы.

Теорема 1. Пусть - корень характеристического многочлена (2), тогда последовательность, где c – производная константа, удовлетворяет уравнению (1).

Теорема 2. Если - простые корни характеристического многочлена (2), то общее решение рекуррентного уравнения (1) имеет вид:

,

где c₁, c₂,.., c_k – произвольные константы.

Теорема 3. Если - корень кратности (i = 1,2,.., s) характеристического многочлена (2), то общее решение рекуррентного уравнения (1) имеет вид:

где c_ij – произвольные константы.

Зная общее решение рекуррентного уравнения (1), по начальным условиям a₀, a₁,.., a_k-1, можно найти неопределенные постоянные c_ij, и, тем самым, получить частное уравнении (1) с данными начальными условиями.

Пример. Найти последовательность { a_n }, удовлетворяющую рекуррентному уравнению

Характеристический многочлен

Дата добавления: 2014-01-11