Операции над языками (1134708), страница 4
Текст из файла (страница 4)
Но здесь мы можем превращать все нетерминалы D в терминальные символы, если только они сначала мигрируют к правому концу сентенциальной формы. Причем как только нетерминал D превращается в терминал d, ниодин символ D больше не может быть превращен ни в d, ни в c. Теорема следуетиз наблюдения, что L(G1) = L (G2) / dc*.В заключение главы приведем сводку описанных в ней свойств замкнутостидля регулярных, контекстно-свободных, контекстно-зависимых и языков типа 0,— см. табл. 9.1.128Т а бл .
9.1Замкнутость относительно операцийОбъединениеКонкатенацияЗамыканиеОбращениеПересечениеДополнениеПересечение с регулярным множествомПодстановкаε-Свободная подстановкаgsm-Отображениеε-Свободное gsm-отображениеОбратные gsm-отображенияk-Ограниченное стираниеДеление на регулярное множестворег.++++++++++++++Класс языкаконт.конт.свобод. завис.++++++++–+–?++++++++++++++++типа0+++++–++++++++В табл.
9.1 символом + отмечен тот факт, что соответствующий класс языковобладает свойством замкнутости относительно соответствующей операции;символ – (минус) обозначает отсутствие соответствующего свойства замкнутости для соответствующего класса языков; символ ? (вопросительный знак) означает, что пока не выяснено, замкнут ли класс контекстно-зависимых языков относительно дополнения или не замкнут.129.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
