Викиконспекты - Вклад участника [ru]

Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора

2014-12-10T18:58:35Z

Maryann: /* Лево- и правосторонний вывод слова */

==Основные определения==
{{Определение
|id=csgrammar
|definition=
'''Контекстно-свободной грамматикой''' (англ. ''сontext-free grammar'') называется грамматика, у которой в левых частях всех правил стоят только одиночные нетерминалы.
}}
{{Определение
|definition=
'''Контекстно-свободный язык''' (англ. ''context-free language'') {{---}} язык, задаваемый контекстно-свободной грамматикой.
}}

==Лево- и правосторонний вывод слова==

{{Определение
|definition=
'''Выводом слова''' (англ. ''derivation of a word'') <tex>\alpha</tex> называется последовательность строк, состоящих из терминалов и нетерминалов. Первая строка последовательности состоит из одного стартового нетерминала. Каждая последующая строка получена из предыдущей путем замены любого нетерминала по одному (любому) из правил, а последней строкой в последовательности является слово <tex>\alpha</tex>.
}}
'''Пример:'''

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

<tex>"("</tex> и <tex>")"</tex> {{---}} терминальные символы;

<tex>S</tex> {{---}} стартовый нетерминал;

Правила: 
<tex>S\rightarrow (S)S</tex> 
<tex>S\rightarrow S(S)</tex> 
<tex>S\rightarrow \varepsilon</tex> 
Выведем слово <tex>"(()(()))()"</tex>: 
<tex>\boldsymbol{S}\Rightarrow (S)\boldsymbol{S} \Rightarrow (S)(\boldsymbol{S})S\Rightarrow(S)()\boldsymbol{S}\Rightarrow(\boldsymbol{S})()\Rightarrow(\boldsymbol{S}(S))()\Rightarrow(S(S)(\boldsymbol{S}))()\Rightarrow(S(S)(\boldsymbol{S}(S)))()\Rightarrow (S(\boldsymbol{S})((S)))()\Rightarrow(\boldsymbol{S}()((S)))()\Rightarrow(()((\boldsymbol{S})))()\Rightarrow(()(()))()</tex>

{{Определение
|definition=
'''Левосторонним выводом слова''' (англ. ''leftmost derivation'') <tex>\alpha</tex> называется такой вывод слова <tex>\alpha</tex>, в котором каждая последующая строка получена из предыдущей путем замены по одному из правил самого левого встречающегося в строке нетерминала.
}}

{{Определение
|definition=
'''Правосторонним выводом слова''' (англ. ''rightmost derivation'') <tex>\alpha</tex> называется такой вывод слова <tex>\alpha</tex>, в котором каждая последующая строка получена из предыдущей путем замены по одному из правил самого правого встречающегося в строке нетерминала.
}}
Рассмотрим левосторонний вывод скобочной последовательности из примера: 
<tex>\boldsymbol{S}\Rightarrow (\boldsymbol{S})S \Rightarrow ((\boldsymbol{S})S)S\Rightarrow (()\boldsymbol{S})S\Rightarrow(()\boldsymbol{S}(S))S\Rightarrow(()(\boldsymbol{S}))S\Rightarrow(()(\boldsymbol{S}(S)))S\Rightarrow(()((\boldsymbol{S})))S\Rightarrow(()(()))\boldsymbol{S}\Rightarrow(()(()))(\boldsymbol{S})S\Rightarrow(()(()))()\boldsymbol{S}\Rightarrow(()(()))()</tex>

==Дерево разбора==

{{Определение
|definition=
'''Деревом разбора грамматики''' (англ. ''parse tree'') называется дерево, в вершинах которого записаны терминалы или нетерминалы. Все вершины, помеченные терминалами, являются листьями. Все вершины, помеченные нетерминалами, имеют детей. Дети вершины, в которой записан нетерминал, соответствуют раскрытию нетерминала по одному любому правилу (в левой части которого стоит этот нетерминал) и упорядочены так же, как в правой части этого правила.
}}
{{Определение
|definition=
'''Крона''' дерева разбора (англ. ''leaves of the parse tree'') {{---}} множество терминальных символов, упорядоченное в соответствии с номерами их достижения при обходе дерева в глубину из корня. Крона дерева разбора представляет из себя слово языка, которое выводит это дерево.
}}
 
Построим дерево разбора скобочной последовательности из примера. 
[[Файл:ParsingTree.png|350px]]

==Однозначные грамматики==

{{Определение
|definition=
Грамматика называется '''однозначной''' (англ. ''unambiguous grammar''), если у каждого слова имеется не более одного дерева разбора в этой грамматике.
}}

{{Лемма
|id=lemma-
|statement=
Пусть <tex>\Gamma</tex> {{---}} однозначная грамматика. Тогда <tex>\forall \omega \in \mathbb{L}(\Gamma)</tex> существует ровно один левосторонний (правосторонний) вывод.
|proof=
Очевидно, что по дереву разбора однозначно восстанавливается левосторонний(правосторонний) вывод. Поскольку каждое слово из языка выводится только одним деревом разбора, то существует только один левосторонний(правосторонний) вывод этого слова.
}}
 
{{Утверждение
|statement = Грамматика из примера не является однозначной.
|proof =
Выше уже было построено дерево разбора для слова <tex>"(()(()))()"</tex>.
Построим еще одно дерево разбора для данного слова.

Например, оно будет выглядеть так:

[[Файл:Parsetree2.png|300px]]
Таким образом, существует слово, у которого есть более одного дерева разбора в данной грамматике <tex>\Rightarrow</tex> эта грамматика не является однозначной.
}}
 
{{Утверждение
|statement = Существуют языки, которые можно задать одновременно как однозначными, так и неоднозначными грамматиками.
|proof =
Для доказательства достаточно привести однозначную грамматику для языка правильных скобочных последовательностей (неоднозначной грамматикой для данного языка является грамматика из примера выше).

Рассмотрим грамматику:

<tex>"("</tex> и <tex>")"</tex> {{---}} терминальные символы;

<tex>S</tex> {{---}} стартовый нетерминал;

Правила: 
1) <tex>S\rightarrow (S)S</tex> 
2) <tex>S\rightarrow \varepsilon</tex> 

Покажем, что эта грамматика однозначна.

Для этого, используя индукцию, докажем, что для любого слова <tex>\omega</tex>, являющегося правильной скобочной последовательностью, в данной грамматике существует только одно дерево разбора.

'''База:''' Если <tex>\omega=\varepsilon</tex>, то оно выводится только по второму правилу <tex>\Rightarrow</tex> для него существует единственное дерево разбора.

'''Переход:''' Пусть <tex>\left\vert \omega \right\vert=n</tex> и <tex>\forall \upsilon</tex>: <tex>\left\vert \upsilon \right\vert < n</tex> и <tex>\upsilon</tex> {{---}} правильная скобочная последовательность <tex>\exists!</tex> дерево разбора.

Найдем в слове <tex>\omega</tex> минимальный индекс <tex>i \neq 0</tex> такой, что слово <tex>\omega[0..i]</tex> является правильной скобочной последовательностью. Так как <tex>i \neq 0</tex> минимальный, то <tex>\omega[0..i]=(\alpha)</tex>. Из того, что <tex>\omega</tex> является правильной скобочной последовательностью <tex>\Rightarrow</tex> <tex>\alpha</tex> и <tex>\beta=\omega[i+1..n-1]</tex> {{---}} правильные скобочные последовательности, при этом <tex>\left\vert \alpha \right\vert<n</tex> и <tex>\left\vert \beta \right\vert<n \Rightarrow</tex> по индукционному предположению предположению у <tex>\alpha</tex> и <tex>\beta</tex> существуют единственные деревья разбора.

