3622
правки
Изменения
Нет описания правки
* все правила в <tex>P'</tex> имеет вид <tex>\alpha \rightarrow \beta</tex> где <tex>\alpha \in (N')^+</tex> и <tex>\beta \in (N')^*</tex> или <tex>A \rightarrow a</tex>, где <tex>A \in N', a \in \Sigma</tex>,
* <tex>L(G') = L(G)</tex>
Кроме того, если <tex>G </tex> контекстно-свободна или контекстно-зависима, то и <tex>G'</tex> будет соответственно контекстно-свободной или контекстно-зависимой.
|proof = Каждому терминалу <tex>a</tex> поставим в соотвествие новый символ <tex>a'</tex>, которого нет в <tex>N \cup \Sigma</tex>, такой что <tex>a' \neq b'</tex> для разных терминалов <tex>a</tex> и <tex>b</tex>.
