Детерминированные автоматы с магазинной памятью, допуск по пустому стеку — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(не показано 9 промежуточных версий 4 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
Определим <b>детерминированный автомат с магазинной памятью, допускающий по пустому стеку</b>, как [[Детерминированные_автоматы_с_магазинной_памятью|детерминированный автомат с магазинной памятью]], у которого нет множества <tex>T</tex> допускающих состояний. Автомат заканчивает свою работу как только стек становится пустым.
+
Определим '''детерминированный автомат с магазинной памятью, допускающий по пустому стеку''' (англ. ''PDA accepting by empty stack''), как [[Детерминированные_автоматы_с_магазинной_памятью|детерминированный автомат с магазинной памятью]], у которого нет множества <tex>T</tex> допускающих состояний. Автомат заканчивает свою работу как только стек становится пустым.
 
}}
 
}}
Определим для него множество допускающих слов <tex>N = \{\omega | (q_0,a_0,Z_0)\vdash^* (p,\epsilon,\epsilon)\}</tex>, где <tex>p</tex> {{---}} произвольное состояние.
+
Определим для него множество допускающих слов <tex>N = \{\omega \mid (q_0,a_0,Z_0)\vdash^* (p,\epsilon,\epsilon)\}</tex>, где <tex>p</tex> {{---}} произвольное состояние.
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
Язык называется <b>беспрефиксным</b>, если для любой пары слов из этого языка ни одно из этих слов не является префиксом другого.
+
Язык называется '''беспрефиксным''' (англ. ''prefix-free''), если для любой пары слов из этого языка ни одно из этих слов не является префиксом другого.
 
}}
 
}}
 
{{Теорема
 
{{Теорема
|statement=Язык <tex>L</tex> допускается ДМП-автоматом, допускающему по пустому стеку <tex>\Leftrightarrow</tex> Язык <tex>L</tex> допускается ДМП-автоматом, допускающему по допускающему состоянию и <tex>L</tex> {{---}} беспрефиксный.
+
|statement=Язык <tex>L</tex> допускается ДМП-автоматом, допускающему по пустому стеку тогда и только тогда, когда язык <tex>L</tex> допускается ДМП-автоматом, допускающему по допускающему состоянию и <tex>L</tex> {{---}} беспрефиксный.
 
|proof=
 
|proof=
 
<tex>\Rightarrow</tex><br>
 
<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>
+
:Допустим, что <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>
 
[[Файл:ДМП1.png]]<br>
 
<tex>\Leftarrow</tex><br>
 
<tex>\Leftarrow</tex><br>
Задан ДМП-автомат с допуском по допускающему состоянию, язык <tex>L</tex> {{---}} беспрефиксный. Если автомат в какойто момент пришел в допускающее состояние, то дальше идти смысла нет, т.к. тогда бы слово, допускаемое этим состоянием было бы префиксом некоторого другого слова. Значит можем удалить все переходы из допускающих состояний и добавить переходы в очистку стека.<br>
+
:Пусть задан ДМП-автомат с допуском по допускающему состоянию, язык <tex>L</tex> {{---}} беспрефиксный. Если автомат в какой-то момент пришел в допускающее состояние, то дальше идти смысла нет, т.к. тогда бы слово, допускаемое этим состоянием было бы префиксом некоторого другого слова. Значит можем удалить все переходы из допускающих состояний и добавить переходы в очистку стека.<br>
 
[[Файл:ДМП2.png]]
 
[[Файл:ДМП2.png]]
 
}}
 
}}
 +
 +
== См. также ==
 +
* [[Детерминированные автоматы с магазинной памятью]]
 +
* [[Автоматы с магазинной памятью]]
 +
* [[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность]]
 +
* [[Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами]]
 +
* [[ДМП-автоматы и неоднозначность]]
 +
 +
==Источники информации==
 +
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' {{---}} '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2008. : ISBN 978-5-8459-1347-0 (рус.)
 +
 +
[[Категория: Теория формальных языков]]
 +
[[Категория: Контекстно-свободные грамматики]]
 +
[[Категория: МП-автоматы]]

Версия 15:54, 3 марта 2018

Определение:
Определим детерминированный автомат с магазинной памятью, допускающий по пустому стеку (англ. PDA accepting by empty stack), как детерминированный автомат с магазинной памятью, у которого нет множества [math]T[/math] допускающих состояний. Автомат заканчивает свою работу как только стек становится пустым.

Определим для него множество допускающих слов [math]N = \{\omega \mid (q_0,a_0,Z_0)\vdash^* (p,\epsilon,\epsilon)\}[/math], где [math]p[/math] — произвольное состояние.

Определение:
Язык называется беспрефиксным (англ. prefix-free), если для любой пары слов из этого языка ни одно из этих слов не является префиксом другого.
Теорема:
Язык [math]L[/math] допускается ДМП-автоматом, допускающему по пустому стеку тогда и только тогда, когда язык [math]L[/math] допускается ДМП-автоматом, допускающему по допускающему состоянию и [math]L[/math] — беспрефиксный.
Доказательство:
[math]\triangleright[/math]

[math]\Rightarrow[/math]

Допустим, что [math]L[/math] не беспрефиксный. Тогда [math]\exists \omega_1, \omega_2 \in L : \omega_2 = \omega_1 \alpha[/math]. Попробуем допустить слово [math]\omega_2[/math]. Тогда автомат остановится сразу после префикса [math]\omega_1[/math], т.к. [math]\omega_1 \in L[/math]. Стек будет пустой, однако до конца слова [math]\omega_2[/math] мы не дойдем, поэтому оно не допустится, хотя содержится в [math]L[/math]. Получили противоречие, значит [math]L[/math] — беспрефиксный.

Построим по заданному ДМП-автомату с допуском по пустому стеку ДМП с допуском по допускающему состоянию.

ДМП1.png
[math]\Leftarrow[/math]

Пусть задан ДМП-автомат с допуском по допускающему состоянию, язык [math]L[/math] — беспрефиксный. Если автомат в какой-то момент пришел в допускающее состояние, то дальше идти смысла нет, т.к. тогда бы слово, допускаемое этим состоянием было бы префиксом некоторого другого слова. Значит можем удалить все переходы из допускающих состояний и добавить переходы в очистку стека.
ДМП2.png
[math]\triangleleft[/math]

См. также

Источники информации

  • Хопкрофт Д., Мотвани Р., Ульман Д.Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2008. : ISBN 978-5-8459-1347-0 (рус.)