Бюрократы, editor, Администраторы
422
правки
Изменения
Нет описания правки
|statement = Если грамматика <tex>G'</tex> была построена с помощью описанного выше алгоритма по грамматике <tex>G</tex>, то <tex>L(G') = L(G)</tex>.
|proof =
Сначала докажем, что , если не выполнять шаг 5 алгоритма, то получится грамматика <tex>G' : L(G') = L(G) \setminus \lbrace \varepsilon \rbrace </tex>.<br/>
Для этого достаточно доказать, что
<tex>A \underset{G'}{\Rightarrow}^*w</tex> тогда и только тогда, когда <tex>A \underset{G}{\Rightarrow}^*w</tex> и <tex>w \ne \varepsilon</tex> (*).
Пусть <tex>A \underset{G'}{\Rightarrow}^*w</tex> и <tex>w \ne \varepsilon</tex>.<br/>
Докажем индукцией по длине порождения, что <tex>A \underset{G}{\Rightarrow}^*w</tex>.<br/>
'''База'''. Пусть <tex>A \underset{G'}{\Rightarrow}^*w</tex>.<br/>В этом случае в <tex>G'</tex> есть правило <tex>A \rightarrow w</tex>. Согласно конструкции По построению <tex>G'</tex> в <tex>G</tex> есть правило <tex>A \rightarrow \alpha</tex>, причем <tex>\alpha</tex> — цепочка <tex>w</tex>, символы которой, возможно, перемежаются <tex>\varepsilon</tex>-порождающими нетерминалами. Тогда в <tex>G</tex> есть порождения <tex>A \underset{G}{\Rightarrow} \alpha \underset{G}{\Rightarrow}w</tex>.<br/>'''Предположение'''. Пусть из <tex>A \underset{G'}{\Rightarrow}^*w\ne \varepsilon</tex> следует, что <tex>A \underset{G}{\Rightarrow}^*w</tex> и <tex>w \ne \varepsilon</tex> менее, чем за <tex>n</tex> шагов.<br/>
'''Переход'''.
Пусть в порождении <tex>n</tex> шагов, <tex>n > 1</tex>. Тогда оно имеет вид <tex>A\underset{G'}{\Rightarrow}X_1 X_2...X_k
Пусть <tex>A \underset{G}{\Rightarrow}^*w</tex> и <tex>w \ne \varepsilon</tex>.<br/>
Докажем индукцией по длине порождения, что <tex>A \underset{G'}{\Rightarrow}^*w</tex>.<br/>
'''База'''. Пусть <tex>A \underset{G}{\Rightarrow}^*w</tex>.<br/>Правило <tex>A \rightarrow w</tex> является правилом присутствует в <tex>G</tex>. Поскольку <tex>w \ne \varepsilon</tex>, это же правило будет и в <tex>G'</tex>, поэтому <tex>A \underset{G'}{\Rightarrow}^*w</tex>.<br/>
'''Предположение'''. Пусть из <tex>A \underset{G}{\Rightarrow}^*w</tex> и <tex>w \ne \varepsilon</tex> следует, что <tex>A \underset{G'}{\Rightarrow}^*w </tex> менее, чем за <tex>n</tex> шагов.<br/>
'''Переход'''. Пусть в порождении <tex>n</tex> шагов, <tex>n > 1</tex>. Тогда оно имеет вид <tex>A\underset{G}{\Rightarrow}Y_1 Y_2...Y_m