Если мы покажем, что из части <tex>(S)</tex> первого правила можно вывести только слово <tex>(\alpha)</tex>, то утверждение будет доказано (так как из первой части первого правила выводится <tex>\alpha</tex>, а из второй только <tex>\beta</tex> и для каждого из них по предположению существуют единственные деревья разбора).

Пусть из <tex>(S)</tex> была выведена часть слова <tex>\omega[0..j]=(\gamma)</tex>, где <tex>j < i</tex>, при этом <tex>\gamma</tex> является правильной скобочной последовательностью, но тогда как минимальный индекс мы должны были выбрать <tex>j</tex>, а не <tex>i</tex> {{---}} противоречие.

Аналогично из <tex>(S)</tex> не может быть выведена часть слова <tex>\omega[0..j]</tex>, где <tex>j > i</tex>, потому что тогда <tex>\omega[0..i]=(\alpha)</tex> не будет правильной скобочной последовательностью, так как в позиции <tex>i-1</tex> баланс скобок будет отрицательный.

Значит, из <tex>(S)</tex> была выведена часть слова <tex>\omega[0..i] \Rightarrow \omega</tex> имеет единственное дерево разбора <tex>\Rightarrow</tex> данная грамматика однозначная.

Таким образом, для языка правильных скобочных последовательностей мы привели пример как однозначной, так и неоднозначной грамматики.
}}

Однако, есть КС-языки, для которых не существует однозначных КС-грамматик. Такие языки и грамматики их порождающие называют [[Существенно неоднозначные языки|''существенно неоднозначными'']].

==См. также==
* [[Формальные грамматики]]
* [[Иерархия Хомского формальных грамматик]]
* [[Замкнутость КС-языков относительно различных операций]]
* [[Существенно неоднозначные языки]]

== Источники информации ==
* [[wikipedia:Context-free grammar | Wikipedia {{---}} Context-free grammar]]
* [[wikipedia:ru:Контекстно-свободная грамматика | Википедия {{---}} Контекстно-свободная грамматика]]
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' {{---}} '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора

2014-12-10T18:51:58Z

Maryann: /* Лево- и правосторонний вывод слова */

==Основные определения==
{{Определение
|id=csgrammar
|definition=
'''Контекстно-свободной грамматикой''' (англ. ''сontext-free grammar'') называется грамматика, у которой в левых частях всех правил стоят только одиночные нетерминалы.
}}
{{Определение
|definition=
'''Контекстно-свободный язык''' (англ. ''context-free language'') {{---}} язык, задаваемый контекстно-свободной грамматикой.
}}

==Лево- и правосторонний вывод слова==

{{Определение
|definition=
'''Выводом слова''' (англ. ''derivation of a word'') <tex>\alpha</tex> называется последовательность строк, состоящих из терминалов и нетерминалов. Первая строка последовательности состоит из одного стартового нетерминала. Каждая последующая строка получена из предыдущей путем замены любого нетерминала по одному (любому) из правил, а последней строкой в последовательности является слово <tex>\alpha</tex>.
}}
'''Пример:'''

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

<tex>"("</tex> и <tex>")"</tex> {{---}} терминальные символы;

<tex>S</tex> {{---}} стартовый нетерминал;

Правила: 
<tex>S\rightarrow (S)S</tex> 
<tex>S\rightarrow S(S)</tex> 
<tex>S\rightarrow \varepsilon</tex> 
Выведем слово <tex>"(()(()))()"</tex>: 
<tex>\boldsymbol{S}\Rightarrow (S)\boldsymbol{S} \Rightarrow (S)(\boldsymbol{S})S\Rightarrow(S)()\boldsymbol{S}\Rightarrow(\boldsymbol{S})()\Rightarrow(\boldsymbol{S}(S))()\Rightarrow(S(S)(\boldsymbol{S}))()\Rightarrow(S(S)(\boldsymbol{S}(S)))()\Rightarrow (S(\boldsymbol{S})((S)))()\Rightarrow(\boldsymbol{S}()((S)))()\Rightarrow(()((\boldsymbol{S})))()\Rightarrow(()(()))()</tex>

{{Определение
|definition=
'''Левосторонним выводом слова''' (англ. ''leftmost derivation'') <tex>\alpha</tex> называется такой вывод <tex>\alpha</tex>, в котором каждая последующая строка получена из предыдущей путем замены по одному из правил самого левого встречающегося в строке нетерминала.
}}

{{Определение
|definition=
'''Правосторонним выводом слова''' (англ. ''rightmost derivation'') <tex>\alpha</tex> называется такой вывод <tex>\alpha</tex>, в котором каждая последующая строка получена из предыдущей путем замены по одному из правил самого правого встречающегося в строке нетерминала.
}}
Рассмотрим левосторонний вывод скобочной последовательности из примера: 
<tex>\boldsymbol{S}\Rightarrow (\boldsymbol{S})S \Rightarrow ((\boldsymbol{S})S)S\Rightarrow (()\boldsymbol{S})S\Rightarrow(()\boldsymbol{S}(S))S\Rightarrow(()(\boldsymbol{S}))S\Rightarrow(()(\boldsymbol{S}(S)))S\Rightarrow(()((\boldsymbol{S})))S\Rightarrow(()(()))\boldsymbol{S}\Rightarrow(()(()))(\boldsymbol{S})S\Rightarrow(()(()))()\boldsymbol{S}\Rightarrow(()(()))()</tex>

==Дерево разбора==

{{Определение
|definition=
'''Деревом разбора грамматики''' (англ. ''parse tree'') называется дерево, в вершинах которого записаны терминалы или нетерминалы. Все вершины, помеченные терминалами, являются листьями. Все вершины, помеченные нетерминалами, имеют детей. Дети вершины, в которой записан нетерминал, соответствуют раскрытию нетерминала по одному любому правилу (в левой части которого стоит этот нетерминал) и упорядочены так же, как в правой части этого правила.
}}
{{Определение
|definition=
'''Крона''' дерева разбора (англ. ''leaves of the parse tree'') {{---}} множество терминальных символов, упорядоченное в соответствии с номерами их достижения при обходе дерева в глубину из корня. Крона дерева разбора представляет из себя слово языка, которое выводит это дерево.
}}
 
Построим дерево разбора скобочной последовательности из примера. 
[[Файл:ParsingTree.png|350px]]

==Однозначные грамматики==

{{Определение
|definition=
Грамматика называется '''однозначной''' (англ. ''unambiguous grammar''), если у каждого слова имеется не более одного дерева разбора в этой грамматике.
}}

{{Лемма
|id=lemma-
|statement=
Пусть <tex>\Gamma</tex> {{---}} однозначная грамматика. Тогда <tex>\forall \omega \in \mathbb{L}(\Gamma)</tex> существует ровно один левосторонний (правосторонний) вывод.
|proof=
Очевидно, что по дереву разбора однозначно восстанавливается левосторонний(правосторонний) вывод. Поскольку каждое слово из языка выводится только одним деревом разбора, то существует только один левосторонний(правосторонний) вывод этого слова.
}}
 
{{Утверждение
|statement = Грамматика из примера не является однозначной.
|proof =
Выше уже было построено дерево разбора для слова <tex>"(()(()))()"</tex>.
Построим еще одно дерево разбора для данного слова.

Например, оно будет выглядеть так:

[[Файл:Parsetree2.png|300px]]
Таким образом, существует слово, у которого есть более одного дерева разбора в данной грамматике <tex>\Rightarrow</tex> эта грамматика не является однозначной.
}}
 
{{Утверждение
|statement = Существуют языки, которые можно задать одновременно как однозначными, так и неоднозначными грамматиками.
|proof =
Для доказательства достаточно привести однозначную грамматику для языка правильных скобочных последовательностей (неоднозначной грамматикой для данного языка является грамматика из примера выше).

Рассмотрим грамматику:

<tex>"("</tex> и <tex>")"</tex> {{---}} терминальные символы;

<tex>S</tex> {{---}} стартовый нетерминал;

Правила: 
1) <tex>S\rightarrow (S)S</tex> 
2) <tex>S\rightarrow \varepsilon</tex> 

