Выводимая цепочка грамматики

Выводимая цепочка грамматики (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\mbox{, }\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].

Литература

• Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: Мир, 1978. — Т. 1,2.

• Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.

• Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. — Новосибирск: Наука. Сиб. отд-ние, 1986.