![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Операции над языками
По определению язык - это множество цепочек, следовательно, над языками можно выполнять операции, правомерные как для множеств, так и для цепочек (строк символов). Определим некоторые из них. Язык 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 ( Язык 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 * = Позитивная итерация языка L, обозначаемая через L+, - это язык Язык L называется подстановкой языка L2 в язык L1 вместо терминала a (L= Обращение языка L, обозначаемое LR, - это язык, содержащий все обращенные цепочки исходного языка. Формально L = {w R ½ w Î L}. Прежде чем обсуждать практические аспекты данных определений, поговорим о том, как построить грамматику языка, полученного в результате операций над языками, и как определить ее тип.
|