Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


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




 

По определению язык - это множество цепочек, следовательно, над языками можно выполнять операции, правомерные как для множеств, так и для цепочек (строк символов). Определим некоторые из них.

Язык L называется объединением языков L1 и L2 (L= L1 È L2), если он содержит все цепочки из L1 вместе со всеми цепочками из L2 . Формально L = {a½a Î L1 или a Î L2}.

Язык L называется пересечением языков L1 и L2 (L= L1 Ç L2), если он содержит все цепочки, принадлежащие как L1, так и L2 . Формально L={a½a Î L1 и a Î L2}.

Язык L называется разностью языков L1 и L2 (L= L1 \ L2), если он содержит все цепочки из L1, которые не принадлежат L2 . Формально L={a½aÎL1 и aÏL2}.

Язык L называется дополнением языка L1 ( ), если он содержит все цепочки из некоторого универсального языка L2, которые не принадлежат L1 . Формально L={a½a Ï L1}.

Язык L называется конкатенацией (сцеплением) языков L1 и L2 (L= L1 L2), если он содержит попарные конкатенации всех возможных цепочек из L1 и L2 . Формально L={ab½a Î L1 и b Î L2}.

Итерация языка L, обозначаемая L*, определяется следующим образом:

(1) L0 = { e },

(2) Ln = LLn-1 для n ³ 0

(3) L*= Ln.

Позитивная итерация языка L, обозначаемая через L+, - это язык Ln. Заметим, что L+ = LL* = L*L и L* = L+ È { e }.

Язык L называется подстановкой языка L2 в язык L1 вместо терминала a (L= ), если он содержит все цепочки языка L1 , в которых терминал a заменен на все возможные цепочки языка L2.

Обращение языка L, обозначаемое LR, - это язык, содержащий все обращенные цепочки исходного языка. Формально L = {w R ½w Î L}.

Прежде чем обсуждать практические аспекты данных определений, поговорим о том, как построить грамматику языка, полученного в результате операций над языками, и как определить ее тип.


Поделиться:

Дата добавления: 2014-11-13; просмотров: 99; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.005 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты