Изменения

'''Мгновенная кофигурацияМгновенное описание''' {{---}} пара <tex> \langle p, q \rangle </tex>, <tex> p \in Q </tex>, <tex> q \in \Sigma^*</tex>.

Определим некоторые операции для мгновенных конфигурацийописаний.

Рефлексивно-транзитивное замыкание отношения <tex> \vdash </tex> обозначается <tex> \vdash^*</tex>. Это отношение называется '''выводится за ноль или более шагов'''.<!--Говорят, что <tex> \langle p, \beta \rangle</tex> '''выводится за ноль и более шагов''' из <tex>\langle q, \alpha \rangle </tex>, если <tex>\exists c_1, c_2 \ldots c_n</tex>:* <tex>\langle q, c_1 c_2 \ldots c_n \beta\rangle \vdash \langle u_1, c_2 c_3 \ldots c_n \beta\rangle \vdash \langle u_2, c_3 \ldots c_n \beta\rangle \ldots \vdash \langle u_{n-1}, c_n \beta\rangle \vdash \langle p, \beta \rangle</tex>.--><!--Это также записывают так: <tex>\langle q, \alpha \rangle \vdash^* \langle p, \beta \rangle</tex>.-->