Выводимая цепочка грамматики: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Выводимая цепочка грамматики''' (''Sentential form'') - цепочка, которая может быть ...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Выводимая цепочка грамматики''' (''Sentential form'') - | '''Выводимая цепочка грамматики''' (''[[Sentential form]]'') - [[цепочка]], которая может быть получена применением правил ''[[грамматика|грамматики]]''. | ||
цепочка, которая может быть получена применением правил ''грамматики''. | |||
Пусть <math>G=(N,\Sigma,P,S)</math> --- грамматика. | Пусть <math>G=(N,\Sigma,P,S)</math> --- грамматика. | ||
| Строка 11: | Строка 10: | ||
<math>\alpha\beta\gamma\Longrightarrow_G\alpha\delta\gamma</math>. | <math>\alpha\beta\gamma\Longrightarrow_G\alpha\delta\gamma</math>. | ||
Транзитивное замыкание отношения <math>\Longrightarrow_G</math> | [[Транзитивное замыкание отношения]] <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>\Longrightarrow_G^+</math> | |||
(<math>\varphi\Longrightarrow^+_G\psi</math> читается: <math>\psi</math> | |||
выводима | |||
рефлексивное и транзитивное замыкание --- через | |||
<math>\Longrightarrow^*_G</math> (<math>\varphi\Longrightarrow^*_G\psi</math> читается: | |||
<math>\psi</math> ''выводима'' из <math>\varphi</math>). | |||
Через <math>\Longrightarrow_G^k</math> обычно обозначается <math>k</math>-степень отношения, | Через <math>\Longrightarrow_G^k</math> обычно обозначается <math>k</math>-степень отношения, | ||
и обычно опускается нижний индекс <math>G</math> в тех случаях, когда из | и обычно опускается нижний индекс <math>G</math> в тех случаях, когда из контекста ясно, о какой грамматике идет речь. | ||
контекста ясно, о какой грамматике идет речь. | |||
Последовательность <math>\alpha_0,\alpha_1,\ldots,\alpha_k</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>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>\alpha</math> называется ''выводимой'' цепочкой грамматики <math>G</math>, если <math>S\Longrightarrow^*_G\alpha</math>. | Цепочка <math>\alpha</math> называется ''выводимой'' цепочкой грамматики <math>G</math>, если <math>S\Longrightarrow^*_G\alpha</math>. | ||
| Строка 33: | Строка 21: | ||
''Язык, порождаемый (определяемый) грамматикой'' <math>G</math> (обозначается | ''Язык, порождаемый (определяемый) грамматикой'' <math>G</math> (обозначается | ||
<math>L(G))</math>, --- это множество терминальных выводимых цепочек | <math>L(G))</math>, --- это множество терминальных выводимых цепочек | ||
грамматики <math>G</math>, т.е. <math>L(G)=\{\omega:\omega\in\Sigma^*\mbox{ | грамматики <math>G</math>, т.е. <math>L(G)=\{\omega:\omega\in\Sigma^*\mbox{ и } S\Longrightarrow^*_G\omega\}</math>. | ||
и } S\Longrightarrow^*_G\omega\}</math>. | |||
==Литература== | ==Литература== | ||
[Ахо-Ульман], | [Ахо-Ульман], | ||
Версия от 11:56, 7 октября 2009
Выводимая цепочка грамматики (Sentential form) - цепочка, которая может быть получена применением правил грамматики.
Пусть [math]\displaystyle{ G=(N,\Sigma,P,S) }[/math] --- грамматика.
Отношение непосредственной выводимости [math]\displaystyle{ \Longrightarrow_G }[/math] на множестве [math]\displaystyle{ (N\cup\Sigma)^* }[/math] определяется следующим образом: если [math]\displaystyle{ \alpha\beta\gamma }[/math] - цепочка из [math]\displaystyle{ (N\cup\Sigma)^* }[/math] и [math]\displaystyle{ \beta\longrightarrow\delta }[/math] --- правило из [math]\displaystyle{ P }[/math], то [math]\displaystyle{ \alpha\beta\gamma\Longrightarrow_G\alpha\delta\gamma }[/math].
Транзитивное замыкание отношения [math]\displaystyle{ \Longrightarrow_G }[/math] обозначается через [math]\displaystyle{ \Longrightarrow_G^+ }[/math] ([math]\displaystyle{ \varphi\Longrightarrow^+_G\psi }[/math] читается: [math]\displaystyle{ \psi }[/math] выводима из [math]\displaystyle{ \varphi }[/math] нетривиальным образом), а его рефлексивное и транзитивное замыкание --- через [math]\displaystyle{ \Longrightarrow^*_G }[/math] ([math]\displaystyle{ \varphi\Longrightarrow^*_G\psi }[/math] читается: [math]\displaystyle{ \psi }[/math] выводима из [math]\displaystyle{ \varphi }[/math]).
Через [math]\displaystyle{ \Longrightarrow_G^k }[/math] обычно обозначается [math]\displaystyle{ k }[/math]-степень отношения, и обычно опускается нижний индекс [math]\displaystyle{ G }[/math] в тех случаях, когда из контекста ясно, о какой грамматике идет речь.
Последовательность [math]\displaystyle{ \alpha_0,\alpha_1,\ldots,\alpha_k }[/math], состоящая из [math]\displaystyle{ k+1 }[/math] цепочек (не обязательно различных), в которой [math]\displaystyle{ \alpha=\alpha_0 }[/math], [math]\displaystyle{ \alpha_{i-1}\Longrightarrow_G\alpha_i }[/math] для всех [math]\displaystyle{ i \geq 1 }[/math] и [math]\displaystyle{ \alpha_k=\beta }[/math], называется выводом длины [math]\displaystyle{ k }[/math] цепочки [math]\displaystyle{ \beta }[/math] из цепочки [math]\displaystyle{ \alpha }[/math] в грамматике [math]\displaystyle{ G }[/math].
Цепочка [math]\displaystyle{ \alpha }[/math] называется выводимой цепочкой грамматики [math]\displaystyle{ G }[/math], если [math]\displaystyle{ S\Longrightarrow^*_G\alpha }[/math].
Язык, порождаемый (определяемый) грамматикой [math]\displaystyle{ G }[/math] (обозначается [math]\displaystyle{ L(G)) }[/math], --- это множество терминальных выводимых цепочек грамматики [math]\displaystyle{ G }[/math], т.е. [math]\displaystyle{ L(G)=\{\omega:\omega\in\Sigma^*\mbox{ и } S\Longrightarrow^*_G\omega\} }[/math].
Литература
[Ахо-Ульман],
[Касьянов/95],
[Касьянов-Поттосин]