2014 dxdy logo

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

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




 
 Построение КС-грамматики
Сообщение24.09.2011, 01:56 
Праверьте пожалуйста правильность построения КС-грамматики, порождающей язык:
$\[\left\{ {x\;|\;x\, \in \;\{ a,\;d\} *,\quad |x{|_a}\; \ge \;|x{|_d}} \right\};\]$
где метасимвол * обозначает любое слово в данном алфавите.

Пусть слово $x$ начинается с символа $a$, тогда рассмотрим два случая (рассмотрим пока слова длины в 4 символа):
$\[1)a\,\underbrace {\overbrace {add}^{B'}}_B\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,2)a\,\underbrace {\overbrace {dad}^{B''}}_B\,\,\]$

Т.е. $B$ возможно является словом с избытком символов $d$ (точнее оно может содержат на один символ $d$больше, чем нужно). А $B''$ может содержать на два символа $d$ больше, чем нужно.
Далее, $B'$ всегда можно представить в виде двух стоящих рядом подцепочек, каждая из которых содержит на одно вхождение символа "d" больше, чем нужно. Поэтому в первом случае:
$\[B \to a\overbrace {BB}^{B'}\]$
В случае 2: $\[B \to d\overbrace S^{B''}\]$ (где $S$ - слово из данного языка)
Итак, если слово x начинается с $a$, то $\[B \to aBB|dS\]$

Теперь пусть слово $x$ начинается с символа d. Тогда получим два случая:
$\[1)d\,\underbrace {a\overbrace {da}^{A'}}_A\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,2)a\,\underbrace {\overbrace {dad}^{A''}}_A\,\,\]$

Тогда $\[A \to aS|daSa|dSaa|daaS\]$ (т.к. в слове $A$ всегда содержится как минимум на два символа "a" больше, чем символов "d")

Собрав все вместе, получим ответ:
$\[\begin{array}{l}
S \to aB|dA|\varepsilon \\
B \to aBB|dS\\
A \to aS|daSa|dSaa|daaS
\end{array}\]$

Думаю что есть способы проще, но я нигде примеров не нашел по построению грамматик, может еще книгу мне посоветуете с примерами, очень пригодится

 
 
 
 Re: Построение КС-грамматики
Сообщение24.09.2011, 16:46 
Если не ошибся в рассуждении, то вот что вышло:

$\begin{array}{rcl} 
S & \to & SaSdS \\ 
& \to & SdSaS \\ 
& \to & SaS \\ 
& \to & \varepsilon 
\end{array}$

или, немного изменив:

$\begin{array}{rcl} 
S & \to & SAS \\ 
& \to & \varepsilon \\ 
A & \to & aSd \\ 
& \to & dSa \\
& \to & a 
\end{array}$

Строк с большим количеством d, чем a, не получится. Но будут ли получаться все возможные строки языка, не очень представляю (только надеюсь).

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


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