Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

Операции над языками



Формальный язык L в алфавите V – это некоторое подмножество: V* LÍV*.

Над языками, как над множествами вводятся теоретико-множественные операции: объединение, пересечение, разность. На декартово произведение похоже соединение (конкатенация) языков, например: L1={па,ма,да}, L2={па,к}, тогда L1×L2={папа,пак,мапа,мак,дапа,дак}.

Очевидно, что L22={па,к}×{па,к}={папа,пак,кпа,кк}.

Имеется также операция подстановки языка в язык [19]. Пусть заданы языки сумм:

Lcm={а,а+а,а+а+а,…} и произведений Lnp={а,аа,ааа,…}. Подстановка Lcm(а®Lnp) дает язык сумм произведений Lcn={аа,ааа,…аа+а,…}.

Итерация языка – это объединениевсех его степеней:

Определение языков – это их задание. Оно осуществляется следующими способами:

· перечислением всех правильных цепочек языка;

· порождением всевозможных цепочек и их «фильтрацией» с помощью так называемых распознавателей, которые распознают требуемые цепочки;

· заданием соответствующей формальной грамматики, определяющей правила построения языка.

Рассмотрим формальные грамматики.





Дата публикования: 2015-02-18; Прочитано: 354 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.006 с)...