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

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

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

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

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

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

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

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

(1) L⁰ = { e },

(2) Lⁿ = LL^n-1 для n ³ 0

(3) L^*= Lⁿ.

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

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

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

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