Изменения

Перейти к: навигация, поиск

Перечислимые языки

3 байта добавлено, 23:03, 10 марта 2019
Основные определения
'''return''' x
U.insert(x)
 .'''''}}
{{Теорема
Рассмотрим полуразрешители для <tex>L</tex> и <tex>\overline L</tex> и одновременно запустим их для одного и того же элемента <tex>x</tex>. <tex>x</tex> принадлежит либо <tex> L </tex>, либо <tex>\overline{L}</tex>, поэтому один из полуразрешителей успешно отработает и не зависнет. Значит, мы за конечное время узнаем, лежит ли <tex>x</tex> в <tex>L</tex> или нет. Таким образом, мы построили разрешитель для <tex>L</tex>, то есть <tex>L</tex> {{---}} разрешимый.
}}
 
== Примеры перечислимых языков ==
36
правок

Навигация