Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Эквивалентность двухсчётчиковой машины трёхсчётчиковой)
м (Эквивалентность двухстековой машины трёхсчётчикой машине)
Строка 22: Строка 22:
  
 
Будем использовать два счётчика для хранения состояний двух стеков, а третий счетчик будем использовать для временных вычислений. Для стека существует три типа элементарных операций: положить символ в стек, снять символ со стека, проверить верхний символ стека. Рассмотрим реализацию этих операция на трёхсчётчиковой машине.
 
Будем использовать два счётчика для хранения состояний двух стеков, а третий счетчик будем использовать для временных вычислений. Для стека существует три типа элементарных операций: положить символ в стек, снять символ со стека, проверить верхний символ стека. Рассмотрим реализацию этих операция на трёхсчётчиковой машине.
*Снять символ со стека. Для того, чтобы снять символ необходимо разделить число, которым представлен стек, на <tex>P</tex>, отбросив остаток. Пусть снимается символ с первого стека. Тогда обнулим третий счётчик. Будем уменьшать первый счётчик на <tex>P</tex>, и, если это удалось сделать, третий увеличивать на один. Эти действия будем повторять, пока первый счётчик не равен нулю. Затем скопируем значение с третьего счётчика на первый: пока третий счётчик не равен нулю, уменьшаем третий счётчик и увеличиваем первый.  
+
*'''Снять символ со стека'''. Для того, чтобы снять символ необходимо разделить число, которым представлен стек, на <tex>P</tex>, отбросив остаток. Пусть снимается символ с первого стека. Тогда обнулим третий счётчик. Будем уменьшать первый счётчик на <tex>P</tex>, и, если это удалось сделать, третий увеличивать на один. Эти действия будем повторять, пока первый счётчик не равен нулю. Затем скопируем значение с третьего счётчика на первый: пока третий счётчик не равен нулю, уменьшаем третий счётчик и увеличиваем первый.  
*Добавить символ в стек. Для того, чтобы снять символ необходимо умножить число, которым представлен стек, на <tex>P</tex> и прибавить к нему номер символа, который добавляется на стек.  Пусть снимается символ с первого стека. Тогда обнулим третий счётчик. Будем уменьшать первый счётчик на один и увеличивать третий на <tex>P</tex>. Эти действия будем повторять, пока первый счётчик не равен нулю. Затем скопируем значение с третьего счётчика на первый.  
+
*'''Добавить символ в стек'''. Для того, чтобы снять символ необходимо умножить число, которым представлен стек, на <tex>P</tex> и прибавить к нему номер символа, который добавляется на стек.  Пусть снимается символ с первого стека. Тогда обнулим третий счётчик. Будем уменьшать первый счётчик на один и увеличивать третий на <tex>P</tex>. Эти действия будем повторять, пока первый счётчик не равен нулю. Затем скопируем значение с третьего счётчика на первый.  
* Проверка верхнего символа стека. Для этого необходимо найти остаток от деления на <tex>P</tex>. Скопируем значение первого счётчика на третий. Реализуем при помощи введения дополнительных автоматов, входящих в управляющий автомат трехсчётчиковой машины. Этот автомат должен состоять из <tex>P</tex> состояний. Каждое состояние соответствует определенному остатку от деления. В случае, если третий счётчик не нуль, автомат осуществляет переход в состояние, соответствующее следующему остатку от деления. Если третий счётчик нуль, то остаток найдени осуществляется переход в управляющем автомате, соответствующий от деления. Будем уменьшать третий счетчик, каждый раз переходя в следующее состояние автомата.
+
* '''Проверка верхнего символа стека'''. Для этого необходимо найти остаток от деления на <tex>P</tex>. Скопируем значение первого счётчика на третий. Реализуем при помощи введения дополнительных автоматов, входящих в управляющий автомат трехсчётчиковой машины. Этот автомат должен состоять из <tex>P</tex> состояний. Каждое состояние соответствует определенному остатку от деления. В случае, если третий счётчик не нуль, автомат осуществляет переход в состояние, соответствующее следующему остатку от деления. Если третий счётчик нуль, то остаток найдени осуществляется переход в управляющем автомате, соответствующий от деления. Будем уменьшать третий счетчик, каждый раз переходя в следующее состояние автомата.
  
 
<tex>\Leftarrow</tex>
 
<tex>\Leftarrow</tex>

Версия 04:14, 24 января 2012

Счётчиковые машины

Определение:
[math]k[/math]-счётчиковой машиной называется набор [math]A=\langle\Sigma, Q, s\in Q, T \subset Q, \delta : Q \times \Sigma \cup \{\varepsilon\} \times \{0,1\}^k \rightarrow Q \times \{ -1, 0, 1\}^k \rangle[/math], где
  • [math]\Sigma[/math] — входной алфавит на ленте;
  • [math]Q[/math] — множество состояний автомата;
  • [math]s[/math] — стартовое состояние автомата;
  • [math]T[/math] — множество допускающих состояний автомата;
  • [math]\delta[/math] — функция переходов, зависящая от символа на ленте, текущего состояния управляющего автомата и состояния счётчиков и осуществляющая переход в автомата в новое состояние и изменение состояния счётчиков.

Для каждого счётчика возможны четыре операции: увеличить на один, уменьшить на один, не изменять значение, проверить является ли значение счетчика нулём.

