What is the Right Context of a Word in Formal Langauge Theory?

100 Views Asked by At

I am reading this paper and am unable to understand this notation in section 2.2 -

The right context of a word $u$ according to a language $W$ is the language {$u^{-1}w$ | $w \in W$}. The equivalence generated over $A^{*}$ by the relations $$u^{-1}W = v^{-1}W, \space \space u,v \in A^{*}$$

is denoted by $\equiv_W$; it is the right syntactic congruence associated with the language $W$

What is the physical interpretation of $u^{-1}$ for some word $u$? If $u^{-1}$ is defined such that $uu^{-1} = \epsilon$ i.e. the word that cancels out a prefix which it is the inverse of, then what happens in $u^{-1}w$, if $w$ does not contain $u$ as a prefix?

If $u$ = "apple" and $v$ = "orange", then what is the string $u^{-1}v$?

1

There are 1 best solutions below

3
On BEST ANSWER

I would understand it as a (confusing/sloppy) way to define the "right context" of $u$ to mean the set $$ \{v\in A^*\mid uv\in W\} $$

There is no inverse operation in formal language theory in general. Formal languages are generally supposed to be subsets of free monoids, which do not have inverses. Assuming that inverses exist would amount to speaking about free groups instead, which is a rather different theory.