Редактирование: Совпадение множества языков МП-автоматов и контекстно-свободных языков

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 30: Строка 30:
 
=== Пример ===
 
=== Пример ===
 
Поскольку доказательство теоремы конструктивно, то используя правила перехода, описанные в ней, можно преобразовать любую КС-грамматику в МП-автомат. Рассмотрим грамматику слов над алфавитом <tex>\{0, 1\}</tex>, в которых одинаковое количество нулей и единиц:
 
Поскольку доказательство теоремы конструктивно, то используя правила перехода, описанные в ней, можно преобразовать любую КС-грамматику в МП-автомат. Рассмотрим грамматику слов над алфавитом <tex>\{0, 1\}</tex>, в которых одинаковое количество нулей и единиц:
: <tex> S \rightarrow 0S1 </tex>
+
: <tex> S \rightarrow 0S1 </tex>;
: <tex> S \rightarrow 1S0 </tex>
+
: <tex> S \rightarrow 1S0 </tex>;
: <tex> S \rightarrow \varepsilon </tex>
+
: <tex> S \rightarrow \varepsilon </tex>.
 
Множеством терминалов является <tex>\Sigma = \{0, 1\}</tex>, а нетерминалов {{---}} <tex>N = \{S\}</tex>. Таким образом, стековый алфавит состоит из <tex>0, 1, S</tex>. Функция переходов <tex>\delta</tex> определена следующим образом:
 
Множеством терминалов является <tex>\Sigma = \{0, 1\}</tex>, а нетерминалов {{---}} <tex>N = \{S\}</tex>. Таким образом, стековый алфавит состоит из <tex>0, 1, S</tex>. Функция переходов <tex>\delta</tex> определена следующим образом:
  
: <tex>\delta(q, \varepsilon, S) = \{(q, 0S1), (q, 1S0), (q, \varepsilon)\}</tex> (в соответствии с первым пунктом построения <tex>\delta</tex>)
+
: <tex>\delta(q, \varepsilon, S) = \{(q, 0S1), (q, 1S0), (q, \varepsilon)\}</tex> (в соответствии с первым пунктом построения <tex>\delta</tex>);
  
: <tex> \delta(q, 0, 0)= \{(q, \varepsilon)\}</tex>; <tex> \delta(q, 1, 1)= \{(q, \varepsilon)\}</tex> (в соответствии со вторым пунктом построения <tex>\delta</tex>)
+
: <tex> \delta(q, 0, 0)= \{(q, \varepsilon)\}</tex>; <tex> \delta(q, 1, 1)= \{(q, \varepsilon)\}</tex> (в соответствии со вторым пунктом построения <tex>\delta</tex>).
  
 
Получившийся автомат:
 
Получившийся автомат:
Строка 71: Строка 71:
 
=== Пример ===
 
=== Пример ===
 
Пусть у нас имеется МП-автомат <tex>A = \langle \{i,e\}, \{Z\}, \{q\}, q, Z, \delta \rangle</tex>, функция <tex>\delta</tex> задана следующим образом:
 
Пусть у нас имеется МП-автомат <tex>A = \langle \{i,e\}, \{Z\}, \{q\}, q, Z, \delta \rangle</tex>, функция <tex>\delta</tex> задана следующим образом:
:<tex>\delta(q, i, Z) = \{(q, ZZ)\}</tex>
+
:<tex>\delta(q, i, Z) = \{(q, ZZ)\}</tex>,
:<tex>\delta(q, e, Z) = \{(q, \varepsilon)\}</tex>
+
:<tex>\delta(q, e, Z) = \{(q, \varepsilon)\}</tex>.
  
 
[[Файл:Example2.png]]
 
[[Файл:Example2.png]]
Строка 87: Строка 87:
 
* Из <tex>\delta(q,e,Z)=\{(q,\varepsilon)\}</tex> получаем правило вывода <tex>[qZq] \rightarrow e</tex>
 
* Из <tex>\delta(q,e,Z)=\{(q,\varepsilon)\}</tex> получаем правило вывода <tex>[qZq] \rightarrow e</tex>
 
Для удобства тройку <tex>[qZq]</tex> можно заменить символом <tex>A</tex>, в таком случае правила вывода в грамматике будут следующие:
 
Для удобства тройку <tex>[qZq]</tex> можно заменить символом <tex>A</tex>, в таком случае правила вывода в грамматике будут следующие:
:<tex>S \rightarrow A</tex>
+
:<tex>S \rightarrow A</tex>;
:<tex>A \rightarrow iAA</tex>
+
:<tex>A \rightarrow iAA</tex>;
:<tex>A \rightarrow e</tex>
+
:<tex>A \rightarrow e</tex>.
 
Упростим грамматику, заменив <tex>A</tex> на <tex>S</tex> (очевидно, она не поменяется), и получим в результате <tex>\Gamma = \langle\{i,e\}, \{S\}, S, \{S \rightarrow iSS | e\}\rangle</tex>
 
Упростим грамматику, заменив <tex>A</tex> на <tex>S</tex> (очевидно, она не поменяется), и получим в результате <tex>\Gamma = \langle\{i,e\}, \{S\}, S, \{S \rightarrow iSS | e\}\rangle</tex>
  

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

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

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

Шаблоны, используемые на этой странице: