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

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

Язык 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}.

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