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

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


Пусть <math>G=(N,\Sigma,P,S)</math> --- грамматика.
Пусть <math>G=(N,\Sigma,P,S)</math> грамматика.


Отношение ''непосредственной выводимости''
Отношение ''непосредственной выводимости''
<math>\Longrightarrow_G</math> на множестве <math>(N\cup\Sigma)^*</math> определяется
<math>\Longrightarrow_G</math> на множестве <math>(N\cup\Sigma)^*</math> определяется
следующим образом: если <math>\alpha\beta\gamma</math> - цепочка из
следующим образом: если <math>\alpha\beta\gamma</math> цепочка из
<math>(N\cup\Sigma)^*</math> и <math>\beta\longrightarrow\delta</math> --- правило из
<math>(N\cup\Sigma)^*</math> и <math>\beta\longrightarrow\delta</math> правило из
<math>P</math>, то
<math>P</math>, то
<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>\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>\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^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>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_0,\alpha_1,\ldots,\alpha_k</math>, состоящая из <math>k+1</math> цепочек (не обязательно различных), в которой <math>\alpha=\alpha_0\mbox{, }\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>.


''Язык, порождаемый (определяемый) грамматикой'' <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{ и } S\Longrightarrow^*_G\omega\}</math>.
грамматики <math>G</math>, т.е. <math>L(G)=\{\omega:\omega\in\Sigma^*\mbox{ и } S\Longrightarrow^*_G\omega\}</math>.
==Литература==
==Литература==
[Ахо-Ульман],  
* Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: Мир, 1978. — Т. 1,2.
* Касьянов В.Н.  Лекции по теории формальных языков, автоматов и сложности вычислений.  — Новосибирск: НГУ, 1995.


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

Навигация