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

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

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

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

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

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

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

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

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

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

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

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