2014 dxdy logo

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

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




На страницу Пред.  1, 2
 
 Re: Отношение конгруэнции на языках
Сообщение05.12.2011, 01:05 
2КА называется конечный автомат $A=(Q, \Sigma, \delta, q_0, F)$ где $\delta: Q\times Q \rightarrow Q\times (-1, 0, 1)$, остальное - как в обычном КА. На входном слове, на каждом шаге работы, если получаем -1 сдвигаемся на одну букву влево по слову, если 0 - остаемся на месте, если 1 - сдвигаемся вправо.

Для каждого состояния $q$ определим множество $M(q, x)=\{w: (q,x)\in \delta^{*}(q_0, w)\}$ - множество слов, принимая которые автомат останавливается в состоянии q и при этом на последнем шаге сдвигается по слову, соответствуя x. Верно ли, что если $x\sim_{L} y \Leftrightarrow M(q, x)=M(q,y)$, где $L$ - язык, принимаемый 2КА?

 
 
 [ Сообщений: 16 ]  На страницу Пред.  1, 2


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group