2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 доказать, ято язык принадлежит классу TIME(n log(n))
Сообщение22.12.2010, 23:53 
Аватара пользователя


27/04/10
71
Нижний Новгород
Есть язык $L^{a-b}=\{a^kb^k\}$ Требуется доказать, что он принадлежит классу TIME(n log(n)), т.е. существует машина Тьюринга, разрешивающая этот язык за время, не превышающее const*n *log(n), где n-длина входного слова. Причём доказывать тот факт, что не существует лучшего времени выполнения не нужно. Ну по сути надо описать МТ, которая будет разрешивать этот язык, за время n*log(n).
Мне известно, что можно построить такую МТ, которая будет разрешивать данный язык за $o(n^2)$ следующим образом: после первого прохода по слову проверяем его структура, т.е. сначало идёт некоторое количество букв a, потом некоторое количество букв b. Если слова имеет такой вид, то стираем первую букву a, идём по слову до последней буквы b, которую тоже стираем, и так пока не кончится один из видов букв, после чего сделаем вывод о принадлежности слова языку. Ну достаточно понятно, что сложность данного алгоритма будет $o(n^2)$.
Первое что приходит в голову - модифицировать этот алгоритм следующим способом: стирать не по 1 букве, а по несколько, но тогда порядок сложности не изменится.
Поскольку в ответе в сложности есть логарифм. то мне показалось, что это можно сделать путём двоичного поиска нужных букв, но вроде его в МТ нельзя реализовать за логарифмическое время, в связи с ограниченностью алфавитов и количества состояний автомата.
Как можно модифицировать данный алгоритм, либо какой другой алгоритм сможет удовлетворять условиям?
P.S. естественно, имеется ввиду, что мы должны построить одноголовочную недетерминированную МТ.

 Профиль  
                  
 
 Re: доказать, ято язык принадлежит классу TIME(n log(n))
Сообщение23.12.2010, 02:13 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Возможно Вы имели ввиду одноленточную ДМТ?

Попробуйте подсчитать количество букв $a$ для чего потребуется $k$ раз выполнит инкремент, каждый потребует не более чем $c\cdot \log k$ операций.

 Профиль  
                  
 
 Re: доказать, ято язык принадлежит классу TIME(n log(n))
Сообщение23.12.2010, 03:13 
Заслуженный участник
Аватара пользователя


06/10/08
6422
Алгоритм простой - на каждом из примерно $\log n$ шагов каждую вторую букву стираем попутно замечая, четное кол-во букв или нечетное, а когда дошли до конца, сравниваем эти четности у $a$ и $b$ (это будут двоичные цифры в количестве букв).

 Профиль  
                  
 
 Re: доказать, ято язык принадлежит классу TIME(n log(n))
Сообщение23.12.2010, 09:46 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Алгоритм предложенный Xaositect лучше моего, и реализовать его проще.

 Профиль  
                  
 
 Re: доказать, ято язык принадлежит классу TIME(n log(n))
Сообщение23.12.2010, 22:16 
Аватара пользователя


27/04/10
71
Нижний Новгород
Действительно, получилось сделать как написал Xaositect. Спасибо)

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group