Покажем, что эта грамматика однозначна.

Для этого, используя индукцию, докажем, что для любого слова <tex>\omega</tex>, являющегося правильной скобочной последовательностью, в данной грамматике существует только одно дерево разбора.

'''База:''' Если <tex>\omega=\varepsilon</tex>, то оно выводится только по второму правилу <tex>\Rightarrow</tex> для него существует единственное дерево разбора.

'''Переход:''' Пусть <tex>\left\vert \omega \right\vert=n</tex> и <tex>\forall \upsilon</tex>: <tex>\left\vert \upsilon \right\vert < n</tex> и <tex>\upsilon</tex> {{---}} правильная скобочная последовательность <tex>\exists!</tex> дерево разбора.

Найдем в слове <tex>\omega</tex> минимальный индекс <tex>i \neq 0</tex> такой, что слово <tex>\omega[0..i]</tex> является правильной скобочной последовательностью. Так как <tex>i \neq 0</tex> минимальный, то <tex>\omega[0..i]=(\alpha)</tex>. Из того, что <tex>\omega</tex> является правильной скобочной последовательностью <tex>\Rightarrow</tex> <tex>\alpha</tex> и <tex>\beta=\omega[i+1..n-1]</tex> {{---}} правильные скобочные последовательности, при этом <tex>\left\vert \alpha \right\vert<n</tex> и <tex>\left\vert \beta \right\vert<n \Rightarrow</tex> по индукционному предположению предположению у <tex>\alpha</tex> и <tex>\beta</tex> существуют единственные деревья разбора.

Если мы покажем, что из части <tex>(S)</tex> первого правила можно вывести только слово <tex>(\alpha)</tex>, то утверждение будет доказано (так как из первой части первого правила выводится <tex>\alpha</tex>, а из второй только <tex>\beta</tex> и для каждого из них по предположению существуют единственные деревья разбора).

Пусть из <tex>(S)</tex> была выведена часть слова <tex>\omega[0..j]=(\gamma)</tex>, где <tex>j < i</tex>, при этом <tex>\gamma</tex> является правильной скобочной последовательностью, но тогда как минимальный индекс мы должны были выбрать <tex>j</tex>, а не <tex>i</tex> {{---}} противоречие.

Аналогично из <tex>(S)</tex> не может быть выведена часть слова <tex>\omega[0..j]</tex>, где <tex>j > i</tex>, потому что тогда <tex>\omega[0..i]=(\alpha)</tex> не будет правильной скобочной последовательностью, так как в позиции <tex>i-1</tex> баланс скобок будет отрицательный.

Значит, из <tex>(S)</tex> была выведена часть слова <tex>\omega[0..i] \Rightarrow \omega</tex> имеет единственное дерево разбора <tex>\Rightarrow</tex> данная грамматика однозначная.

Таким образом, для языка правильных скобочных последовательностей мы привели пример как однозначной, так и неоднозначной грамматики.
}}

Однако, есть КС-языки, для которых не существует однозначных КС-грамматик. Такие языки и грамматики их порождающие называют [[Существенно неоднозначные языки|''существенно неоднозначными'']].

==См. также==
* [[Формальные грамматики]]
* [[Иерархия Хомского формальных грамматик]]
* [[Замкнутость КС-языков относительно различных операций]]
* [[Существенно неоднозначные языки]]

== Источники информации ==
* [[wikipedia:Context-free grammar | Wikipedia {{---}} Context-free grammar]]
* [[wikipedia:ru:Контекстно-свободная грамматика | Википедия {{---}} Контекстно-свободная грамматика]]
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' {{---}} '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора

2014-12-10T18:40:23Z

Maryann: /* Дерево разбора */

==Основные определения==
{{Определение
|id=csgrammar
|definition=
'''Контекстно-свободной грамматикой''' (англ. ''сontext-free grammar'') называется грамматика, у которой в левых частях всех правил стоят только одиночные нетерминалы.
}}
{{Определение
|definition=
'''Контекстно-свободный язык''' (англ. ''context-free language'') {{---}} язык, задаваемый контекстно-свободной грамматикой.
}}

==Лево- и правосторонний вывод слова==

{{Определение
|definition=
'''Выводом слова''' (англ. ''derivation of a word'') <tex>\alpha</tex> называется последовательность строк, состоящих из терминалов и нетерминалов. Первая строка последовательности состоит из одного стартового нетерминала. Каждая последующая строка получена из предыдущей путем замены любого нетерминала по одному (любому) из правил, а последней строкой в последовательности является слово <tex>\alpha</tex>.
}}
'''Пример:'''

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

<tex>"("</tex> и <tex>")"</tex> {{---}} терминальные символы;

<tex>S</tex> {{---}} стартовый нетерминал;

Правила: 
<tex>S\rightarrow (S)S</tex> 
<tex>S\rightarrow S(S)</tex> 
<tex>S\rightarrow \varepsilon</tex> 
Выведем слово <tex>"(()(()))()"</tex>: 
<tex>\boldsymbol{S}\Rightarrow (S)\boldsymbol{S} \Rightarrow (S)(\boldsymbol{S})S\Rightarrow(S)()\boldsymbol{S}\Rightarrow(\boldsymbol{S})()\Rightarrow(\boldsymbol{S}(S))()\Rightarrow(S(S)(\boldsymbol{S}))()\Rightarrow(S(S)(\boldsymbol{S}(S)))()\Rightarrow (S(\boldsymbol{S})((S)))()\Rightarrow(\boldsymbol{S}()((S)))()\Rightarrow(()((\boldsymbol{S})))()\Rightarrow(()(()))()</tex>

{{Определение
|definition=
'''Левосторонний вывод слова''' (англ. ''leftmost derivation'')<tex>\alpha</tex> {{---}} вывод, где каждая последующая строка получена из предыдущей путем замены по одному из правил самого левого встречающегося в строке нетерминала.
}}

{{Определение
|definition=
'''Правосторонним выводом слова''' (англ. '' rightmost derivation'') <tex>\alpha</tex> {{---}} вывод, где каждая последующая строка получена из предыдущей путем замены по одному из правил самого правого встречающегося в строке нетерминала.
}}
Рассмотрим левосторонний вывод скобочной последовательности из примера: 
<tex>\boldsymbol{S}\Rightarrow (\boldsymbol{S})S \Rightarrow ((\boldsymbol{S})S)S\Rightarrow (()\boldsymbol{S})S\Rightarrow(()\boldsymbol{S}(S))S\Rightarrow(()(\boldsymbol{S}))S\Rightarrow(()(\boldsymbol{S}(S)))S\Rightarrow(()((\boldsymbol{S})))S\Rightarrow(()(()))\boldsymbol{S}\Rightarrow(()(()))(\boldsymbol{S})S\Rightarrow(()(()))()\boldsymbol{S}\Rightarrow(()(()))()</tex>

==Дерево разбора==

{{Определение
|definition=
'''Деревом разбора грамматики''' (англ. ''parse tree'') называется дерево, в вершинах которого записаны терминалы или нетерминалы. Все вершины, помеченные терминалами, являются листьями. Все вершины, помеченные нетерминалами, имеют детей. Дети вершины, в которой записан нетерминал, соответствуют раскрытию нетерминала по одному любому правилу (в левой части которого стоит этот нетерминал) и упорядочены так же, как в правой части этого правила.
}}
{{Определение
|definition=
'''Крона''' дерева разбора (англ. ''leaves of the parse tree'') {{---}} множество терминальных символов, упорядоченное в соответствии с номерами их достижения при обходе дерева в глубину из корня. Крона дерева разбора представляет из себя слово языка, которое выводит это дерево.
}}
 
