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

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 69: Строка 69:
 
:Поскольку это дерево является деревом разбора, <tex>A \rightarrow \omega</tex> должно быть продукцией. Таким образом, <tex>A \Rightarrow_{lm} \omega</tex> есть одношаговое левое порождение <tex>\omega</tex> из <tex>A</tex>.
 
:Поскольку это дерево является деревом разбора, <tex>A \rightarrow \omega</tex> должно быть продукцией. Таким образом, <tex>A \Rightarrow_{lm} \omega</tex> есть одношаговое левое порождение <tex>\omega</tex> из <tex>A</tex>.
  
'''Индукционный переход:''' Существует корень с отметкой <tex>A</tex> и сыновьями, отмеченными слева направо <tex>X_1X_2 \ldots X_k</tex>. Символы <tex>X</tex> могут быть как терминалами, так и переменными.
+
'''Индукционный переход:''' Существует корень с отметкой <tex>A</tex> и сыновьями, отмеченными слева направо <tex>X_1X_2 \dots X_k</tex>. Символы <tex>X</tex> могут быть как терминалами, так и переменными.
 
# Если <tex>X_i</tex> — терминал, то определим <tex>\omega_i</tex> как цепочку, состоящую из одного <tex>X_i</tex>.
 
# Если <tex>X_i</tex> — терминал, то определим <tex>\omega_i</tex> как цепочку, состоящую из одного <tex>X_i</tex>.
 
# Если <tex>X_i</tex> — переменная, то она должна быть корнем некоторого поддерева с терминальной кроной, которую обозначим <tex>\omega_i</tex>. Заметим, что в этом случае высота поддерева меньше <tex>n</tex>, поэтому к нему применимо предположение индукции. Следовательно, существует левое порождение <tex>X_i \Rightarrow^{*}_{lm} \omega_i</tex>.
 
# Если <tex>X_i</tex> — переменная, то она должна быть корнем некоторого поддерева с терминальной кроной, которую обозначим <tex>\omega_i</tex>. Заметим, что в этом случае высота поддерева меньше <tex>n</tex>, поэтому к нему применимо предположение индукции. Следовательно, существует левое порождение <tex>X_i \Rightarrow^{*}_{lm} \omega_i</tex>.
  
Заметим, что <tex>\omega = \omega_1\omega_2 \ldots \omega_k</tex>.
+
Заметим, что <tex>\omega = \omega_1\omega_2 \dots \omega_k</tex>.
 
Построим левое порождение цепочки <tex>\omega</tex> следующим образом:
 
Построим левое порождение цепочки <tex>\omega</tex> следующим образом:
:Начнем с шага <tex>A \Rightarrow_{lm} X_1X_2\ldots X_k</tex>.
+
:Начнем с шага <tex>A \Rightarrow_{lm} X_1X_2\dots X_k</tex>.
:Затем для <tex>i = 1, 2, \ldots, k \ </tex> покажем, что имеет место следующее порождение: <tex>A \Rightarrow^{*}_{lm} \omega_1\omega_2\ldots\omega_iX_{i+1}X_{i+2}\ldots X_k</tex>
+
:Затем для <tex>i = 1, 2, \dots, k \ </tex> покажем, что имеет место следующее порождение: <tex>A \Rightarrow^{*}_{lm} \omega_1\omega_2\dots\omega_iX_{i+1}X_{i+2}\dots X_k</tex>
  
 
Данное доказательство использует в действительности еще одну индукцию, на этот раз по <tex>i</tex>.
 
Данное доказательство использует в действительности еще одну индукцию, на этот раз по <tex>i</tex>.
Для базиса <tex>i = 0</tex> мы уже знаем, что <tex>A \Rightarrow_{lm} X_1X_2\ldots X_k</tex>.
+
Для базиса <tex>i = 0</tex> мы уже знаем, что <tex>A \Rightarrow_{lm} X_1X_2\dots X_k</tex>.
  
