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 сообщение ] 

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



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

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


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

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