Построим дерево разбора скобочной последовательности из примера. 
[[Файл:ParsingTree.png|350px]]

==Однозначные грамматики==

{{Определение
|definition=
Грамматика называется '''однозначной''' (англ. ''unambiguous grammar''), если у каждого слова имеется не более одного дерева разбора в этой грамматике.
}}

{{Лемма
|id=lemma-
|statement=
Пусть <tex>\Gamma</tex> {{---}} однозначная грамматика. Тогда <tex>\forall \omega \in \mathbb{L}(\Gamma)</tex> существует ровно один левосторонний (правосторонний) вывод.
|proof=
Очевидно, что по дереву разбора однозначно восстанавливается левосторонний(правосторонний) вывод. Поскольку каждое слово из языка выводится только одним деревом разбора, то существует только один левосторонний(правосторонний) вывод этого слова.
}}
 
{{Утверждение
|statement = Грамматика из примера не является однозначной.
|proof =
Выше уже было построено дерево разбора для слова <tex>"(()(()))()"</tex>.
Построим еще одно дерево разбора для данного слова.

Например, оно будет выглядеть так:

[[Файл:Parsetree2.png|300px]]
Таким образом, существует слово, у которого есть более одного дерева разбора в данной грамматике <tex>\Rightarrow</tex> эта грамматика не является однозначной.
}}
 
{{Утверждение
|statement = Существуют языки, которые можно задать одновременно как однозначными, так и неоднозначными грамматиками.
|proof =
Для доказательства достаточно привести однозначную грамматику для языка правильных скобочных последовательностей (неоднозначной грамматикой для данного языка является грамматика из примера выше).

Рассмотрим грамматику:

<tex>"("</tex> и <tex>")"</tex> {{---}} терминальные символы;

<tex>S</tex> {{---}} стартовый нетерминал;

Правила: 
1) <tex>S\rightarrow (S)S</tex> 
2) <tex>S\rightarrow \varepsilon</tex> 

Покажем, что эта грамматика однозначна.

Для этого, используя индукцию, докажем, что для любого слова <tex>\omega</tex>, являющегося правильной скобочной последовательностью, в данной грамматике существует только одно дерево разбора.

'''База:''' Если <tex>\omega=\varepsilon</tex>, то оно выводится только по второму правилу <tex>\Rightarrow</tex> для него существует единственное дерево разбора.

'''Переход:''' Пусть <tex>\left\vert \omega \right\vert=n</tex> и <tex>\forall \upsilon</tex>: <tex>\left\vert \upsilon \right\vert < n</tex> и <tex>\upsilon</tex> {{---}} правильная скобочная последовательность <tex>\exists!</tex> дерево разбора.

Найдем в слове <tex>\omega</tex> минимальный индекс <tex>i \neq 0</tex> такой, что слово <tex>\omega[0..i]</tex> является правильной скобочной последовательностью. Так как <tex>i \neq 0</tex> минимальный, то <tex>\omega[0..i]=(\alpha)</tex>. Из того, что <tex>\omega</tex> является правильной скобочной последовательностью <tex>\Rightarrow</tex> <tex>\alpha</tex> и <tex>\beta=\omega[i+1..n-1]</tex> {{---}} правильные скобочные последовательности, при этом <tex>\left\vert \alpha \right\vert<n</tex> и <tex>\left\vert \beta \right\vert<n \Rightarrow</tex> по индукционному предположению предположению у <tex>\alpha</tex> и <tex>\beta</tex> существуют единственные деревья разбора.

Если мы покажем, что из части <tex>(S)</tex> первого правила можно вывести только слово <tex>(\alpha)</tex>, то утверждение будет доказано (так как из первой части первого правила выводится <tex>\alpha</tex>, а из второй только <tex>\beta</tex> и для каждого из них по предположению существуют единственные деревья разбора).

Пусть из <tex>(S)</tex> была выведена часть слова <tex>\omega[0..j]=(\gamma)</tex>, где <tex>j < i</tex>, при этом <tex>\gamma</tex> является правильной скобочной последовательностью, но тогда как минимальный индекс мы должны были выбрать <tex>j</tex>, а не <tex>i</tex> {{---}} противоречие.

Аналогично из <tex>(S)</tex> не может быть выведена часть слова <tex>\omega[0..j]</tex>, где <tex>j > i</tex>, потому что тогда <tex>\omega[0..i]=(\alpha)</tex> не будет правильной скобочной последовательностью, так как в позиции <tex>i-1</tex> баланс скобок будет отрицательный.

Значит, из <tex>(S)</tex> была выведена часть слова <tex>\omega[0..i] \Rightarrow \omega</tex> имеет единственное дерево разбора <tex>\Rightarrow</tex> данная грамматика однозначная.

Таким образом, для языка правильных скобочных последовательностей мы привели пример как однозначной, так и неоднозначной грамматики.
}}

Однако, есть КС-языки, для которых не существует однозначных КС-грамматик. Такие языки и грамматики их порождающие называют [[Существенно неоднозначные языки|''существенно неоднозначными'']].

==См. также==
* [[Формальные грамматики]]
* [[Иерархия Хомского формальных грамматик]]
* [[Замкнутость КС-языков относительно различных операций]]
* [[Существенно неоднозначные языки]]

== Источники информации ==
* [[wikipedia:Context-free grammar | Wikipedia {{---}} Context-free grammar]]
* [[wikipedia:ru:Контекстно-свободная грамматика | Википедия {{---}} Контекстно-свободная грамматика]]
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' {{---}} '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора

2014-12-10T18:38:42Z

Maryann: /* Литература */

==Основные определения==
{{Определение
|id=csgrammar
|definition=
'''Контекстно-свободной грамматикой''' (англ. ''сontext-free grammar'') называется грамматика, у которой в левых частях всех правил стоят только одиночные нетерминалы.
}}
{{Определение
|definition=
'''Контекстно-свободный язык''' (англ. ''context-free language'') {{---}} язык, задаваемый контекстно-свободной грамматикой.
}}

==Лево- и правосторонний вывод слова==

{{Определение
|definition=
'''Выводом слова''' (англ. ''derivation of a word'') <tex>\alpha</tex> называется последовательность строк, состоящих из терминалов и нетерминалов. Первая строка последовательности состоит из одного стартового нетерминала. Каждая последующая строка получена из предыдущей путем замены любого нетерминала по одному (любому) из правил, а последней строкой в последовательности является слово <tex>\alpha</tex>.
}}
'''Пример:'''

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

<tex>"("</tex> и <tex>")"</tex> {{---}} терминальные символы;

<tex>S</tex> {{---}} стартовый нетерминал;

Правила: 
<tex>S\rightarrow (S)S</tex> 
<tex>S\rightarrow S(S)</tex> 
<tex>S\rightarrow \varepsilon</tex> 
Выведем слово <tex>"(()(()))()"</tex>: 
<tex>\boldsymbol{S}\Rightarrow (S)\boldsymbol{S} \Rightarrow (S)(\boldsymbol{S})S\Rightarrow(S)()\boldsymbol{S}\Rightarrow(\boldsymbol{S})()\Rightarrow(\boldsymbol{S}(S))()\Rightarrow(S(S)(\boldsymbol{S}))()\Rightarrow(S(S)(\boldsymbol{S}(S)))()\Rightarrow (S(\boldsymbol{S})((S)))()\Rightarrow(\boldsymbol{S}()((S)))()\Rightarrow(()((\boldsymbol{S})))()\Rightarrow(()(()))()</tex>

{{Определение
|definition=
'''Левосторонний вывод слова''' (англ. ''leftmost derivation'')<tex>\alpha</tex> {{---}} вывод, где каждая последующая строка получена из предыдущей путем замены по одному из правил самого левого встречающегося в строке нетерминала.
}}

