Skip to content
Parsing

Languages with context

There are several variations of languages with “context”:

CF with one-sided context

Languages of strings in contexts: L⊆Σ∗×Σ∗L \subseteq \Sigma^* \times \Sigma^*:

L1∪L2={(x,y)∣(x,y)∈L1∨(x,y)∈L2}L1∩L2={(x,y)∣(x,y)∈L1∧(x,y)∈L2}\begin{align*} L_1 \cup L_2 &= \{ (x,y) \mid (x,y) \in L_1 \lor (x,y) \in L_2\} \\ L_1 \cap L_2 &= \{ (x,y) \mid (x,y) \in L_1 \land (x,y) \in L_2\} \\ \end{align*}

Left context:

L1⋅⊲L2={(x,yz)∣(x,y)∈L1∧(xy,z)∈L2}⊲L1={(x,y)∣(ε,x)∈L1∧y∈Σ∗}⊴L1={(x,y)∣(ε,xy)∈L1}⊲L1=?(ε∩⊴L1)Σ∗⊴L1=?Σ∗(ε∩⊲L1)\begin{align*} L_1 \cdot^\lhd L_2 &= \{ (x,yz) \mid (x,y) \in L_1 \land (xy,z) \in L_2\} \\ \lhd L_1 &= \{ (x,y) \mid (\varepsilon, x) \in L_1 \land y \in \Sigma^* \} \\ \trianglelefteq L_1 &= \{ (x,y) \mid (\varepsilon, xy) \in L_1 \} \\ \\ \lhd L_1 & \stackrel{?}{=} (\varepsilon \cap \trianglelefteq L_1) \Sigma^* \\ \trianglelefteq L_1 & \stackrel{?}{=} \Sigma^* (\varepsilon \cap \lhd L_1) \\ \end{align*}

Right context:

L1⋅⊳L2={(zy,x)∣(z,yx)∈L1∧(y,x)∈L2}⊳L1={(y,x)∣(x,ε)∈L1∧y∈Σ∗}⊵L1={(y,x)∣(yx,ε)∈L1}⊳L1=?Σ∗(ε∩⊵L1)⊵L1=?(ε∩⊳L1)Σ∗\begin{align*} L_1 \cdot^\rhd L_2 &= \{ (zy, x) \mid (z, yx) \in L_1 \land (y, x) \in L_2\} \\ \rhd L_1 &= \{ (y,x) \mid (x, \varepsilon) \in L_1 \land y \in \Sigma^* \} \\ \trianglerighteq L_1 &= \{ (y,x) \mid (yx, \varepsilon) \in L_1 \} \\ \\ \rhd L_1 & \stackrel{?}{=} \Sigma^* (\varepsilon \cap \trianglerighteq L_1) \\ \trianglerighteq L_1 & \stackrel{?}{=} (\varepsilon \cap \rhd L_1) \Sigma^* \\ \end{align*}

Reversal:

LR={(xR,yR)∣(y,x)∈L}(L1⋅⊲L2)R=L2R⋅⊳L1R\begin{align*} L^R &= \{ (x^R, y^R) \mid (y, x) \in L \} \\ (L_1 \cdot^\lhd L_2)^R &= L_2^R \cdot^\rhd L_1^R \\ \end{align*}

Read more here:

CFwLA

L1⋅L2={(xy,z)∣(x,yz)∈L1∧(y,z)∈L2}&L1={(ε,xy)∣(x,y)∈L1}!L1=({ε}×Σ∗)∖&L1&L1≈⊳(L1Σ∗)\begin{align*} L_1 \cdot L_2 &= \{ (xy,z) \mid (x,yz) \in L_1 \land (y,z) \in L_2\} \\ \& L_1 &= \{ (\varepsilon,xy) \mid (x,y) \in L_1 \} \\ ! L_1 &= (\{ \varepsilon \} \times \Sigma^*) \setminus \& L_1 \\ \\ \& L_1 &\approx \rhd (L_1 \Sigma^*)\\ \end{align*}

Read more here:

Conjuctive

(&L1)L2≈(L1Σ∗)∩L2if ∣w1∣≤∣w2∣,w1∈L1,w2∈L2(\& L_1) L_2 \approx (L_1 \Sigma^*) \cap L_2 \\ \text{if } |w_1| \leq |w_2|, w_1 \in L_1, w_2 \in L_2

Limited Boolean

(!L1)L2≈(L1Σ∗)′∩L2if ∣w1∣≤∣w2∣,w1∈L1,w2∈L2(! L_1) L_2 \approx (L_1 \Sigma^*)' \cap L_2 \\ \text{if } |w_1| \leq |w_2|, w_1 \in L_1, w_2 \in L_2