2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 ДКА с маленькой деталью
Сообщение19.09.2015, 06:20 
Заслуженный участник


27/04/09
28128
Как-то давно мне пригодилось такое маленькое обобщение ДКА — кроме переходов по символу из каждого состояния допускалось до одного перехода по пустой строке, который делался (обязательно), если никакой переход по символу не получился; автомат остаётся детерминированным при понятно каких условиях. Наверняка такие автоматы где-то уже описаны и названы. Подскажите, кто знает.

P. S. Переход по пустой строке, конечно, не должен сопровождаться и никакими выходными символами, если автомат их выдаёт.

-- Сб сен 19, 2015 08:27:11 --

А, вот у Хопкрофта и др. во «Введении в теорию языков и вычислений» НКА с ε-переходами ($\varepsilon$ здесь обозначение пустой строки) называются просто ε-НКА. По аналогии мои автоматы можно звать ε-ДКА, видимо. Но всё равно от комментариев не откажусь.

 Профиль  
                  
 
 Re: ДКА с маленькой деталью
Сообщение19.09.2015, 07:00 
Заслуженный участник


16/02/13
4105
Владивосток
Ну, помнится, все НКА эквивалентны стандартным ДКА. Ваши, как мне кажется, посредством их (НДКА) вполне реализуются. Так что для практических целей могут быть удобнее, но каких-то принципиальных теоретических последствий не должны бы нести, не?

 Профиль  
                  
 
 Re: ДКА с маленькой деталью
Сообщение19.09.2015, 11:40 
Заслуженный участник


27/04/09
28128
Да, всё реализуется, и даже ДКА — это одновременно и частный случай НКА. А ε-ДКА мог бы быть так же частным случаем ε-НКА, но нет: мы не можем пойти куда-то параллельно из состояния 2, в которое попали по ε-переходу из состояния 1, и самого 1 — в результате получится несогласие с описанием, т. к. мы в моём случае никогда не перейдём из 2 по символам, по которым можем перейти из 1. (Чувствую, проще было бы нарисовать картинку, чем сейчас городить этот словесный огород, но пока немного лень. Надеюсь, не слишком непонятно получилось.)

Из ε-ДКА эквивалентный ДКА мы, конечно, как и из [ε-]НКА, получить можем, и даже ещё проще, чем с [ε-]НКА; это просто самое простое сокращение некоторых ДКА, которое приходит в голову. Так что принципиальных теоретических последствий я тоже не вижу. :-) Но, как показано выше в этом посте, ДКА : НКА ≠ ε-ДКА : ε-НКА, так что мне не нравится название, которое я здесь сам и дал, и хотелось бы чего-то получше.

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

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



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

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


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

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