doc/unambig.tex

   1 \documentclass{amsart}
   2
   3 \usepackage{amsmath}
   4 \usepackage{xspace}
   5 \usepackage{amssymb}
   6 \usepackage{bcprules}
   7
   8 \newcommand{\ensmath}[1]{\ensuremath{#1}\xspace}
   9
  10 \newcommand{\opnam}[1]{\ensmath{\operatorname{\mathit{#1}}}}
  11 \newcommand{\nget}{\opnam{get}}
  12 \newcommand{\nput}{\opnam{put}}
  13 \newcommand{\ncreate}{\opnam{create}}
  14 \newcommand{\nkey}{\opnam{key}}
  15 \newcommand{\lget}[1]{\opnam{get}{#1}}
  16 \newcommand{\lput}[3]{\opnam{put}{#1}\,{#2}\,{#3}}
  17 \newcommand{\lcreate}[2]{\opnam{create}{#1}\,{#2}}
  18 \newcommand{\lkey}[1]{\nkey{#1}}
  19
  20 \newcommand{\suff}{\ensmath{\operatorname{suff}}}
  21 \newcommand{\pref}{\ensmath{\operatorname{pref}}}
  22 \newcommand{\lenstype}[3][K]{\ensmath{{#2}\stackrel{#1}{\Longleftrightarrow}{#3}}}
  23 \newcommand{\tree}[1]{\ensmath{[#1]}}
  24 \newcommand{\niltree}{\ensmath{[]}}
  25 \newcommand{\Regexp}{\ensmath{\mathcal R}}
  26 \newcommand{\reglang}[1]{\ensmath{[\![{#1}]\!]}}
  27 \newcommand{\lens}[1]{\opnam{#1}}
  28 \newcommand{\eps}{\ensmath{\epsilon}}
  29 \newcommand{\conc}[2]{\ensmath{#1\cdot #2}}
  30 \newcommand{\uaconc}[2]{\ensmath{#1\cdot^{!} #2}}
  31 \newcommand{\xconc}[2]{\ensmath{#1\odot #2}}
  32 \newcommand{\alt}[2]{\ensmath{#1\,|\,#2}}
  33 \newcommand{\cstar}[1]{\ensmath{#1^*}}
  34 \newcommand{\uastar}[1]{\ensmath{#1^{!*}}}
  35 \newcommand{\Trees}{\ensmath{\mathcal T}}
  36 \newcommand{\Words}{\ensmath{\Sigma^*}}
  37 \newcommand{\Wordsrhd}{\ensmath{\Words\cup\rhd}}
  38 \newcommand{\tmap}[2]{\ensmath{#1\mapsto #2}}
  39 \newcommand{\tmaptt}[2]{\ensmath{{\mathtt #1}\mapsto {\mathtt #2}}}
  40 \newcommand{\dom}[1]{\ensmath{\mathrm{dom}(#1)}}
  41 \newcommand{\List}{\ensmath{\mathtt{List}}}
  42 \newcommand{\redigits}{\ensmath{\mathtt{D}}}
  43
  44 \newcommand{\noeps}[1]{\ensmath{{#1}_{\setminus \epsilon}}}
  45
  46 \newtheorem{theorem}{Theorem}
  47 \newtheorem{lemma}[theorem]{Lemma}
  48 {\theoremstyle{definition}
  49   \newtheorem{defn}{Definition}
  50   \newtheorem*{remark}{Remark}
  51   \newtheorem*{example}{Example}}
  52
  53 \begin{document}
  54
  55 \section*{Ambiguity}
  56
  57 \begin{defn}
  58   For a language $L$ over $\Sigma$, define
  59   \begin{equation*}
  60     \begin{split}
  61       \suff(L) = \{ p \in \Sigma^+ | \exists u \in L: up \in L \}\\
  62       \pref(L) = \{ p \in \Sigma^+ | \exists v \in L: pv \in L \}
  63     \end{split}
  64   \end{equation*}
  65 \end{defn}
  66 Note that $\suff(L)$ and $\pref(L)$ do not contain $\eps$. Note also that
  67 we only take prefixes and suffixes that can be expanded to a word in $L$
  68 with another word in $L$, not any word in $\Sigma^*$.
  69
  70 The set $\suff(L)$ is identical to the left quotient $L^{-1}L$ of $L$ by
  71 itself. Similarly, $\pref(L) = LL^{-1}$.
  72
  73 \begin{defn}
  74 Two languages $L_1$ and $L_2$ are \emph{unambiguosuly concatenable},
  75 written \uaconc{L_1}{L_2}, iff for every $u_1, v_1 \in L_1$ and $u_2, v_2
  76 \in L_2$, if $u_1u_2=v_1v_2$ then $u_1=v_1$ and $u_2=v_2$.
  77 \end{defn}
  78
  79 \begin{lemma}
  80   The languages $L_1$ and $L_2$ are unambiguously concatenable if and only
  81   if $\suff(L_1) \cap \pref(L_2) = \emptyset$.
  82 \end{lemma}
  83 \begin{proof}
  84 Let $L_1$ and $L_2$ not unambiguously concatenable, i.e. there exist $u_1$,
  85 $v_1$ in $L_1$ and $u_2$, $v_2$ in $L_2$ such that $u_1u_2=v_1v_2$ and
  86 $u_1\neq v_1$ and therefore $u_2 \neq v_2$. Assume $u_1$ is strictly
  87 shorter than $v_1$, therefore $v_1 = u_1 p, p \neq \eps$. With that $v_1v_2
  88 = u_1pv_2$ and $u_2 = pv_2$ and $p \in \suff(L_1) \cap \pref(L_2)$
  89
  90 Let $p \in \suff(L_1) \cap \pref(L_2)$. That implies that
  91 there are $u\in L_1$ and $v\in L_2$ such that $up\in L_1$ and $pv\in
  92 L_2$. The word $upv$ can be split as $\conc{up}{v}$ and as $\conc{u}{pv}$
  93 and therefore $L_1$ and $L_2$ are not unambiguously concatenable.
  94 \end{proof}
  95
  96 To ease notation we write $\noeps{L}$ for $L\setminus \{
  97 \epsilon \}$.
  98
  99 \begin{defn}
 100 A language $L$ is \emph{unambiguously iterable}, written \uastar{L}, iff
 101 for every $u_1,\dots,u_m, v_1,\dots,v_n \in \noeps{L}$ with $u_1\cdots u_m
 102 = v_1 \cdots v_n$, $m=n$ and $u_i = v_i$.
 103 \end{defn}
 104
 105 It is very important that we exclude $\epsilon$ in the definition of
 106 unambiguous iteration, since otherwise \emph{any} language $L$ that
 107 contains $\epsilon$ is trivially not ambiguously iterable, even though that
 108 presents no problems for our purposes, since we never split $\epsilon$ into
 109 more than one word.
 110
 111 \begin{lemma}
 112 The language $L$ is unambiguously iterable if and only if $\noeps{L}$ and
 113 $\noeps{\cstar{L}}$ are unambiguously concatenable.
 114 \end{lemma}
 115 \begin{proof}
 116 Let $L$ be unambiguously iterable, and assume that there is $u_1v_1 =
 117 u_2v_2$ with $u_i \in \noeps{L}$ and $v_i \in \noeps{\cstar{L}}$ and $u_1
 118 \neq u_2$. This contradicts $\uastar{L}$ since $\noeps{L}\cdot
 119 \noeps{\cstar{L}}\subseteq \cstar{L}$.
 120
 121 Let $\uaconc{\noeps{L}}{\noeps{\cstar{L}}}$ and assume there are
 122 $u_1,\dots,u_m, v_1,\dots,v_n \in \noeps{L}$ with $u_1\cdots u_m = v_1
 123 \cdots v_n$, but there is an $i \leq \min(m,n)$ with $u_i \neq v_i$. We can
 124 assume that $u_1 \neq v_1$\footnote{if $u_1 = v_1$, we simply use
 125   $u_2\cdots u_m$ and $v_2 \cdots v_n$ for this argument}, and therefore
 126 $\min(m,n)\geq 2$. Since $u_1$ and $v_1$ are in $\noeps{L}$, we have an
 127 ambiguous split of a word from $\noeps{L}\cdot\noeps{\cstar{L}}$,
 128 contradicting the initial assumption.
 129 \end{proof}
 130
 131 \begin{example}
 132 Using regular expression notation, the language $L=(a|b|c|abc)$ is
 133 unambiguously concatenable with itself, but not unambiguosly
 134 iterable. $\cstar{L} = (a|b|c)^*$ and the word $abcabc$ can be split into
 135 $abc\cdot abc$ and $a\cdot bcabc$. This example shows that $\uaconc{L}{L}$
 136 does not imply $\uastar{L}$, but as the previous lemma showed,
 137 $\uaconc{\noeps{L}}{\noeps{\cstar{L}}}$ does.
 138 \end{example}
 139
 140 If you have $P = \suff(L_1) \cap \pref(L_2)$, how do you generate a word that
 141 is ambiguous ?
 142 \end{document}
 143
 144 %% TeX-parse-self: t
 145 %% TeX-auto-save: t
 146
 147 %% Local Variables:
 148 %% TeX-master: "unambig.tex"
 149 %% compile-command: "pdflatex -file-line-error -halt-on-error unambig.tex"
 150 %% End: