2014 dxdy logo

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

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


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Теория абстрактных автоматов
Сообщение26.05.2023, 11:24 


23/02/18
11
Задача.
Покажите, что для отображений $z$ и $h$,
заданных равенствами $z(p)=pp$ (удвоение слова $p$); $h(p) = p'$ , $p'$ где получено из $p$ изъятием всех вхождений некоторой буквы входного алфавита, существует более экономная процедура выравнивания длины слов, чем стандартное выравнивание длины слов?

Попытка решения:
Для этого мы можем использовать следующую процедуру:
Пусть $w_1$ и $w_2$ - слова из языков $L_1$ и $L_2$ соответственно.
Применим отображение $h$ к каждому слову, чтобы получить новые слова $h(w_1)$
и $h(w_2)$ . Вычислим длину максимального общего префикса $p$ между $h(w_1)$ и $h(w_2)$ . Затем мы можем использовать отображение $z$ для удвоения префикса $p$ и получения новых слов $z^{|p|}(h(w_1))$ . и $z^{|p|}(h(w_2))$. После этого мы можем сравнить длины новых слов и выбрать то, которое короче. Эта процедура экономнее, чем стандартное выравнивание длины слов, потому что она не требует добавления дополнительных символов в конец слов, что может привести к увеличению размера языка. Вместо этого она использует отображения $h$ и$z$ , чтобы
выровнять длины слов без добавления дополнительных символов.

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

Модераторы: Модераторы Математики, Супермодераторы



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

Сейчас этот форум просматривают: Alex Krylov


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

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