Будем считать, что значение нулевых счётчиков уменьшать нельзя.

По сути, [math]k[/math]-счётчиковая машина является [math]k[/math]-стековой машиной с односимвольным алфавитом.

Эквивалентность двухстековой машины трёхсчётчикой машине

Лемма:
Язык [math]L[/math] допускается двухстековой машиной тогда и только тогда, когда он допускается трёхсчётчиковой машиной.
Доказательство:
[math]\triangleright[/math]

[math]\Rightarrow[/math]

Для доказательства необходимо показать, что двухстековая машина имитируется на трёхсчётчиковой. Пусть [math]\Pi[/math] - стековый алфавит, [math]|\Pi|=P[/math]. Пронумеруем символы алфавита от [math]0[/math] до [math]P[/math]. Тогда стек можно рассматривать как целое число в системе счисления с основанием [math]P[/math].

Будем использовать два счётчика для хранения состояний двух стеков, а третий счетчик будем использовать для временных вычислений. Для стека существует три типа элементарных операций: положить символ в стек, снять символ со стека, проверить верхний символ стека. Рассмотрим реализацию этих операция на трёхсчётчиковой машине.

  • Снять символ со стека. Для того, чтобы снять символ необходимо разделить число, которым представлен стек, на [math]P[/math], отбросив остаток. Пусть снимается символ с первого стека. Тогда обнулим третий счётчик. Будем уменьшать первый счётчик на [math]P[/math], и, если это удалось сделать, третий увеличивать на один. Эти действия будем повторять, пока первый счётчик не равен нулю. Затем скопируем значение с третьего счётчика на первый: пока третий счётчик не равен нулю, уменьшаем третий счётчик и увеличиваем первый.
  • Добавить символ в стек. Для того, чтобы снять символ необходимо умножить число, которым представлен стек, на [math]P[/math] и прибавить к нему номер символа, который добавляется на стек. Пусть снимается символ с первого стека. Тогда обнулим третий счётчик. Будем уменьшать первый счётчик на один и увеличивать третий на [math]P[/math]. Эти действия будем повторять, пока первый счётчик не равен нулю. Затем скопируем значение с третьего счётчика на первый.
  • Проверка верхнего символа стека. Для этого необходимо найти остаток от деления на [math]P[/math]. Скопируем значение первого счётчика на третий. Реализуем при помощи введения дополнительных автоматов, входящих в управляющий автомат трехсчётчиковой машины. Этот автомат должен состоять из [math]P[/math] состояний. Каждое состояние соответствует определенному остатку от деления. В случае, если третий счётчик не нуль, автомат осуществляет переход в состояние, соответствующее следующему остатку от деления. Если третий счётчик нуль, то остаток найдени осуществляется переход в управляющем автомате, соответствующий от деления. Будем уменьшать третий счетчик, каждый раз переходя в следующее состояние автомата.

[math]\Leftarrow[/math]

Трёхсчётчиковая машина является частным случаем трёхстековой машины, а любая [math]k[/math]-стековая машина эквивалента по вычислительной мощности двухстековой, следовательно, любой язык, допускаемый трёхсчётчиковой машиной, допускается двухстековой.
[math]\triangleleft[/math]

Эквивалентность двухсчётчиковой машины трёхсчётчиковой

Лемма:
Для любого [math]k[/math] и для любой [math]k[/math]-счётчиковой машины существует эквивалентная ей двухсчётчиковая машина.
Доказательство:
[math]\triangleright[/math]

Для доказательства покажем, как имитировать [math]k[/math]-счётчиковую машины на двухсчётчиковой. Пусть [math]C_1, C_2, ..., C_k[/math] — значения счётчиков [math]k[/math]-счётчиковой машины. Тогда состояние [math]k[/math]-счётчиковой машины можно охарактеризовать одним числом [math]2^{C_1}*3^{C_2}*...*p_k^{C_k}[/math], где [math]p_k[/math][math]k[/math]-е простое число. Тогда любое состояние k-счётчиковой машины можно хранить на одном счётчике, и использовать второй счётчик для временных вычислений.

Тогда элементарные операции на [math]k[/math]-счётчиковой машине реализуются следующим образом.

  • Увеличить [math]i[/math]-й счётчик. Для этого необходимо умножить значение счётчика на [math]p_i[/math].
  • Уменьшить [math]i[/math]-й счётчик. Для этого необходимо поделить значение счётчика на [math]p_i[/math].
  • Сравнить с нулём значение [math]i[/math]-го счётчика. Для этого необходимо найти остаток от деления значения счётчика на [math]p_i[/math] и сравнить его с нулём.

Операции умножения деления и нахождения остатка при помощи двух счётчиков описаны в предыдущей лемме.

Таким образом, для любого [math]k[/math] и для любой [math]k[/math]-счётчиковой машины существует эквивалентная ей двухсчётчиковая машина.
[math]\triangleleft[/math]

Эквивалентность двухсчётчиковой машины МТ

Теорема:
Для любого перечислимого языка [math]L[/math] существует двухсчётчиковая машина, которая распознает этот язык.
Доказательство:
[math]\triangleright[/math]
Утверждение теоремы очевидно следует из двух описанных выше лемм, эквивалентности двухстековой машины машине Тьюринга и тезиса Тьюринга-Черча.
[math]\triangleleft[/math]

Источники

  • Хопкрофт Д., Мотвани Р., Ульман Д.Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)