Выводимая цепочка грамматики: различия между версиями

'''Выводимая цепочка грамматики''' (''[[Sentential form]]'') - [[цепочка]], которая может быть получена применением правил ''[[грамматика|грамматики]]''.

[[Транзитивное замыкание отношения]] <math>\Longrightarrow_G</math> обозначается через <math>\Longrightarrow_G^+</math> (<math>\varphi\Longrightarrow^+_G\psi</math> читается: <math>\psi</math> выводима из <math>\varphi</math> ''нетривиальным образом''), а его рефлексивное и транзитивное замыкание --- через <math>\Longrightarrow^*_G</math> (<math>\varphi\Longrightarrow^*_G\psi</math> читается: <math>\psi</math> ''выводима'' из <math>\varphi</math>).

и обычно опускается нижний индекс <math>G</math> в тех случаях, когда из контекста ясно, о какой грамматике идет речь.

Последовательность <math>\alpha_0,\alpha_1,\ldots,\alpha_k</math>, состоящая из <math>k+1</math> цепочек (не обязательно различных), в которой <math>\alpha=\alpha_0</math>, <math>\alpha_{i-1}\Longrightarrow_G\alpha_i</math> для всех <math>i \geq 1</math> и <math>\alpha_k=\beta</math>, называется ''выводом длины'' <math>k</math> цепочки <math>\beta</math> из цепочки <math>\alpha</math> в грамматике <math>G</math>.

грамматики <math>G</math>, т.е. <math>L(G)=\{\omega:\omega\in\Sigma^*\mbox{ и } S\Longrightarrow^*_G\omega\}</math>.