Редактирование: Возможность порождения формальной грамматикой произвольного перечислимого языка

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 41: Строка 41:
 
<tex>A_1 \Rightarrow^* q_o[a_1,a_1][a_2,a_2] \ldots [a_n,a_n]A_2</tex>, где <tex>a_i \in \Sigma</tex> для некоторого <tex>i</tex>.
 
<tex>A_1 \Rightarrow^* q_o[a_1,a_1][a_2,a_2] \ldots [a_n,a_n]A_2</tex>, где <tex>a_i \in \Sigma</tex> для некоторого <tex>i</tex>.
  
Предположим, что <tex>Tm</tex> допускает строку <tex>a_1a_2 \ldots a_n</tex>. Тогда для некоторого <tex>m</tex> <tex>Tm</tex> использует не более, чем <tex>m</tex> ячеек справа от входа. Используя правило <tex>3</tex>, а затем <tex>m</tex> раз правило <tex>4</tex>, и, наконец, правило <tex>5</tex>, имеем:<br>
+
Предположим, что <tex>Tm</tex> допускает строку <tex>a_1a_2 \ldots a_n</tex>. Тогда для некоторого <tex>m</tex> <tex>Tm</tex> использует не более, чем <tex>m</tex> ячеек справа от входа. Используя правило <tex>3</tex>, а затем правило <tex>4</tex> {{---}} <tex>m</tex> раз, и, наконец, правило <tex>5</tex>, имеем:<br>
 
<tex>A_1 \Rightarrow^* q_0[a_1,a_1][a_2,a_2] \ldots [a_n,a_n][e,B]^m</tex>.<br>
 
<tex>A_1 \Rightarrow^* q_0[a_1,a_1][a_2,a_2] \ldots [a_n,a_n][e,B]^m</tex>.<br>
 
Начиная с этого момента могут быть использованы только правила <tex>6</tex> и <tex>7</tex>, пока не сгенерируется допускающее состояние. Отметим, что первые компоненты ленточных символов в <tex>(\Sigma \cup {e}) \times \Gamma</tex> никогда не меняются. Индукцией по числу шагов <tex>Tm</tex> можно показать, что если <tex>(q_0,a_1a_2 \ldots a_n,1)\vdash(q, X_1X_2 \ldots X_S,r)</tex>, то <tex>q_0[a_1,a_1][a_2,a_2] \ldots [a_n,a_n][e,B]^m \Rightarrow [a_1,X_1][a_2,X_2] \ldots [a_{r-1},X_{r-1}]q[a_r,X_r] \ldots [a_{n+m},X_{n+m}]</tex>, где <tex> a_1,a_2,\ldots,a_n \in \Sigma</tex>, <tex>a_{n+1}=a_{n+2}= \ldots =a_{n+m}=e</tex>, <tex>X_1, X_2, \ldots ,X_{n+m} \in \Gamma</tex> и <tex>X_{S+1}=X_{S+2}= \ldots =X_{n+m}=B</tex>.
 
Начиная с этого момента могут быть использованы только правила <tex>6</tex> и <tex>7</tex>, пока не сгенерируется допускающее состояние. Отметим, что первые компоненты ленточных символов в <tex>(\Sigma \cup {e}) \times \Gamma</tex> никогда не меняются. Индукцией по числу шагов <tex>Tm</tex> можно показать, что если <tex>(q_0,a_1a_2 \ldots a_n,1)\vdash(q, X_1X_2 \ldots X_S,r)</tex>, то <tex>q_0[a_1,a_1][a_2,a_2] \ldots [a_n,a_n][e,B]^m \Rightarrow [a_1,X_1][a_2,X_2] \ldots [a_{r-1},X_{r-1}]q[a_r,X_r] \ldots [a_{n+m},X_{n+m}]</tex>, где <tex> a_1,a_2,\ldots,a_n \in \Sigma</tex>, <tex>a_{n+1}=a_{n+2}= \ldots =a_{n+m}=e</tex>, <tex>X_1, X_2, \ldots ,X_{n+m} \in \Gamma</tex> и <tex>X_{S+1}=X_{S+2}= \ldots =X_{n+m}=B</tex>.
Строка 58: Строка 58:
 
Таким образом, <Tex>q_0[a_1,a_1][a_2,a_2] \ldots [a_n,a_n][e,B]^m \Rightarrow [a_1,Y_1]q_2[a_{j_2},Y_{j_2}] \ldots [a_{n+m},Y_{n+m}]</tex>, что доказывает предположение индукции.
 
Таким образом, <Tex>q_0[a_1,a_1][a_2,a_2] \ldots [a_n,a_n][e,B]^m \Rightarrow [a_1,Y_1]q_2[a_{j_2},Y_{j_2}] \ldots [a_{n+m},Y_{n+m}]</tex>, что доказывает предположение индукции.
  
По правилам <tex>8, 9, 10</tex>:<Br>
+
По правилам <tex>8, 9, 10</tex> если <Tex>q \in F</tex>, легко показать что <tex>[a_1,X_1] \ldots q[a_j,X_j] \ldots [a_{n+m},X_{n+m}] \Rightarrow^* a_1a_2 \ldots a_n</tex>.
Eсли <Tex>q \in F</tex>, легко показать что <tex>[a_1,X_1] \ldots q[a_j,X_j] \ldots [a_{n+m},X_{n+m}] \Rightarrow^* a_1a_2 \ldots a_n</tex>.
 
  
 
Таким образом, <tex>G</tex> может генерировать <tex>a_1a_2 \ldots a_n</tex>, если <tex>a_1a_2 \ldots a_n</tex> допускается <tex>Tm</tex>. Таким образом, <tex>L(G)</tex> включает все слова, допускаемые <tex>Tm</tex>. Для завершения доказательства необходимо показать, что все слова из <tex>L(G)</tex> допускаются <Tex>Tm</tex>. Индукцией доказывается, что <tex>A_1 \Rightarrow w</tex> только если <Tex>w</tex> допускается <tex>Tm</tex>.
 
Таким образом, <tex>G</tex> может генерировать <tex>a_1a_2 \ldots a_n</tex>, если <tex>a_1a_2 \ldots a_n</tex> допускается <tex>Tm</tex>. Таким образом, <tex>L(G)</tex> включает все слова, допускаемые <tex>Tm</tex>. Для завершения доказательства необходимо показать, что все слова из <tex>L(G)</tex> допускаются <Tex>Tm</tex>. Индукцией доказывается, что <tex>A_1 \Rightarrow w</tex> только если <Tex>w</tex> допускается <tex>Tm</tex>.

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

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

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