{{Определение
|definition=
'''Правосторонним выводом слова''' (англ. '' rightmost derivation'') <tex>\alpha</tex> {{---}} вывод, где каждая последующая строка получена из предыдущей путем замены по одному из правил самого правого встречающегося в строке нетерминала.
}}
Рассмотрим левосторонний вывод скобочной последовательности из примера: 
<tex>\boldsymbol{S}\Rightarrow (\boldsymbol{S})S \Rightarrow ((\boldsymbol{S})S)S\Rightarrow (()\boldsymbol{S})S\Rightarrow(()\boldsymbol{S}(S))S\Rightarrow(()(\boldsymbol{S}))S\Rightarrow(()(\boldsymbol{S}(S)))S\Rightarrow(()((\boldsymbol{S})))S\Rightarrow(()(()))\boldsymbol{S}\Rightarrow(()(()))(\boldsymbol{S})S\Rightarrow(()(()))()\boldsymbol{S}\Rightarrow(()(()))()</tex>

==Дерево разбора==

{{Определение
|definition=
'''Деревом разбора грамматики''' (англ. ''parse tree'') называется дерево, в вершинах которого записаны терминалы или нетерминалы. Все вершины, помеченные терминалами, являются листьями. Все вершины, помеченные нетерминалами, имеют детей. Дети вершины, в которой записан нетерминал, соответствуют раскрытию нетерминала по одному любому правилу (в левой части которого стоит этот нетерминал) и упорядочены так же, как в правой части этого правила.
}}
{{Определение
|definition=
'''Крона''' дерева разбора {{---}} множество терминальных символов, упорядоченное в соответствии с номерами их достижения при обходе дерева в глубину из корня. Крона дерева разбора представляет из себя слово языка, которое выводит это дерево.
}}
 
Построим дерево разбора скобочной последовательности из примера. 
[[Файл:ParsingTree.png|350px]]

==Однозначные грамматики==

{{Определение
|definition=
Грамматика называется '''однозначной''' (англ. ''unambiguous grammar''), если у каждого слова имеется не более одного дерева разбора в этой грамматике.
}}

{{Лемма
|id=lemma-
|statement=
Пусть <tex>\Gamma</tex> {{---}} однозначная грамматика. Тогда <tex>\forall \omega \in \mathbb{L}(\Gamma)</tex> существует ровно один левосторонний (правосторонний) вывод.
|proof=
Очевидно, что по дереву разбора однозначно восстанавливается левосторонний(правосторонний) вывод. Поскольку каждое слово из языка выводится только одним деревом разбора, то существует только один левосторонний(правосторонний) вывод этого слова.
}}
 
{{Утверждение
|statement = Грамматика из примера не является однозначной.
|proof =
Выше уже было построено дерево разбора для слова <tex>"(()(()))()"</tex>.
Построим еще одно дерево разбора для данного слова.

Например, оно будет выглядеть так:

[[Файл:Parsetree2.png|300px]]
Таким образом, существует слово, у которого есть более одного дерева разбора в данной грамматике <tex>\Rightarrow</tex> эта грамматика не является однозначной.
}}
 
{{Утверждение
|statement = Существуют языки, которые можно задать одновременно как однозначными, так и неоднозначными грамматиками.
|proof =
Для доказательства достаточно привести однозначную грамматику для языка правильных скобочных последовательностей (неоднозначной грамматикой для данного языка является грамматика из примера выше).

Рассмотрим грамматику:

<tex>"("</tex> и <tex>")"</tex> {{---}} терминальные символы;

<tex>S</tex> {{---}} стартовый нетерминал;

Правила: 
1) <tex>S\rightarrow (S)S</tex> 
2) <tex>S\rightarrow \varepsilon</tex> 

Покажем, что эта грамматика однозначна.

Для этого, используя индукцию, докажем, что для любого слова <tex>\omega</tex>, являющегося правильной скобочной последовательностью, в данной грамматике существует только одно дерево разбора.

'''База:''' Если <tex>\omega=\varepsilon</tex>, то оно выводится только по второму правилу <tex>\Rightarrow</tex> для него существует единственное дерево разбора.

'''Переход:''' Пусть <tex>\left\vert \omega \right\vert=n</tex> и <tex>\forall \upsilon</tex>: <tex>\left\vert \upsilon \right\vert < n</tex> и <tex>\upsilon</tex> {{---}} правильная скобочная последовательность <tex>\exists!</tex> дерево разбора.

Найдем в слове <tex>\omega</tex> минимальный индекс <tex>i \neq 0</tex> такой, что слово <tex>\omega[0..i]</tex> является правильной скобочной последовательностью. Так как <tex>i \neq 0</tex> минимальный, то <tex>\omega[0..i]=(\alpha)</tex>. Из того, что <tex>\omega</tex> является правильной скобочной последовательностью <tex>\Rightarrow</tex> <tex>\alpha</tex> и <tex>\beta=\omega[i+1..n-1]</tex> {{---}} правильные скобочные последовательности, при этом <tex>\left\vert \alpha \right\vert<n</tex> и <tex>\left\vert \beta \right\vert<n \Rightarrow</tex> по индукционному предположению предположению у <tex>\alpha</tex> и <tex>\beta</tex> существуют единственные деревья разбора.

Если мы покажем, что из части <tex>(S)</tex> первого правила можно вывести только слово <tex>(\alpha)</tex>, то утверждение будет доказано (так как из первой части первого правила выводится <tex>\alpha</tex>, а из второй только <tex>\beta</tex> и для каждого из них по предположению существуют единственные деревья разбора).

Пусть из <tex>(S)</tex> была выведена часть слова <tex>\omega[0..j]=(\gamma)</tex>, где <tex>j < i</tex>, при этом <tex>\gamma</tex> является правильной скобочной последовательностью, но тогда как минимальный индекс мы должны были выбрать <tex>j</tex>, а не <tex>i</tex> {{---}} противоречие.

Аналогично из <tex>(S)</tex> не может быть выведена часть слова <tex>\omega[0..j]</tex>, где <tex>j > i</tex>, потому что тогда <tex>\omega[0..i]=(\alpha)</tex> не будет правильной скобочной последовательностью, так как в позиции <tex>i-1</tex> баланс скобок будет отрицательный.

Значит, из <tex>(S)</tex> была выведена часть слова <tex>\omega[0..i] \Rightarrow \omega</tex> имеет единственное дерево разбора <tex>\Rightarrow</tex> данная грамматика однозначная.

Таким образом, для языка правильных скобочных последовательностей мы привели пример как однозначной, так и неоднозначной грамматики.
}}

Однако, есть КС-языки, для которых не существует однозначных КС-грамматик. Такие языки и грамматики их порождающие называют [[Существенно неоднозначные языки|''существенно неоднозначными'']].

==См. также==
* [[Формальные грамматики]]
* [[Иерархия Хомского формальных грамматик]]
* [[Замкнутость КС-языков относительно различных операций]]
* [[Существенно неоднозначные языки]]

== Источники информации ==
* [[wikipedia:Context-free grammar | Wikipedia {{---}} Context-free grammar]]
* [[wikipedia:ru:Контекстно-свободная грамматика | Википедия {{---}} Контекстно-свободная грамматика]]
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' {{---}} '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора

2014-12-09T22:57:21Z

Maryann: /* Однозначные грамматики */

==Основные определения==
{{Определение
|id=csgrammar
|definition=
'''Контекстно-свободной грамматикой''' (англ. ''сontext-free grammar'') называется грамматика, у которой в левых частях всех правил стоят только одиночные нетерминалы.
}}
{{Определение
|definition=
'''Контекстно-свободный язык''' (англ. ''context-free language'') {{---}} язык, задаваемый контекстно-свободной грамматикой.
}}

==Лево- и правосторонний вывод слова==

