2014 dxdy logo

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

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




 
 Как построить ДМП-преобразователь?
Сообщение09.12.2010, 18:31 
Построить ДМП преобразователь осуществляющий перевод цепочки из множества $\{1^m 0^n, m,n>0, m\neq n\}$ в цепочку вида $1^{m-n} $ , если $m>n$ или в цепочку $1^{n-m} $ , если $n>m$.
Для того что бы его построить нужно сначала, построить СУ-схему, потом транслирующую грамматику и уже по ней ДМП. Но для этого нужно сначала построить саму грамматику, определяющую этот язык, что собственно и не получается, никак не могу выполнить условие $m\neq n$. Может кто помочь разобраться?

 
 
 
 Re: Как построить ДМП-преобразователь?
Сообщение09.12.2010, 19:07 
Можно, наверное, как-то так:
$S \to P~|~ Q$
$P \to 1 ~|~ 1P~ |~ 1P0$
$Q \to 0 ~|~ Q0 ~|~ 1Q0$

 
 
 
 Re: Как построить ДМП-преобразователь?
Сообщение09.12.2010, 19:14 
Спасибо огромное! :-) Пошла разбираться дальше...

 
 
 
 Re: Как построить ДМП-преобразователь?
Сообщение09.12.2010, 21:50 
Построила по заданной грамматике СУ-схему: $$S\rightarrow P,P \qquad S\rightarrow Q,Q$$ $$P\rightarrow 1,\{1\} \qquad P\rightarrow 1P,\{1\}P$$
$$P\rightarrow 1P0,P \qquad Q\rightarrow 0,\{1\}$$
$$Q\rightarrow 0Q,\{1\} \qquad Q\rightarrow 1Q0,Q$$

Проверила:
$$$(S,S)\Rightarrow (P,P) \Rightarrow (1P0,P) \Rightarrow
(11P0,\{1\}P) \Rightarrow (1110, \{1\}\{1\})$$$
$$$(S,S) \Rightarrow
(Q,Q) \Rightarrow (1Q0,Q) \Rightarrow (100,\{1\})$$$
выводит правильно...
Вот по ней, вроде как, построила транслирующую грамматику
G:
$S\rightarrow P\mid Q
\\ P\rightarrow 1\{1\}\mid 1\{1\}P \mid 1P0
\\ Q\rightarrow 0\{1\}\mid 0\{1\}Q \mid 1Q0$
Не знаю правильно или нет, но вроде по алгоритму.
Может кто-нибудь очень доходчиво объяснить как по этой транслирующей грамматике построить детерминированный преобразователь?? Очень нужно разобраться (...

 
 
 [ Сообщений: 4 ] 


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