Для индукции предположим, что существует следующее порождение: <tex>A \Rightarrow^{*}_{lm} \omega_1\omega_2\ldots\omega_{i–1}X_iX_{i+1}\ldots X_k</tex>
+
Для индукции предположим, что существует следующее порождение: <tex>A \Rightarrow^{*}_{lm} \omega_1\omega_2\dots\omega_{i–1}X_iX_{i+1}\dots X_k</tex>
  
# Если <tex>X_i</tex> — терминал, то не делаем ничего, но в дальнейшем рассматриваем <tex>X_i</tex> как терминальную цепочку <tex>\omega_i</tex>. Таким образом, приходим к существованию следующего порождения. <tex>A \Rightarrow^{*}_{lm} \omega_1\omega_2\ldots\omega_iX_{i+1}X_{i+2}\ldots X_k</tex>
+
# Если <tex>X_i</tex> — терминал, то не делаем ничего, но в дальнейшем рассматриваем <tex>X_i</tex> как терминальную цепочку <tex>\omega_i</tex>. Таким образом, приходим к существованию следующего порождения. <tex>A \Rightarrow^{*}_{lm} \omega_1\omega_2\dots\omega_iX_{i+1}X_{i+2}\dots X_k</tex>
# Если <tex>X_i</tex> является переменной, то продолжаем порождением <tex>\omega_i</tex> из <tex>X_i</tex> в контексте уже построенного порождения. Таким образом, если этим порождением является: <tex>X_i \Rightarrow_{lm} \alpha_1 \Rightarrow_{lm} \alpha_2\ldots \Rightarrow_{lm} \omega_i</tex>, то продолжаем следующими порождениями:  
+
# Если <tex>X_i</tex> является переменной, то продолжаем порождением <tex>\omega_i</tex> из <tex>X_i</tex> в контексте уже построенного порождения. Таким образом, если этим порождением является: <tex>X_i \Rightarrow_{lm} \alpha_1 \Rightarrow_{lm} \alpha_2\dots \Rightarrow_{lm} \omega_i</tex>, то продолжаем следующими порождениями:  
  
::<tex>\omega_1\omega_2\ldots\omega_{i–1}X_iX_{i+1}\ldots X_k \Rightarrow_{lm}</tex>
+
::<tex>\omega_1\omega_2\dots\omega_{i–1}X_iX_{i+1}\dots X_k \Rightarrow_{lm}</tex>
  
::<tex>\omega_1\omega_2\ldots\omega_{i–1}\alpha_1X_{i+1}\ldots X_k \Rightarrow_{lm}</tex>
+
::<tex>\omega_1\omega_2\dots\omega_{i–1}\alpha_1X_{i+1}\dots X_k \Rightarrow_{lm}</tex>
  
::<tex>\omega_1\omega_2\ldots\omega_{i–1}\alpha_2X_{i+1}\ldots X_k  \Rightarrow_{lm}</tex>
+
::<tex>\omega_1\omega_2\dots\omega_{i–1}\alpha_2X_{i+1}\dots X_k  \Rightarrow_{lm}</tex>
  
::<tex>\ldots</tex>
+
::<tex>\dots</tex>
  
::<tex>\omega_1\omega_2\ldots\omega_iX_{i+1}X_{i+2}\ldots X_k</tex>
+
::<tex>\omega_1\omega_2\dots\omega_iX_{i+1}X_{i+2}\dots X_k</tex>
  
Результатом является порождение <tex>A \Rightarrow^{*}_{lm} \omega_1\omega_2\ldots\omega_iX_{i+1}X_{i+2}\ldots X_k</tex>.
+
Результатом является порождение <tex>A \Rightarrow^{*}_{lm} \omega_1\omega_2\dots\omega_iX_{i+1}X_{i+2}\dots X_k</tex>.
 
Когда <tex>i = k</tex>, результат представляет собой левое порождение <tex>\omega</tex> из <tex>A</tex>.
 
Когда <tex>i = k</tex>, результат представляет собой левое порождение <tex>\omega</tex> из <tex>A</tex>.
 
}}
 
}}

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)