{{Определение
|definition=
'''Выводом слова''' (англ. ''derivation of a word'') <tex>\alpha</tex> называется последовательность строк, состоящих из терминалов и нетерминалов. Первая строка последовательности состоит из одного стартового нетерминала. Каждая последующая строка получена из предыдущей путем замены любого нетерминала по одному (любому) из правил, а последней строкой в последовательности является слово <tex>\alpha</tex>.
}}
'''Пример:'''

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

<tex>"("</tex> и <tex>")"</tex> {{---}} терминальные символы;

<tex>S</tex> {{---}} стартовый нетерминал;

Правила: 
<tex>S\rightarrow (S)S</tex> 
<tex>S\rightarrow S(S)</tex> 
<tex>S\rightarrow \varepsilon</tex> 
Выведем слово <tex>"(()(()))()"</tex>: 
<tex>\boldsymbol{S}\Rightarrow (S)\boldsymbol{S} \Rightarrow (S)(\boldsymbol{S})S\Rightarrow(S)()\boldsymbol{S}\Rightarrow(\boldsymbol{S})()\Rightarrow(\boldsymbol{S}(S))()\Rightarrow(S(S)(\boldsymbol{S}))()\Rightarrow(S(S)(\boldsymbol{S}(S)))()\Rightarrow (S(\boldsymbol{S})((S)))()\Rightarrow(\boldsymbol{S}()((S)))()\Rightarrow(()((\boldsymbol{S})))()\Rightarrow(()(()))()</tex>

{{Определение
|definition=
'''Левосторонний вывод слова''' (англ. ''leftmost derivation'')<tex>\alpha</tex> {{---}} вывод, где каждая последующая строка получена из предыдущей путем замены по одному из правил самого левого встречающегося в строке нетерминала.
}}

{{Определение
|definition=
'''Правосторонним выводом слова''' (англ. '' rightmost derivation'') <tex>\alpha</tex> {{---}} вывод, где каждая последующая строка получена из предыдущей путем замены по одному из правил самого правого встречающегося в строке нетерминала.
}}
Рассмотрим левосторонний вывод скобочной последовательности из примера: 
<tex>\boldsymbol{S}\Rightarrow (\boldsymbol{S})S \Rightarrow ((\boldsymbol{S})S)S\Rightarrow (()\boldsymbol{S})S\Rightarrow(()\boldsymbol{S}(S))S\Rightarrow(()(\boldsymbol{S}))S\Rightarrow(()(\boldsymbol{S}(S)))S\Rightarrow(()((\boldsymbol{S})))S\Rightarrow(()(()))\boldsymbol{S}\Rightarrow(()(()))(\boldsymbol{S})S\Rightarrow(()(()))()\boldsymbol{S}\Rightarrow(()(()))()</tex>

==Дерево разбора==

{{Определение
|definition=
'''Деревом разбора грамматики''' (англ. ''parse tree'') называется дерево, в вершинах которого записаны терминалы или нетерминалы. Все вершины, помеченные терминалами, являются листьями. Все вершины, помеченные нетерминалами, имеют детей. Дети вершины, в которой записан нетерминал, соответствуют раскрытию нетерминала по одному любому правилу (в левой части которого стоит этот нетерминал) и упорядочены так же, как в правой части этого правила.
}}
{{Определение
|definition=
'''Крона''' дерева разбора {{---}} множество терминальных символов, упорядоченное в соответствии с номерами их достижения при обходе дерева в глубину из корня. Крона дерева разбора представляет из себя слово языка, которое выводит это дерево.
}}
 
Построим дерево разбора скобочной последовательности из примера. 
[[Файл:ParsingTree.png|350px]]

==Однозначные грамматики==

{{Определение
|definition=
Грамматика называется '''однозначной''' (англ. ''unambiguous grammar''), если у каждого слова имеется не более одного дерева разбора в этой грамматике.
}}

{{Лемма
|id=lemma-
|statement=
Пусть <tex>\Gamma</tex> {{---}} однозначная грамматика. Тогда <tex>\forall \omega \in \mathbb{L}(\Gamma)</tex> существует ровно один левосторонний (правосторонний) вывод.
|proof=
Очевидно, что по дереву разбора однозначно восстанавливается левосторонний(правосторонний) вывод. Поскольку каждое слово из языка выводится только одним деревом разбора, то существует только один левосторонний(правосторонний) вывод этого слова.
}}
 
{{Утверждение
|statement = Грамматика из примера не является однозначной.
|proof =
Выше уже было построено дерево разбора для слова <tex>"(()(()))()"</tex>.
Построим еще одно дерево разбора для данного слова.

Например, оно будет выглядеть так:

[[Файл:Parsetree2.png|300px]]
Таким образом, существует слово, у которого есть более одного дерева разбора в данной грамматике <tex>\Rightarrow</tex> эта грамматика не является однозначной.
}}
 
{{Утверждение
|statement = Существуют языки, которые можно задать одновременно как однозначными, так и неоднозначными грамматиками.
|proof =
Для доказательства достаточно привести однозначную грамматику для языка правильных скобочных последовательностей (неоднозначной грамматикой для данного языка является грамматика из примера выше).

Рассмотрим грамматику:

<tex>"("</tex> и <tex>")"</tex> {{---}} терминальные символы;

<tex>S</tex> {{---}} стартовый нетерминал;

Правила: 
1) <tex>S\rightarrow (S)S</tex> 
2) <tex>S\rightarrow \varepsilon</tex> 

Покажем, что эта грамматика однозначна.

Для этого, используя индукцию, докажем, что для любого слова <tex>\omega</tex>, являющегося правильной скобочной последовательностью, в данной грамматике существует только одно дерево разбора.

'''База:''' Если <tex>\omega=\varepsilon</tex>, то оно выводится только по второму правилу <tex>\Rightarrow</tex> для него существует единственное дерево разбора.

'''Переход:''' Пусть <tex>\left\vert \omega \right\vert=n</tex> и <tex>\forall \upsilon</tex>: <tex>\left\vert \upsilon \right\vert < n</tex> и <tex>\upsilon</tex> {{---}} правильная скобочная последовательность <tex>\exists!</tex> дерево разбора.

Найдем в слове <tex>\omega</tex> минимальный индекс <tex>i \neq 0</tex> такой, что слово <tex>\omega[0..i]</tex> является правильной скобочной последовательностью. Так как <tex>i \neq 0</tex> минимальный, то <tex>\omega[0..i]=(\alpha)</tex>. Из того, что <tex>\omega</tex> является правильной скобочной последовательностью <tex>\Rightarrow</tex> <tex>\alpha</tex> и <tex>\beta=\omega[i+1..n-1]</tex> {{---}} правильные скобочные последовательности, при этом <tex>\left\vert \alpha \right\vert<n</tex> и <tex>\left\vert \beta \right\vert<n \Rightarrow</tex> по индукционному предположению предположению у <tex>\alpha</tex> и <tex>\beta</tex> существуют единственные деревья разбора.

Если мы покажем, что из части <tex>(S)</tex> первого правила можно вывести только слово <tex>(\alpha)</tex>, то утверждение будет доказано (так как из первой части первого правила выводится <tex>\alpha</tex>, а из второй только <tex>\beta</tex> и для каждого из них по предположению существуют единственные деревья разбора).

Пусть из <tex>(S)</tex> была выведена часть слова <tex>\omega[0..j]=(\gamma)</tex>, где <tex>j < i</tex>, при этом <tex>\gamma</tex> является правильной скобочной последовательностью, но тогда как минимальный индекс мы должны были выбрать <tex>j</tex>, а не <tex>i</tex> {{---}} противоречие.

Аналогично из <tex>(S)</tex> не может быть выведена часть слова <tex>\omega[0..j]</tex>, где <tex>j > i</tex>, потому что тогда <tex>\omega[0..i]=(\alpha)</tex> не будет правильной скобочной последовательностью, так как в позиции <tex>i-1</tex> баланс скобок будет отрицательный.

