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