38
правок
Изменения
Новая страница: «{{Определение |definition = Определим <b>детерминированный автомат с магазинной памятью, допуска…»
{{Определение
|definition =
Определим <b>детерминированный автомат с магазинной памятью, допускающий по пустому стеку</b>, как [[Детерминированные_автоматы_с_магазинной_памятью|детерминированный автомат с магазинной памятью]], у которого нет множества <tex>F</tex> допускающих состояний. Автомат заканчивает свою работу как только стек становится пустым. Определим для него множество допускающих слов <tex>N = \{\omega | (q_0,a_0,Z_0)\vdash^* (p,\epsilon,\epsilon)\}</tex>, где <tex>p</tex> {{---}} произвольное состояние.
}}
{{Определение
|definition =
Язык называется <b>беспрефиксным</b>, если для него верно следующее: для любой пары слов из этого языка ни одно из этих слов не является префиксом другого.
}}
{{Теорема
|statement=Язык <tex>L</tex> допускается ДМП-автоматом, допускающему по пустому стеку <tex>\Leftrightarrow</tex> Язык <tex>L</tex> допускается ДМП-автоматом, допускающему по допускающему состоянию и <tex>L</tex> {{---}} беспрефиксный.
|proof=
<tex>\Rightarrow</tex><br>
Допустим, что <tex>L</tex> не беспрефиксный. Тогда <tex>\exists \omega_1, \omega_2 \in L : \omega_2 = \omega_1 \alpha</tex>. Попробуем допустить слово <tex>\omega_2</tex>. Тогда автомат остановится сразу после префикса <tex>\omega_1</tex>, т.к. <tex>\omega_1 \in L</tex>. Стек будет пустой, однако до конца слова <tex>\omega_2</tex> мы не дойдем, поэтому оно не допустится, хотя содержится в <tex>L</tex>. Получили противоречие, значит <tex>L</tex> {{---}} беспрефиксный.<br>
Построим по заданному ДМП-автомату с допуском по пустому стеку ДМП с допуском по допускающему состоянию.<br>
[[Файл:ДМП1.png]]<br>
<tex>\Leftarrow</tex><br>
Задан ДМП-автомат с допуском по допускающему состоянию, язык <tex>L</tex> {{---}} беспрефиксный. Если автомат в какойто момент пришел в допускающее состояние, то дальше идти смысла нет, т.к. тогда бы слово, допускаемое этим состоянием было бы префиксом некоторого другого слова. Значит можем удалить все переходы из допускающих состояний и добавить переходы в очистку стека.<br>
[[Файл:ДМП2.png]]
}}
|definition =
Определим <b>детерминированный автомат с магазинной памятью, допускающий по пустому стеку</b>, как [[Детерминированные_автоматы_с_магазинной_памятью|детерминированный автомат с магазинной памятью]], у которого нет множества <tex>F</tex> допускающих состояний. Автомат заканчивает свою работу как только стек становится пустым. Определим для него множество допускающих слов <tex>N = \{\omega | (q_0,a_0,Z_0)\vdash^* (p,\epsilon,\epsilon)\}</tex>, где <tex>p</tex> {{---}} произвольное состояние.
}}
{{Определение
|definition =
Язык называется <b>беспрефиксным</b>, если для него верно следующее: для любой пары слов из этого языка ни одно из этих слов не является префиксом другого.
}}
{{Теорема
|statement=Язык <tex>L</tex> допускается ДМП-автоматом, допускающему по пустому стеку <tex>\Leftrightarrow</tex> Язык <tex>L</tex> допускается ДМП-автоматом, допускающему по допускающему состоянию и <tex>L</tex> {{---}} беспрефиксный.
|proof=
<tex>\Rightarrow</tex><br>
Допустим, что <tex>L</tex> не беспрефиксный. Тогда <tex>\exists \omega_1, \omega_2 \in L : \omega_2 = \omega_1 \alpha</tex>. Попробуем допустить слово <tex>\omega_2</tex>. Тогда автомат остановится сразу после префикса <tex>\omega_1</tex>, т.к. <tex>\omega_1 \in L</tex>. Стек будет пустой, однако до конца слова <tex>\omega_2</tex> мы не дойдем, поэтому оно не допустится, хотя содержится в <tex>L</tex>. Получили противоречие, значит <tex>L</tex> {{---}} беспрефиксный.<br>
Построим по заданному ДМП-автомату с допуском по пустому стеку ДМП с допуском по допускающему состоянию.<br>
[[Файл:ДМП1.png]]<br>
<tex>\Leftarrow</tex><br>
Задан ДМП-автомат с допуском по допускающему состоянию, язык <tex>L</tex> {{---}} беспрефиксный. Если автомат в какойто момент пришел в допускающее состояние, то дальше идти смысла нет, т.к. тогда бы слово, допускаемое этим состоянием было бы префиксом некоторого другого слова. Значит можем удалить все переходы из допускающих состояний и добавить переходы в очистку стека.<br>
[[Файл:ДМП2.png]]
}}