Значит, из <tex>(S)</tex> была выведена часть слова <tex>\omega[0..i] \Rightarrow \omega</tex> имеет единственное дерево разбора <tex>\Rightarrow</tex> данная грамматика однозначная.

Таким образом, для языка правильных скобочных последовательностей мы привели пример как однозначной, так и неоднозначной грамматики.
}}

Однако, есть КС-языки, для которых не существует однозначных КС-грамматик. Такие языки и грамматики их порождающие называют [[Существенно неоднозначные языки|''существенно неоднозначными'']].

==См. также==
* [[Формальные грамматики]]
* [[Иерархия Хомского формальных грамматик]]
* [[Замкнутость КС-языков относительно различных операций]]
* [[Существенно неоднозначные языки]]

== Литература ==
* [[wikipedia:Context-free grammar | Wikipedia {{---}} Context-free grammar]]
* [[wikipedia:ru:Контекстно-свободная грамматика | Википедия {{---}} Контекстно-свободная грамматика]]
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' {{---}} '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора

2014-12-09T22:44:28Z

Maryann: /* Однозначные грамматики */

==Основные определения==
{{Определение
|id=csgrammar
|definition=
'''Контекстно-свободной грамматикой''' (англ. ''сontext-free grammar'') называется грамматика, у которой в левых частях всех правил стоят только одиночные нетерминалы.
}}
{{Определение
|definition=
'''Контекстно-свободный язык''' (англ. ''context-free language'') {{---}} язык, задаваемый контекстно-свободной грамматикой.
}}

==Лево- и правосторонний вывод слова==

{{Определение
|definition=
'''Выводом слова''' (англ. ''derivation of a word'') <tex>\alpha</tex> называется последовательность строк, состоящих из терминалов и нетерминалов. Первая строка последовательности состоит из одного стартового нетерминала. Каждая последующая строка получена из предыдущей путем замены любого нетерминала по одному (любому) из правил, а последней строкой в последовательности является слово <tex>\alpha</tex>.
}}
'''Пример:'''

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

<tex>"("</tex> и <tex>")"</tex> {{---}} терминальные символы;

<tex>S</tex> {{---}} стартовый нетерминал;

Правила: 
<tex>S\rightarrow (S)S</tex> 
<tex>S\rightarrow S(S)</tex> 
<tex>S\rightarrow \varepsilon</tex> 
Выведем слово <tex>"(()(()))()"</tex>: 
<tex>\boldsymbol{S}\Rightarrow (S)\boldsymbol{S} \Rightarrow (S)(\boldsymbol{S})S\Rightarrow(S)()\boldsymbol{S}\Rightarrow(\boldsymbol{S})()\Rightarrow(\boldsymbol{S}(S))()\Rightarrow(S(S)(\boldsymbol{S}))()\Rightarrow(S(S)(\boldsymbol{S}(S)))()\Rightarrow (S(\boldsymbol{S})((S)))()\Rightarrow(\boldsymbol{S}()((S)))()\Rightarrow(()((\boldsymbol{S})))()\Rightarrow(()(()))()</tex>

{{Определение
|definition=
'''Левосторонний вывод слова''' (англ. ''leftmost derivation'')<tex>\alpha</tex> {{---}} вывод, где каждая последующая строка получена из предыдущей путем замены по одному из правил самого левого встречающегося в строке нетерминала.
}}

{{Определение
|definition=
'''Правосторонним выводом слова''' (англ. '' rightmost derivation'') <tex>\alpha</tex> {{---}} вывод, где каждая последующая строка получена из предыдущей путем замены по одному из правил самого правого встречающегося в строке нетерминала.
}}
Рассмотрим левосторонний вывод скобочной последовательности из примера: 
<tex>\boldsymbol{S}\Rightarrow (\boldsymbol{S})S \Rightarrow ((\boldsymbol{S})S)S\Rightarrow (()\boldsymbol{S})S\Rightarrow(()\boldsymbol{S}(S))S\Rightarrow(()(\boldsymbol{S}))S\Rightarrow(()(\boldsymbol{S}(S)))S\Rightarrow(()((\boldsymbol{S})))S\Rightarrow(()(()))\boldsymbol{S}\Rightarrow(()(()))(\boldsymbol{S})S\Rightarrow(()(()))()\boldsymbol{S}\Rightarrow(()(()))()</tex>

==Дерево разбора==

{{Определение
|definition=
'''Деревом разбора грамматики''' (англ. ''parse tree'') называется дерево, в вершинах которого записаны терминалы или нетерминалы. Все вершины, помеченные терминалами, являются листьями. Все вершины, помеченные нетерминалами, имеют детей. Дети вершины, в которой записан нетерминал, соответствуют раскрытию нетерминала по одному любому правилу (в левой части которого стоит этот нетерминал) и упорядочены так же, как в правой части этого правила.
}}
{{Определение
|definition=
'''Крона''' дерева разбора {{---}} множество терминальных символов, упорядоченное в соответствии с номерами их достижения при обходе дерева в глубину из корня. Крона дерева разбора представляет из себя слово языка, которое выводит это дерево.
}}
 
Построим дерево разбора скобочной последовательности из примера. 
[[Файл:ParsingTree.png|350px]]

==Однозначные грамматики==

{{Определение
|definition=
Грамматика называется '''однозначной''' (англ. ''unambiguous grammar''), если у каждого слова имеется не более одного дерева разбора в этой грамматике.
}}

{{Лемма
|id=lemma-
|statement=
Пусть <tex>\Gamma</tex> {{---}} однозначная грамматика. Тогда <tex>\forall \omega \in \mathbb{L}(\Gamma)</tex> существует ровно один левосторонний (правосторонний) вывод.
|proof=
Очевидно, что по дереву разбора однозначно восстанавливается левосторонний(правосторонний) вывод. Поскольку каждое слово из языка выводится только одним деревом разбора, то существует только один левосторонний(правосторонний) вывод этого слова.
}}
 
{{Утверждение
|statement = Грамматика из примера не является однозначной.
|proof =
Выше уже было построено дерево разбора для слова <tex>"(()(()))()"</tex>.
Построим еще одно дерево разбора для данного слова.

Например, оно будет выглядеть так:

[[Файл:Parsetree2.png|300px]]
Таким образом, существует слово, у которого есть более одного дерева разбора в данной грамматике <tex>\Rightarrow</tex> эта грамматика не является однозначной.
}}
 
{{Утверждение
|statement = Существуют языки, которые можно задать одновременно как однозначными, так и неоднозначными грамматиками.
|proof =
Для доказательства достаточно привести однозначную грамматику для языка правильных скобочных последовательностей (неоднозначной грамматикой для данного языка является грамматика из примера выше).

Рассмотрим грамматику:

<tex>"("</tex> и <tex>")"</tex> {{---}} терминальные символы;

<tex>S</tex> {{---}} стартовый нетерминал;

Правила: 
1) <tex>S\rightarrow (S)S</tex> 
2) <tex>S\rightarrow \varepsilon</tex> 

Покажем, что эта грамматика однозначна.

Для этого, используя индукцию, докажем, что для любого слова <tex>\omega</tex>, являющегося правильной скобочной последовательностью, в данной грамматике существует только одно дерево разбора.

'''База:''' Если <tex>\omega=\varepsilon</tex>, то оно выводится только по второму правилу <tex>\Rightarrow</tex> для него существует единственное дерево разбора.

'''Переход:''' Пусть <tex>\left\vert \omega \right\vert=n</tex> и <tex>\forall \upsilon</tex>: <tex>\left\vert \upsilon \right\vert < n</tex> и <tex>\upsilon</tex> {{---}} правильная скобочная последовательность <tex>\exists!</tex> дерево разбора.

Найдем в слове <tex>\omega</tex> минимальный индекс <tex>i \neq 0</tex> такой, что слово <tex>\omega[0..i]</tex> является правильной скобочной последовательностью. Так как <tex>i \neq 0</tex> минимальный, то <tex>\omega[0..i]=(\alpha)</tex>. Из того, что <tex>\omega</tex> является правильной скобочной последовательностью <tex>\Rightarrow</tex> <tex>\alpha</tex> и <tex>\beta=\omega[i+1..n-1]</tex> {{---}} правильные скобочные последовательности, при этом <tex>\left\vert \alpha \right\vert<n</tex> и <tex>\left\vert \beta \right\vert<n \Rightarrow</tex> по индукционному предположению предположению у <tex>\alpha</tex> и <tex>\beta</tex> существуют единственные деревья разбора.

Если мы покажем, что из части <tex>(S)</tex> первого правила можно вывести только слово <tex>(\alpha)</tex>, то утверждение будет доказано (так как из первой части первого правила выводится <tex>\alpha</tex>, а из второй только <tex>\beta</tex> и каждое из них по предположению выводится однозначно).

Пусть из <tex>(S)</tex> была выведена часть слова <tex>\omega[0..j]=(\gamma)</tex>, где <tex>j < i</tex>, при этом <tex>\gamma</tex> является правильной скобочной последовательностью, но тогда как минимальный индекс мы должны были выбрать <tex>j</tex>, а не <tex>i</tex> {{---}} противоречие.

Аналогично из <tex>(S)</tex> не может быть выведена часть слова <tex>\omega[0..j]</tex>, где <tex>j > i</tex>, потому что тогда <tex>\alpha</tex> не будет правильной скобочной последовательностью, так как в позиции <tex>i</tex> баланс скобок будет отрицательный.

Значит, из <tex>(S)</tex> была выведена часть слова <tex>\omega[0..i] \Rightarrow \omega</tex> имеет единственное дерево разбора <tex>\Rightarrow</tex> данная грамматика однозначная.

Таким образом, для языка правильных скобочных последовательностей мы привели пример как однозначной, так и неоднозначной грамматики.
}}

Однако, есть КС-языки, для которых не существует однозначных КС-грамматик. Такие языки и грамматики их порождающие называют [[Существенно неоднозначные языки|''существенно неоднозначными'']].

==См. также==
* [[Формальные грамматики]]
* [[Иерархия Хомского формальных грамматик]]
* [[Замкнутость КС-языков относительно различных операций]]
* [[Существенно неоднозначные языки]]

== Литература ==
* [[wikipedia:Context-free grammar | Wikipedia {{---}} Context-free grammar]]
* [[wikipedia:ru:Контекстно-свободная грамматика | Википедия {{---}} Контекстно-свободная грамматика]]
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' {{---}} '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора

2014-12-09T20:39:48Z

Файл:ParsingTree.png

2014-11-24T22:55:59Z

Maryann:

Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора

2014-11-24T12:05:56Z

Maryann:

{{Определение
|id=csgrammar
|definition=
'''Контекстно-свободной грамматикой''' (англ. ''сontext-free grammar'') называется грамматика, у которой в левых частях всех правил стоят только одиночные нетерминалы.
}}
{{Определение
|definition=
'''Контекстно-свободный язык''' (англ. ''context-free language'') {{---}} язык, задаваемый контекстно-свободной грамматикой.
}}

{{Определение
|definition=
'''Выводом слова''' <tex>\alpha</tex> называется последовательность строк, состоящих из терминалов и нетерминалов. Первая строка последовательности состоит из одного стартового нетерминала. Каждая последующая строка получена из предыдущей путем замены любого нетерминала по одному (любому) из правил, а последней строкой в последовательности является слово <tex>\alpha</tex>.
}}

Рассмотрим на примере грамматики, выводящей все правильные скобочные последовательности.

Терминальные символы {{---}} <tex>"("</tex> и <tex>")"</tex>;

<tex>S</tex> {{---}} стартовый нетерминал;

Правила: 
<tex>S\rightarrow (S)S</tex> 
<tex>S\rightarrow S(S)</tex> 
<tex>S\rightarrow \varepsilon</tex> 
Выведем слово <tex>"(()(()))()"</tex>: 
<tex>\boldsymbol{S}\Rightarrow (S)\boldsymbol{S} \Rightarrow (S)(\boldsymbol{S})S\Rightarrow(S)()\boldsymbol{S}\Rightarrow(\boldsymbol{S})()\Rightarrow(\boldsymbol{S}(S))()\Rightarrow(S(S)(\boldsymbol{S}))()\Rightarrow(S(S)(\boldsymbol{S}(S)))()\Rightarrow (S(\boldsymbol{S})((S)))()\Rightarrow(\boldsymbol{S}()((S)))()\Rightarrow(()((\boldsymbol{S})))()\Rightarrow(()(()))()</tex>

{{Определение
|definition=
'''Левосторонним выводом слова <tex>\alpha</tex>''' называется такой его вывод, что каждая последующая строка получена из предыдущей путем замены по одному из правил самого левого встречающегося в строке нетерминала.
}}

{{Определение
|definition=
'''Правосторонним выводом слова <tex>\alpha</tex>''' называется такой его вывод, что каждая последующая строка получена из предыдущей путем замены по одному из правил самого правого встречающегося в строке нетерминала.
}}
 
Рассмотрим левосторонний вывод нашей скобочной последовательности: 
<tex>\boldsymbol{S}\Rightarrow (\boldsymbol{S})S \Rightarrow ((\boldsymbol{S})S)S\Rightarrow (()\boldsymbol{S})S\Rightarrow(()\boldsymbol{S}(S))S\Rightarrow(()(\boldsymbol{S}))S\Rightarrow(()(\boldsymbol{S}(S)))S\Rightarrow(()((\boldsymbol{S})))S\Rightarrow(()(()))\boldsymbol{S}\Rightarrow(()(()))(\boldsymbol{S})S\Rightarrow(()(()))()\boldsymbol{S}\Rightarrow(()(()))()</tex>

{{Определение
|definition=
'''Деревом разбора грамматики''' (англ. ''parse tree'') называется дерево, в вершинах которого записаны терминалы или нетерминалы, а дети вершины, в которой записан нетерминал, соответствуют раскрытию нетерминала по одному любому правилу, в левой части которого стоит этот нетерминал, и упорядочены так же, как в правой части этого правила. Все вершины, помеченные терминалами, являются листьями. Все вершины, помеченные нетерминалами, имеют детей.
}}
{{Определение
|definition=
'''Крона''' дерева разбора {{---}} множество терминальных символов, упорядоченное в соответствии с номерами их достижения при обходе дерева в глубину из корня.
}}
Крона дерева разбора представляет из себя слово языка, которое выводит это дерево. 
Рассмотрим, как будет выглядеть дерево разбора нашей скобочной последовательности. 
[[Файл:derivation_tree.png]]
{{Определение
|definition=
Грамматика называется '''однозначной''' (англ. ''unambiguous grammar''), если у каждого слова имеется не более одного дерева разбора в этой грамматике.
}}

{{Лемма
|id=lemma-
|statement=
Пусть <tex>\Gamma</tex> {{---}} однозначная грамматика. Тогда <tex>\forall \omega \in \mathbb{L}(\Gamma)</tex> существует ровно один левосторонний (правосторонний) вывод <tex>\omega</tex>.
|proof=
Очевидно, что по дереву разбора однозначно восстанавливается левосторонний вывод. Поскольку каждое слова из языка выводится только одним деревом разбора, то существует только один левосторонний вывод этого слова.
}}

== Литература ==
* Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений.

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]

2014-06-05T18:40:07Z

Maryann: /* Трансверсальный матроид */

Примеры матроидов

2014-06-05T18:38:19Z

Maryann: Отмена правки 37673 участника Maryann (обсуждение)